The Polynomial Compatibility Conjecture for Low-Influence Degree-d Distributions

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

A purely combinatorial question about polynomials, which several quantum black-box separations are waiting on. Take two distributions over low-degree, unit-norm functions on \(\mathcal{Y}^N\) whose coordinates all have small influence on average. Must there be one function in the support of each, and one point, where both are non-zero? The two distributions come from the two branches of a purified quantum party, and a point where both are non-zero is what “these two outcomes are simultaneously realizable” means — two openings of a commitment, or two consistent executions. It is known for exponentially small influences and false for large ones; the conjecture is that it survives all the way down to inverse-polynomial, which is the regime the separations need.

View PDF · Download LaTeX source

Let \(\mathcal{Y}\) be a finite abelian group. For \(f : \mathcal{Y}^N \to \mathbb{C}\), expand \(f\) in the character basis; \(\deg(f)\) is the largest number of non-trivial coordinates in a character with a non-zero coefficient, \(\lVert f \rVert_2\) is taken under the uniform distribution on \(\mathcal{Y}^N\), and \(\mathrm{Inf}_i(f)\) is the total squared weight on characters non-trivial at coordinate \(i\).

Conjecture. There exist a finite abelian group \(\mathcal{Y}\), constants \(c_1 \in (0,1]\) and \(c_2 > 0\), and a function \(\delta : \mathbb{N} \to (0,1]\) with \(\delta(d) \ge c_1 d^{-c_2}\) for all \(d \ge 1\) — equivalently \(\delta(d) \ge 1/p(d)\) for some polynomial \(p\) — such that for every \(d, N \in \mathbb{N}\) the following holds. Let \(\mathbf{F}\) and \(\mathbf{G}\) be any two distributions over functions \(\mathcal{Y}^N \to \mathbb{C}\) with

\(\lVert f \rVert_2 = 1\) and \(\lVert g \rVert_2 = 1\) for every \(f \in \mathrm{supp}(\mathbf{F})\), \(g \in \mathrm{supp}(\mathbf{G})\);
\(\deg(f) \le d\) and \(\deg(g) \le d\) throughout both supports;
\(\mathbb{E}_{f \gets \mathbf{F}}[\mathrm{Inf}_i(f)] \le \delta(d)\) and \(\mathbb{E}_{g \gets \mathbf{G}}[\mathrm{Inf}_i(g)] \le \delta(d)\) for every \(i \in [N]\).

Then there exist \(f \in \mathrm{supp}(\mathbf{F})\), \(g \in \mathrm{supp}(\mathbf{G})\) and \(x \in \mathcal{Y}^N\) with \(f(x) \cdot g(x) \ne 0\).

Why the constant in \(\delta\) is load-bearing. Writing the bound as \(\delta(d) \ge d^{-c}\) instead would force \(\delta(1) = 1\), and the statement is then false: over \(\mathcal{Y} = \mathbb{Z}_2\) with \(N = 1\), the degree-one unit-norm functions \(f = (1+x)/\sqrt{2}\) and \(g = (1-x)/\sqrt{2}\) have \(\mathrm{Inf}_1 = 1/2\) and vanish at opposite points, so point masses on them refute it. The papers’ own \(1/\mathrm{poly}(d)\) — admitting, say, \(\delta(d) = 1/(100d)\) — is untouched by this, and is what is transcribed above.

Open in the regime that matters, and pinned from both sides.

Proved for exponentially small influences. Theorem 4.4 of the paper that introduced the conjecture establishes it whenever \(\delta < \lvert\mathcal{Y}\rvert^{-d}/d\). That paper also shows (its Theorem 5.6) that the polynomial formulation is equivalent to a quantum-state formulation, so nothing is lost by working combinatorially.

False for \(\delta \ge 1/(2d)\). Its Appendix B rules that regime out, and shows the degree and influence hypotheses are needed on both distributions rather than one.

What is left, and what it buys. Everything between \(\lvert\mathcal{Y}\rvert^{-d}/d\) and \(1/(2d)\). Any \(\delta\) that is \(1/\mathrm{poly}(d, \log\lvert\mathcal{Y}\rvert)\) already suffices for a polynomial-query attack, which is why the inverse-polynomial regime is the target. The later paper assumes the conjecture throughout — its Theorem 1.1, Section 4, Lemma 4.4 and Construction 4.5 are all conditional on it — to rule out quantum black-box constructions of non-interactive commitments from post-quantum one-way functions.

The asymmetry of the two directions. \(\mathcal{Y}\) is existentially quantified, so a proof for one finite abelian group — \(\mathbb{Z}_2\), say — settles the conjecture, while a refutation has to rule out every finite abelian group.

The conjecture is what remains after Zhandry’s compressed-oracle technique is applied to a black-box separation argument. Classically one records the oracle positions a party asked and fixes a partial oracle consistent with that record; a superposition query cannot be recorded, so the argument is re-run in the purified view with the oracle register in the Fourier basis. A \(d\)-query algorithm is then sparse in that basis, each branch of the purified party becomes a distribution over degree-\(d\), unit-norm, low-influence functions, and “both branches are simultaneously realizable” becomes exactly the non-vanishing condition above.

The source papers note a kinship with the Aaronson–Ambainis line on the need for structure in quantum speedups, and the downstream construction replaces Schwartz–Zippel with the Donoho–Stark support-size uncertainty principle to boost a single compatible oracle into a large set of them.

This page is the merge of two harvested drafts. polynomial-compatibility was taken from ePrint 2022/218 and polynomial-compatibility-2 from ePrint 2023/570; they state the same conjecture, since the second paper explicitly uses “the Polynomial Compatibility Conjecture of [ACC+22]”. The LaTeX published here is the second, both because its parameterization is the correct one (see the note under Statement) and because it takes the codomain to be \(\mathbb{C}\) rather than \(\mathbb{R}\), which is what the quantum application needs. The first draft stays in latex/conjectures/ and is not separately promoted.

Prove or refute the conjecture for \(\delta(d) = 1/\mathrm{poly}(d)\), for some finite abelian group.
Close the gap from either end: push the proof above \(\lvert\mathcal{Y}\rvert^{-d}/d\), or push the counterexamples below \(1/(2d)\).
Decide whether the answer depends on the group at all — whether \(\mathbb{Z}_2\) is representative, given the existential quantifier.
Check whether the quantum-state formulation remains equivalent in the inverse-polynomial regime, or only where the equivalence was proved.
Formalize the statement in Lean. Characters on \(\mathcal{Y}^N\), degree, and influence are all elementary but none are in place.

Austrin, Chung, Chung, Fu, Lin, and Mahmoody. On the Impossibility of Key Agreements from Quantum Random Oracles. Cryptology ePrint Archive, Report 2022/218; CRYPTO 2022, pp. 165–194. Where the conjecture is introduced; Theorem 4.4 (exponentially small influences), Theorem 5.6 (equivalence with the quantum-state formulation), Appendix B (the refuted regime).
Chung, Lin, and Mahmoody. Black-Box Separations for Non-Interactive Commitments in a Quantum World. Cryptology ePrint Archive, Report 2023/570; EUROCRYPT 2023. Conjecture 2.8, the restatement transcribed above, and the separation built on it.
Zhandry. How to record quantum queries, and applications to quantum indifferentiability. CRYPTO 2019, pp. 239–268. The compressed-oracle technique the whole reduction to polynomials rests on.
Mahmoody and Pass. The curious case of non-interactive commitments — on the power of black-box vs. non-black-box use of primitives. CRYPTO 2012, pp. 701–718. The classical separation being lifted.
Donoho and Stark. Uncertainty principles and signal recovery. SIAM Journal on Applied Mathematics 49(3):906–931, 1989. Used downstream in place of Schwartz–Zippel.