What was already known
Earlier general influence bounds could decay exponentially with the degree. Lovett and Zhang gave a route through fractional certificates that depended on a further conjectured inequality. Blanc, Docter, Strassle and Tan obtained the quantum simulation consequence for a fixed number of rounds of parallel queries.
AI involvement
PSI credits a non-public Anthropic model with the determinant argument, the inequality comparing pairs of inputs, the first complete proof and two improvements to the bound. David Turturean developed and ran the research system, scoped the problem and reviewed and edited the manuscript. The proof builds on Lovett and Zhang’s fractional-certificate approach and Reimer’s Butterfly Lemma.
- Turturean’s proof of the Aaronson–Ambainis conjectureAcknowledgments and Appendix A
- PSI’s announcement and account of the AI workResearch workflow
- Turturean’s arXiv manuscript
Importance
This proves the general influence conjecture. By Aaronson and Ambainis’s reduction, a classical algorithm can approximate a quantum query algorithm’s acceptance probability on most uniformly random inputs. For fixed accuracy and exceptional fraction, the classical query count grows polynomially in the quantum query count.
Technical verification
PSI reports kernel replay in Lean 4 and sandboxed checks with Lean and Nanoda through Comparator. The checks cover the unconditional influence theorem, including the original normalization, and use only Lean’s three standard axioms. PSI also reports a manuscript proof audit by its advisor Jim Halverson.
Formal checking
PSI reports kernel replay and sandboxed comparison with a separate Mathlib-only statement.
- Checker
- Lean 4 kernel and Nanoda through Comparator
- Scope
- Unconditional influence bounds in Theorem 1.1 and Corollary 1.2, including the original conjecture in its 0/1 normalization
- Basis
- Reported by the linked checker
- Lean statement of the original conjecturePrintedConjecture
- Lean and Nanoda verification reportKernel replay, Comparator, and archived logs
- A short proof of the Aaronson-Ambainis Conjecture via the completion framework
- Proof of the Aaronson–Ambainis Conjecture: An Exposition
Human understanding
Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan explain how fractional certificates lead to an influential bit through a weighted inequality on pairs of inputs. They trace that inequality to a routing lemma on the Boolean cube and explain the determinant identity that proves it. Their exposition uses weaker exponents to make the argument easier to follow. They report using public Anthropic models while preparing it.
Human follow-up work
A short proof of the Aaronson-Ambainis Conjecture via the completion framework
9 Nov 2026Rederives the Boolean case of Turturean’s certificate inequality, then uses it to complete partial Boolean functions on most of their domain. The authors obtain a deterministic query bound polynomial in the quantum query count, inverse domain density and inverse error. They disclose using ChatGPT while exploring the completion route.
Thomas Huffstutler, David Miloschewsky and Supartha Podder.Proof of the Aaronson–Ambainis Conjecture: An Exposition
10 Nov 2026Explains the certificate-influence inequality, the weighted all-pairs argument, the routing lemma and the determinant proof. The exposition keeps the main ideas and gives weaker exponents than Turturean’s original. The authors disclose using public Anthropic models in preparing the exposition.
Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan.
Correction and publication history
Blanc, Docter, Strassle and Tan explain the main steps of Turturean’s proof, including the determinant argument.
Read this published revisionHuffstutler, Miloschewsky and Podder give a self-contained derivation of a special case of Turturean’s certificate inequality.
Read this published revisionAdd the arXiv copy of the original paper without a research notification.
Read this published revisionNew unconditional proof of the general Aaronson–Ambainis conjecture, with central AI work and source-reported formal checks.
Read this published revision