A proof of the Aaronson–Ambainis conjecture

Get email updates

David Turturean

Let p be a real polynomial of total degree at most d that takes values in [0,1][0,1] on {0,1}n\{0,1\}^n. If p has variance at least ε>0\varepsilon>0 under uniform input, some bit has influence at least 815125π4ε5/2d6\frac{8\sqrt{15}}{125\pi^4}\frac{\varepsilon^{5/2}}{d^6}, which implies the simpler bound (ε/d)7(\varepsilon/d)^7. A bit’s influence is the average squared change in p when that bit is flipped.

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 AI-led

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.

Importance Major

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 Formal (Lean 4 and Nanoda + human)

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

Human understanding Explained

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.

Correction and publication history

2026-11-10 · amendment

Blanc, Docter, Strassle and Tan explain the main steps of Turturean’s proof, including the determinant argument.

Read this published revision
2026-11-10 · amendment

Huffstutler, Miloschewsky and Podder give a self-contained derivation of a special case of Turturean’s certificate inequality.

Read this published revision
2026-11-07 · publication

New unconditional proof of the general Aaronson–Ambainis conjecture, with central AI work and source-reported formal checks.

Read this published revision