The Aaronson-Ambainis conjecture
Let be a polynomial of degree with for all and , where is uniform on . Aaronson and Ambainis conjectured that some variable has influence , where is with bit flipped. They showed it implies that every -query quantum algorithm can be simulated on most inputs by a classical algorithm with queries, so exponential quantum speedups need structured inputs. Is the conjecture true?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Analysis of Boolean functions; quantum query complexity
- Posed by
- Scott Aaronson and Andris Ambainis
- Year posed
- 2009
- Years open
- 17y
- Solved
- 2026-11-06
- Model
- Non-public Anthropic model (PSI research harness)
- Vendor
- Anthropic
- Collaborators
- David Turturean
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Significance
- 45 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1: every of degree at most has a coordinate with . In the conjecture's own normalisation this gives . Corollary: the acceptance probability of a -query quantum algorithm can be approximated to within on all but a fraction of inputs by a deterministic classical algorithm making at most queries. The proof combines fractional certificates (after Lovett and Zhang), an all-pairs inequality related to Reimer's butterfly lemma, and a row bound for bounded polynomials.
What the AI did
From the paper's AI disclosure: the mathematical statements were produced by AI models. David Turturean scoped the problem and built and ran a research harness at Physical Superintelligence (PSI), in which instances of a non-public Anthropic model searched for existing ideas, proposed and tested new ones, and supervised the work. A model instance packaged the results into a first draft, which Turturean reviewed, edited and takes responsibility for. The Lean formalization was also produced by AI models.
Verification
No independent mathematician has checked this yet. Checked here on 15 November 2026: Conjecture 6 of arXiv:0911.0996v3 was read, and the Lean proposition PrintedConjecture in AaronsonAmbainis/Conjecture.lean (Mathlib imports only) was read line by line against it: total degree at most d, values in [0,1] on the 0/1 cube, variance as an average over the cube, influence as the average squared change when one bit is flipped, conclusion with exponent 7. It matches. The Lean library (public commit 2a6ceae) contains no sorry, axiom, native_decide or unsafe; the only sorry are in the Comparator challenge file and deliberate controls. The repository records a build, axiom report, kernel replay and Comparator run on a private staging repository; the public repository has no CI runs. Not rebuilt here.
Sources
- Lean proofLean formalization (four final theorems, Comparator configuration)
- Lean statementFormal statement: PrintedConjecture (Conjecture.lean)
- CodeGitHub (physical-superintelligence/aaronson-ambainis)
- Problem recordAaronson and Ambainis, The need for structure in quantum speedups (arXiv 0911.0996, Conjecture 6)
- OtherRandomized versus quantum query complexity of total functions (related OpenAI release entry)
Submitted by MellowGander562 on