Aaronson–Ambainis conjecture
Take a real polynomial of degree at most d whose values lie between 0 and 1 on all bit strings of a fixed length. Draw a string uniformly at random. The influence of a bit is the average squared change in the polynomial’s value when you flip that bit. If the variance is at least , must some bit have influence at least a fixed power of , regardless of the string length?
Why it matters and what counts as progress
Why it matters: A quantum query algorithm’s acceptance probability is a bounded polynomial. A sufficiently influential bit gives a classical simulator a bit to read. The conjecture guarantees that the simulator can estimate the acceptance probability on most uniform inputs with a polynomial number of queries.
What counts as progress: Prove an influence bound for all bounded polynomials or for a precisely defined class. Improve the bound’s dependence on degree or variance, or sharpen the resulting classical query guarantee. State the input distribution and how influence is measured.
How the problem developed
- 2008 · Initial conjecture [1]
Scott Aaronson Raised the influence question in a lecture on open problems in quantum computing.
- 2009 · Reduction to polynomial influences [5]
Scott Aaronson and Andris Ambainis Stated the influence conjecture and showed that it would give a polynomial-query classical simulation of quantum acceptance probabilities on most uniform inputs.
- 1 Feb 2023 · Fractional certificates [6]
Shachar Lovett and Jiapeng Zhang Proved bounds on fractional certificate complexity for bounded polynomials and reduced the influence conjecture to a further proposed concentration inequality.
- 19 Aug 2026 · Simulation for fixed query depth [7]
Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan Proved the classical query simulation guarantee for quantum algorithms with a fixed number of rounds of parallel queries.
David Turturean at PSI with a non-public Anthropic model Proved the conjecture for all bounded real polynomials on the Boolean cube. The proof uses a determinant argument to obtain an inequality comparing pairs of inputs. PSI released the Lean formalization with its verification report.
- 9 Nov 2026 · Short completion proof [8]
Thomas Huffstutler, David Miloschewsky and Supartha Podder Reproved the Boolean special case of Turturean’s certificate inequality and used it to bound the queries needed to complete partial Boolean functions.
- 10 Nov 2026 · Exposition of Turturean’s proof [9]
Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan Explained the certificate, all-pairs, routing and determinant arguments, with weaker exponents in the exposition.
AI contribution
A proof of the Aaronson–Ambainis conjecture
Let p be a real polynomial of total degree at most d that takes values in on . If p has variance at least under uniform input, some bit has influence at least , which implies the simpler bound . A bit’s influence is the average squared change in p when that bit is flipped.
Sources
- Turturean’s proof of the Aaronson–Ambainis conjecture
- PSI’s announcement and account of the AI work
- Lean statement of the original conjecture
- Lean and Nanoda verification report
- The Need for Structure in Quantum Speedups
- Fractional Certificates for Bounded Functions
- Quantum Speedups Require Structure or Depth
- A short proof of the Aaronson-Ambainis Conjecture via the completion framework
- Proof of the Aaronson–Ambainis Conjecture: An Exposition
- Turturean’s arXiv manuscript
Publication history
Daily emails by default, only when there’s an update.