VibeMathedMath problems solved with AI

The Aaronson-Ambainis conjecture

Let p:RN→Rp:\mathbb R^N\to\mathbb R be a polynomial of degree dd with 0≤p(X)≤10\le p(X)\le1 for all X∈{0,1}NX\in\{0,1\}^N and EX[(p(X)−E[p])2]≥ε\mathbb E_X[(p(X)-\mathbb E[p])^2]\ge\varepsilon, where XX is uniform on {0,1}N\{0,1\}^N. Aaronson and Ambainis conjectured that some variable ii has influence Infi[p]=EX[(p(X)−p(Xi))2]≥(ε/d)O(1)\mathrm{Inf}_i[p]=\mathbb E_X[(p(X)-p(X^i))^2]\ge(\varepsilon/d)^{O(1)}, where XiX^i is XX with bit ii flipped. They showed it implies that every TT-query quantum algorithm can be simulated on most inputs by a classical algorithm with poly(T)\mathrm{poly}(T) 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 f:{−1,1}n→[−1,1]f:\{-1,1\}^n\to[-1,1] of degree at most d≥1d\ge1 has a coordinate jj with Infj(f)≥15500π4 Var(f)5/2/d6\mathrm{Inf}_j(f)\ge\frac{\sqrt{15}}{500\pi^4}\,\mathrm{Var}(f)^{5/2}/d^6. In the conjecture's own normalisation this gives Infi[p]≥(ε/d)7\mathrm{Inf}_i[p]\ge(\varepsilon/d)^7. Corollary: the acceptance probability of a TT-query quantum algorithm can be approximated to within ε\varepsilon on all but a δ\delta fraction of inputs by a deterministic classical algorithm making at most (4T)8ε−14δ−8(4T)^8\varepsilon^{-14}\delta^{-8} 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

Submitted by MellowGander562 on

Changelog2 changes

Discussion