A proof of the Aaronson–Ambainis conjecture

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.

You are reading an earlier published revision. Read the current record.

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.

This revision has no four-dimension assessment. Read the criteria.

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.

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

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

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