CS Paper Radar

A proof of the Aaronson-Ambainis conjecture

David Turturean

cs.CC quant-ph ·submitted 2026-11-06 17:36 UTC · v1
theorycode/data

Abstract

Aaronson and Ambainis conjectured that every bounded polynomial of low degree on the discrete cube has an influential variable. They showed that the conjecture implies that the acceptance probability of every quantum algorithm making $T$ queries can be approximated on most inputs by a classical algorithm making $\mathrm{poly}(T)$ queries. We prove their conjecture: every function $f\colon\{-1,1\}^n\to[-1,1]$ of degree at most $d\ge1$ has a variable of influence at least $c\,\operatorname{Var}(f)^{5/2}/d^{6}$, where $c>0$ is an absolute constant. In the original formulation, for polynomials of degree at most $d$ with values in $[0,1]$ on $\{0,1\}^n$ and variance at least $\varepsilon$, this gives a variable of influence at least $(\varepsilon/d)^{7}$. The proof is elementary, with steps inspired by works of others. Thus, as Aaronson and Ambainis anticipated, superpolynomial quantum speedups in the query model require structure, such as a promise on the inputs.

Comment
60 pages. Lean formalization and reproducibility materials: https://github.com/physical-superintelligence/aaronson-ambainis

Closest papers

Nearest neighbours by meaning across the whole index.

Proof of the Aaronson-Ambainis Conjecture: An Exposition

cs.CC quant-ph ·2026-11-08 ·Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan
similarity 0.74
Abstract · 30 pages, 6 figures

We give an exposition of a recent proof of the Aaronson-Ambainis conjecture, which states that every degree-$d$ polynomial $p : \{0,1\}^n \to [0,1]$ has a variable of influence at least $\mathrm{poly}(\mathrm{Var}(p)/d)$. This implies that quantum query algorithms for decision problems can be efficiently simulated classically on most inputs. It also yields a near-equivalence between the status of the $\mathsf{BPP}$ vs. $\mathsf{BQP}$ problem in the random oracle and unrelativized worlds. We organize the proof around four main steps and discuss how each connects to the literature on the analysis of boolean functions and probabilistic combinatorics. To bring out the key ideas, we do not optimize parameters, and our presentation yields weaker exponents than the original. $\textbf{Authors' note.}$ The proof was discovered by David Turturean using a research system developed at Physical Superintelligence (PSI), in combination with a non-public Anthropic model. The proof was then shared with the authors, who worked to understand it and prepare this exposition. Anthropic's public models were used in this process. The authors did not receive financial compensation from Anthropic or PSI. This article is not intended for publication at a conference or in a journal.

0.26

A short proof of the Aaronson-Ambainis Conjecture via the completion framework

cs.CC quant-ph ·2026-11-09 ·Thomas Huffstutler, David Miloschewsky, Supartha Podder
similarity 0.71
Abstract · 7 pages

We give a short proof of the Aaronson-Ambainis conjecture. If a partial Boolean function $f$ is defined on a $δ$-fraction of all $n$-bit strings and have quantum query complexity $Q(f)$, then, for every $0<ε<1$, a deterministic algorithm computes $f$ correctly on at least a $1-ε$ fraction of its domain using $O( Q(f)^6 / (εδ)^2)$ queries. Our proof uses the completion framework and establishes a more general bound in terms of the classical adversary measure. The only result we use from Turturean's recent proof is a special case of his certificate inequality, for which we provide a self-contained proof. We also derive the stronger variant of the Aaronson-Ambainis Conjecture, the bounded-polynomial influence conjecture, from our main result in the appendix.

0.17

Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms

cs.CC quant-phmath.FA ·2026-09-04 ·Francisco Escudero Gutiérrez, Miquel Saucedo, Carlos Palazuelos
theory similarity 0.68
Abstract · 30 pages

We consider the problem of establishing limitations on the power of quantum query algorithms via the completely bounded polynomial method. In particular, we prove several optimal functional inequalities involving different notions of completely bounded polynomials. These inequalities lead to limiting theorems for the power of quantum query algorithms that improve on prior works. 1. An optimal root-influence bound for block-multilinear polynomials. Prior work showed that block-multilinear polynomials $p$ of degree $t$ satisfy a root-influence bound, $\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t^2$, which is stronger than the bound appearing in the Aaronson-Ambainis conjecture. We find the optimal constant in that inequality: $\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t$. Since the amplitudes of quantum algorithms that query disjoint blocks of inputs-such as $t$-fold forrelation- are block-multilinear polynomials with $\|p\|_{\text{cb}}\leq 1,$ our inequality shows that they satisfy $t\geq \sum_i\sqrt{\mathrm{Inf}_i[p]}$. We prove that this inequality yields both a more efficient classical simulation than prior results based on the Aaronson-Ambainis argument, and a qualitative improvement: all classical queries are nonadaptive. 2. Optimal Fourier growth of the highest level of quantum query algorithms. We show that for every polynomial $p$ defined on $\{-1,1\}^n$ of degree $2t$, the Fourier Growth at the level $2t,$ namely $\|\widehat p_{2t}\|_{\ell_1}$, satisfies $\|\widehat p_{2t}\|_{\ell_1}\leq (en/(2t-1))^{\frac{2t-1}{2}}\|p\|_{\text{cb}}$. This is optimal up to the factor $e$, as witnessed by $2t$-fold forrelation. As quantum query algorithms that make $t$ queries (to the whole input) satisfy $\|p\|_{\text{cb}}\leq 1$, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).

0.55

Optimal bound for the polynomial Littlewood-Offord problem

cs.CC math.COmath.PR ·2026-10-06 ·Alexandr Grebennikov
similarity 0.64
Abstract · 9 pages

We present an exposition of an argument, discovered by GPT-6 Pro, that gives an optimal bound for the polynomial Littlewood-Offord problem. Namely, let $F$ be a degree-$d$ multilinear polynomial that contains $r$ degree-$d$ monomials involving disjoint sets of variables. Then, for i.i.d. Rademacher random variables $ξ_1, \ldots, ξ_n$, we have $\mathbb{P}[F(ξ_1, \ldots, ξ_n) = 0] = O_d(r^{-1/2})$. This improves upon the previous bound of $(\log r)^{O_d(1)} r^{-1/2}$ due to Meka, O. Nguyen, and Vu, and resolves a conjecture attributed to H. Nguyen and Vu. The key part of the proof is an estimate for the total influence of bounded-degree rational functions, which resolves a recent conjecture of Kothari, Kovacs-Deak, Wang, and Yang.

0.22

Exponential Sampling Lower Bounds for Polynomial Sources

cs.CC math.CO ·2026-09-06 ·Yan Zhong
similarity 0.64
Abstract · 17 pages

A degree-$d$ polynomial source is the output of a polynomial map of degree at most $d$ over $\mathbb{F}_2$ on arbitrarily many uniform random bits. Khodabandeh and Shinkar (FOCS '26) proved that $\mathrm{Ber}(1/3)^{\otimes N}$ has statistical distance $1-o(1)$ from every constant-degree polynomial source and conjectured exponentially small overlap. Independently of Khodabandeh and Shinkar, Byramji, Kane, Morris, and Ostuni (RANDOM '26) asked for an explicit target distribution at distance $1-\exp(-N^{Ω_d(1)})$. We resolve both questions. For every fixed $d\geq1$, every degree-$d$ polynomial source has overlap at most $\exp(-c_dN)$ with $\mathrm{Ber}(1/3)^{\otimes N}$, where $c_d>0$ is independent of the seed length. For quadratics, $c_2=2^{-26}$ suffices. We amplify Khodabandeh and Shinkar's uniform separation of acceptance probabilities from non-dyadic parameters (numbers not of the form $a/2^b$ for integers $a$ and $b\geq0$). The result extends to other non-dyadic Bernoulli parameters and to coordinates that are Boolean functions of boundedly many bounded-degree polynomials. We also give a uniform deterministic hierarchy between adjacent degrees. Appending the outputs of disjoint AND gates on $d+1$ inputs to uniform seed bits yields flat degree-$(d+1)$ target distributions of entropy $k$ with overlap $\exp(-Ω_d(\min\{k,N-k\}))$ against every degree-$d$ source, for $\min\{k,N-k\}\geq2(d+1)$. This entropy dependence is optimal up to constants in the exponent among flat target distributions for fixed $d$. The construction has locality $d+1$ and uses $O(N)$ field operations to sample. At $k=\lfloor N/2\rfloor$, it handles $d\leq(1-\varepsilon)\log_2N/3$ with overlap $\exp(-N^{\varepsilon-o(1)})$ for fixed $0<\varepsilon<1$. The proof combines monotonicity of Gowers uniformity norms, pairwise independence of points in a random affine cube, and relative entropy.

0.53

Almost every Boolean function has central threshold degree

cs.DM cs.ITmath.CO ·2026-10-10 ·Martin Anthony
theory similarity 0.64
Abstract · 12 pages. Revised abstract and exposition to clarify the conjectures resolved; references updated. Results and proofs unchanged

The polynomial threshold degree (or threshold degree) of a Boolean function is the least degree of a real polynomial whose sign represents it. We prove that almost every Boolean function has polynomial threshold degree among the central one or two integers. More precisely, a uniformly chosen Boolean function on $n$ variables has threshold degree either $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$, except with probability at most $\exp(-c2^{n/2}/n)$, for an absolute constant $c>0$ and all sufficiently large $n$. The paper proves a 1991 conjecture of Aspnes, Beigel, Furst and Rudich. It also proves a 1991 conjecture of Wang and Williams for even $n$ and its main concentration assertion for odd $n$. A parity example gives a lower bound on the exceptional probability whose exponent differs from ours by a factor of order $n$. The proof relates polynomial sign representation to recovery of Reed--Muller codes from random erasures, and combines sharp-threshold estimates with bounds on generalized Hamming weights and minimum distance.

0.36

Majority and Torus Polynomials: Bounded-Lift Lower Bounds and Explicit Constructions

cs.CC ·2026-10-13 ·Saint Wesonga
similarity 0.62
Abstract

Bhrushundi et al. (2019) introduced torus polynomial approximation as an approach to separating Majority from $ACC^0$. In this model, approximation is measured modulo integers. Krishan and Vishwanathan (2026) developed a duality framework for lower bounds and posed five open problems. We resolve two of these, concerning integer lifts and explicit polynomial approximations. An integer lift records the integer shifts that turn a torus approximation into an ordinary real approximation. We show that a degree-d torus polynomial approximating Majority with error at most 1/8 and lift contained in an interval of width $B$ must satisfy $d(B + 1) = Ω(n)$. This rules out low-degree approximating polynomials with lifts in {-1, 0, 1}, answering their Open Problem 2. We also answer Open Problem 5 by giving, for every Boolean function on $n \geq 1$ variables, an explicit torus polynomial approximation of degree at most $n - 1$. Its error is optimal: zero when the accepting set has even cardinality and $2^{-n-1}$ otherwise. The results presented were discovered and formalized in Lean using GPT-6 Astra.

0.31

Exponential Correlation Bounds for Polynomials

cs.CC ·2026-09-23 ·Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal +1 more
publishedtheoryhighly cited similarity 0.62
Abstract · 26 pages. Revision: Generalized the main results to all fields, added new applications and improved some existing ones, and expanded the exp…

We prove that the XOR of $k$ majorities on disjoint blocks of $\ell$ bits has correlation at most $(4d/\sqrt{\ell})^k$ with every Boolean-valued degree-$d$ polynomial over an arbitrary field. By known techniques, we obtain explicit pseudorandom generators that fool such polynomials on $n$ Boolean inputs with seed length $d^2\cdot\polylog(n/\varepsilon)$. The correlation and the generator extend to small $\mathsf{AC}^0[q]$ circuits, for every fixed prime power $q$. These results resolve several long-standing questions in circuit complexity and pseudorandomness.

0.61