A proof of the Aaronson-Ambainis conjecture
Authors: David Turturean
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.
The papers around it, by date and closeness
Higher is closer to this paper; left is older. Lines join papers close to each other: groups of lines are sub-topics. Select a point to see why it is there. Back to the summary of this paper
Papers around this one
Ranked by how close their title and abstract are to this paper’s. Select some to read them together.
Closest papers
-
An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphsMatthew Kwan, Lisa Sauermann · 2019 · Combinatorics · cited 7 times · AI summary available
The quadratic Littlewood-Offord paper studies concentration and algebraic structure of quadratic polynomials, rather than influential variables of bounded low-degree functions.
Abstract
Consider a quadratic polynomial $f\left(\xi_{1},\dots,\xi_{n}\right)$ of independent Bernoulli random variables. What can be said about the concentration of $f$ on any single value? This generalises the classical Littlewood--Offord problem, which asks the same question for linear polynomials. As in the linear case, it is known that the point probabilities of $f$ can be as large as about $1/\sqrt{n}$, but still poorly understood is the "inverse" question of characterising the algebraic and arithmetic features $f$ must have if it has point probabilities comparable to this bound. In this paper we prove some results of an algebraic flavour, showing that if $f$ has point probabilities much larger…
-
Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjectureMatthew Kwan, Ashwin Sah, Lisa Sauermann et al. · 2022 · Combinatorics · cited 12 times · AI summary available
The Ramsey-graphs paper studies edge-count concentration using tools for low-degree polynomials, not the influence lower bound for bounded functions.
Abstract
An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $C\log_2 n$ (i.e., if it has near-optimal Ramsey behavior). In this paper, we study edge-statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a $C$-Ramsey graph. This brings together two ongoing lines of research: the study of "random-like" properties of Ramsey graphs and the study of small-ball probabilities for low-degree polynomials of independent random variables. The proof proceeds via an "additive structure" dichotomy on the degree sequence, and involves a wide range of different tools from Fourier analysis,…
-
Optimizing QAOA: Success Probability and Runtime Dependence on Circuit DepthMurphy Yuezhen Niu, Sirui Lu, Isaac L. Chuang · 2019 · Quantum Physics · preprint, not peer reviewed · cited 48 times · Not summarized yet
The QAOA paper analyzes success probability for state transfer, whereas this paper concerns influences of low-degree functions and their implications for quantum query algorithms.
Abstract
The quantum approximate optimization algorithm~(QAOA) first proposed by Farhi et al. promises near-term applications based on its simplicity, universality, and provable optimality. A depth-p QAOA consists of p interleaved unitary transformations induced by two mutually non-commuting Hamiltonians. A long-standing question concerning the performance of QAOA is the dependence of its success probability as a function of circuit depth p. We make initial progress by analyzing the success probability of QAOA for realizing state transfer in a one-dimensional qubit chain using two-qubit XY Hamiltonians and single-qubit Hamiltonians. We provide analytic state transfer success probability dependencies …
-
Quantum query complexity of edge connectivitySimon Apers, Troy Lee · 2020 · Quantum Physics · cited 11 times · AI summary available
The edge-connectivity paper bounds quantum query complexity for graph connectivity, while this paper studies when low-degree functions have influential variables.
Abstract
The edge connectivity of a simple graph is the least number of edges whose removal disconnects the graph. We study the quantum query complexity of computing the edge connectivity of a simple graph with $n$ vertices and $m$ edges in both the adjacency matrix and adjacency array models. For classical randomized algorithms, $\Omega(n^2)$ and $\Omega(m)$ lower bounds are known for these models, respectively, showing that the trivial algorithm is optimal in terms of query complexity for both cases. In contrast, we show upper bounds of $\tilde O(n^{3/2})$ and $\tilde O(\sqrt{mn})$ on the quantum query complexity of computing edge connectivity in the adjacency matrix and adjacency array models, res…
-
Are Quantum States Exponentially Long Vectors?Scott Aaronson · 2005 · Quantum Physics · preprint, not peer reviewed · cited 11 times · AI summary available
The essay argues against Goldreich’s views on quantum computing, while this paper proves a structural conjecture with consequences for quantum query algorithms.
Abstract
I'm grateful to Oded Goldreich for inviting me to the 2005 Oberwolfach Meeting on Complexity Theory. In this extended abstract, which is based on a talk that I gave there, I demonstrate that gratitude by explaining why Goldreich's views about quantum computing are wrong.
-
A doubly composite Chernoff-Stein lemma and its applicationsLudovico Lami · 2025 · Information Theory · preprint, not peer reviewed · cited 6 times · Not summarized yet
The Chernoff-Stein paper studies hypothesis testing for correlated distributions, not low-degree functions on the discrete cube.
Abstract
Given a sequence of random variables $X^n=X_1,\ldots, X_n$, discriminating between two hypotheses on the underlying probability distribution is a key task in statistics and information theory. Of interest here is the Stein exponent, i.e. the largest rate of decay (in $n$) of the type II error probability for a vanishingly small type I error probability. When the hypotheses are simple and i.i.d., the Chernoff-Stein lemma states that this is given by the relative entropy between the single-copy probability distributions. Generalisations of this result exist in the case of composite hypotheses, but mostly to settings where the probability distribution of $X^n$ is not genuinely correlated, but r…
-
On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-StigumFerenc Bencs, Brice Huang, Daniel Z. Lee et al. · 2026 · Data Structures and Algorithms · AI summary available
The Ising-model paper develops an algorithm for partition-function estimation on random regular graphs, unlike this paper’s influence bound.
In short
The paper proves zero-freeness and deterministic polynomial-time partition-function approximation for the antiferromagnetic Ising model on random regular graphs at every fixed inverse temperature below Kesten–Stigum.
-
Adversarial Wronskians: A proof of the Kung--Traub conjectureMatthew J. Colbrook · 2026 · Numerical Analysis · AI summary available
The Kung–Traub paper proves a limit on root-finding methods using polynomial Wronskians, rather than studying influences on the discrete cube.
In short
The paper proves that deterministic stationary root-finding without memory, using at most n scalar evaluations per iteration, has universal local order at most 2^(n−1), and that this bound is sharp.
Go further
How are these papers found?
We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.
Updated on 9 November 2026.