A proof of the Aaronson-Ambainis conjecture

David Turturean

AI summary · arXiv: 2611.09773v1 · cs.CC

A proof of the Aaronson-Ambainis conjecture

David Turturean

Original paper Submitted to arXiv on 06 Nov. 2026 60 pages. Lean formalization and reproducibility materials: https://github.com/physical-superintelligence/aaronson-ambainis License: NONEXCLUSIVE-DISTRIB 1.0 Also in: fr

How to read this summary? Illustrated guide

The essentials

The paper proves the Aaronson–Ambainis conjecture by establishing a lower bound on the influence of some variable in every bounded low-degree function on the discrete cube.

Based on the abstract only: check the details in the original paper.

Question

Can every bounded low-degree function on the discrete cube be shown to have at least one influential variable? The question matters because the conjecture links such functions to classical approximation of quantum query algorithms.

Method

The paper gives an elementary proof for functions from {-1,1}^n to [-1,1] with degree at most d ≥ 1. It establishes an absolute-constant lower bound of c Var(f)^(5/2)/d^6 for the influence of some variable; in the original formulation, variance at least ε yields influence at least (ε/d)^7.

Findings

Result Every function from {-1,1}^n to [-1,1] of degree at most d ≥ 1 has a variable with influence at least c Var(f)^(5/2)/d^6, for an absolute constant c > 0.
See the passage in the paper
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.
Result In the original formulation, a polynomial with values in [0,1], degree at most d, and variance at least ε has a variable with influence at least (ε/d)^7.
See the passage in the paper
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}$.
Authors’ interpretation The authors describe the proof as elementary, with steps inspired by earlier work.
See the passage in the paper
The proof is elementary, with steps inspired by works of others.
Authors’ interpretation The authors conclude that superpolynomial quantum speedups in the query model require structure in the inputs, such as a promise.
See the passage in the paper
Thus, as Aaronson and Ambainis anticipated, superpolynomial quantum speedups in the query model require structure, such as a promise on the inputs.

Limitations

The abstract does not state a limitation; the result is scoped to bounded low-degree functions on the discrete cube.

Why it matters

The proof resolves the Aaronson–Ambainis conjecture and, as the authors argue, supports the implication that superpolynomial quantum query speedups require structured or promised inputs.

Written by AI from the paper. Passages are checked word for word against the text we analysed; the rest may contain errors.

AI-generated keywords: Aaronson–Ambainis conjecture Boolean functions variable influence quantum query complexity low-degree polynomials

Read further

Comprehensive Summary
Layman's Summary
Blog article
Original abstract

The paper addresses the Aaronson–Ambainis conjecture, which asks whether every bounded, low-degree polynomial on the discrete cube has a variable with substantial influence. A variable’s influence measures how much changing that coordinate can affect the function. The conjecture is significant in quantum query complexity: Aaronson and Ambainis showed that it would imply that, on most inputs, the acceptance probability of any quantum algorithm making $T$ queries can be approximated by a classical algorithm using a number of queries polynomial in $T$. The author claims to prove the conjecture using an elementary argument inspired by earlier work. However, only the title, author information, and abstract are available; the full paper is inaccessible under its license. As a result, the proof’s steps, technical assumptions beyond those stated in the abstract, and relationship to earlier approaches cannot be summarized or independently assessed. The abstract’s main quantitative result is that for every function from the $n$-dimensional discrete cube to $[-1,1]$ with degree at most $d$, where $d\geq 1$, some variable has influence at least $c\,\mathrm{Var}(f)^{5/2}/d^6$, where $c$ is an absolute positive constant. This bound links the existence of an influential variable to the function’s variance and degree: greater variance strengthens the bound, while higher degree weakens it. The abstract also states a consequence in the conjecture’s original formulation. If a polynomial of degree at most $d$ takes values in $[0,1]$ on the Boolean cube and has variance at least $\epsilon$, then some variable has influence at least $(\epsilon/d)^7$. The author presents this polynomial lower bound as resolving the conjecture. More broadly, the result supports the view that superpolynomial quantum speedups in the query model require structure in the input problem, such as a promise restricting the allowed inputs. This implication relies on the connection established by Aaronson and Ambainis; it does not, on its own, show that every quantum algorithm has an efficient classical simulation on every input. The available abstract does not give the proof, the value of $c$, detailed definitions or conventions for influence and variance, or the derivation of the bound in the original formulation. It therefore supports reporting the theorem and its stated implications, but not evaluating the proof’s correctness, novelty, tightness, or practical significance beyond the author’s claims.

A New Proof of the Aaronson–Ambainis Conjecture—And What We Can Verify

How much can one bit of an input matter to a function? In theoretical computer science, this question is captured by the idea of a variable’s influence: a measure of how much changing one coordinate can affect the function’s value. A research paper by David Turturean, titled “A proof of the Aaronson-Ambainis conjecture,” claims a significant result about influential variables in low-degree functions on the Boolean cube.

The claim matters beyond the study of Boolean functions. The Aaronson–Ambainis conjecture is connected to quantum query complexity, where it would imply that many quantum computations can be approximated by classical algorithms on most inputs. The paper’s abstract presents a proof of the conjecture using an elementary argument inspired by earlier work. But there is an important limitation: the full paper is inaccessible under its license. The available information therefore supports describing the stated theorem and its claimed consequences, but not evaluating the proof itself.

The conjecture in plain language

Consider a function on the discrete cube, whose inputs are strings of bits. A polynomial can represent such a function, and its degree describes, roughly, how complicated its dependence on the input bits can be. The conjecture asks whether every bounded, low-degree polynomial must have at least one variable with substantial influence.

The intuition is that a function cannot be both meaningfully variable overall and spread its dependence so thinly across all coordinates that none of them matters much. The conjecture gives this intuition a quantitative form: the degree and the function’s variation should force a lower bound on the influence of some individual variable.

The theorem reported in the abstract

Turturean’s abstract states that for every function from the n-dimensional discrete cube to [-1,1] with degree at most d, where d is at least 1, some variable has influence at least:

c Var(f)5/2/d6

Here, c is an absolute positive constant, and Var(f) denotes the function’s variance. The bound links three features: the function’s variance, its degree, and the influence of its most influential variable. Greater variance raises the stated lower bound, while greater degree weakens it.

The abstract also gives a consequence in the conjecture’s original formulation. If a polynomial has degree at most d, takes values in [0,1] on the Boolean cube, and has variance at least ε, then some variable has influence at least (ε/d)7. The author presents this lower bound as resolving the conjecture.

Why the result matters for quantum computing

The conjecture is important partly because of a connection to quantum query complexity. Aaronson and Ambainis showed that the conjecture would imply that, on most inputs, the acceptance probability of any quantum algorithm making T queries can be approximated by a classical algorithm using a number of queries polynomial in T.

If Turturean’s claimed proof establishes the conjecture, it therefore supports a broad conclusion: in the query model, large quantum advantages may depend on special structure in the input problem, such as a promise that rules out many possible inputs. This should not be mistaken for a claim that every quantum algorithm can be efficiently simulated classically on every input. The stated implication concerns approximation on most inputs and rests on the connection established by Aaronson and Ambainis.

What the available information cannot tell us

The abstract provides a striking theorem, but it is not enough to independently assess how the result is obtained. The proof’s steps are unavailable, as are details that could matter when interpreting or checking the argument. In particular, the abstract does not provide the value of c, the detailed conventions for influence and variance, or the derivation of the bound in the [0,1]-valued formulation.

That limitation also prevents a careful comparison with earlier approaches. The author describes the proof as elementary and inspired by prior work, but without the full text it is not possible to assess what makes the argument elementary, how it relates to previous methods, or whether the result is tight. The abstract supports reporting the claim; it does not establish, for a reader who cannot inspect the paper, whether the proof is correct or how novel its techniques are.

A notable claim, with a clear caveat

The reported bounds offer a concrete relationship between variance, degree, and influence, and the claimed resolution has implications for how quantum and classical algorithms compare in query problems. The broader message is that influential coordinates may be unavoidable in sufficiently variable low-degree functions.

For now, though, the appropriate conclusion is measured: Turturean’s abstract announces a proof of the Aaronson–Ambainis conjecture and states its quantitative consequences. Understanding and independently judging the proof requires access to the full argument.

Created on 09 Nov. 2026

Was this synthesis useful?

Score: 0

Ask questions about this paper to our AI assistant

How to chat with this paper? Illustrated guide

Compare with the PDF

You can also chat with multiple papers at once here.

AI assistant instructions?

Tools for this paper

Explain it differently 1 free rewrite left today

Save to a collection Group papers in collections to compare them, chat with them and export them. Continue with Google Create a free account Log in

Export BibTeX · RIS (Zotero, Mendeley, EndNote) · Obsidian (Markdown) · Notion (Markdown)

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero

Citation alerts Citation alerts guide

Who works on it? The people and institutions who publish on its topic

Weekly letter Presented in "Computing beyond AI this week" of 9 November 2026. Computing beyond AI this week: What noise reveals, and what guarantees conceal

Journal club Premium+ Slides to present it Propose for the journal club

Versions What changed between versions

Talk about it in public Premium+ Press kit: release, questions, hype check Press kit guide

Papers around this one

See them on a map

Ranked by how close their title and abstract are to this paper’s. Select some to read them together.

Closest papers

Close Broader context
An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
Matthew 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…
Close Broader context
Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture
Matthew 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,…
Related Broader context
Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth
Murphy 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 …
Related Broader context
Quantum query complexity of edge connectivity
Simon 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…
Related Broader context
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.
Related Broader context
A doubly composite Chernoff-Stein lemma and its applications
Ludovico 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…
Related Broader context
On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten-Stigum
Ferenc 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.
Related Broader context
Adversarial Wronskians: A proof of the Kung--Traub conjecture
Matthew 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.

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.

A proof of the Aaronson-Ambainis conjecture

The essentials

Question

Method

Findings

Limitations

Why it matters

Read further

Definitions

A New Proof of the Aaronson–Ambainis Conjecture—And What We Can Verify

The conjecture in plain language

The theorem reported in the abstract

Why the result matters for quantum computing

What the available information cannot tell us

A notable claim, with a clear caveat

Ask questions about this paper to our AI assistant

Tools for this paper

Advanced tools Premium

Papers around this one

Closest papers

Go further

Cite this paper (BibTeX)