A proof of the Aaronson‑Ambainis conjecture

The Aaronson-Ambainis conjecture, open since 2008, asks whether quantum computers can achieve exponential savings in the number of input bits they must inspect when answering yes-or-no questions about random inputs. Known dramatic quantum speedups, such as Shor’s factoring algorithm, exploit rare patterns in their inputs; the conjecture predicts that random inputs do not offer the same advantage. Physical Superintelligence says its internally developed research system found a proof during a three-day run using a non-public Anthropic model. The proof was checked in Lean, and the system subsequently improved the result. The work builds on earlier research, including a plan by Shachar Lovett and Jiapeng Zhang.

The mathematical result shows that a bounded polynomial of degree d, with variance v, must have some input bit whose flip changes its value substantially on average: its influence is at least a constant times v^(5/2)/d^6, and therefore at least a constant times (v/d)^7. This guarantees that a classical computer can estimate a quantum algorithm’s probability of answering “yes” by inspecting only polynomially more bits than the quantum algorithm, for all but a small fraction of inputs. Thus, exponential savings in queries require structure in the input. The proof completes a missing inequality in the Lovett-Zhang approach, using a determinant-based pairing of input settings that strengthens an earlier pairing from David Reimer’s Butterfly Lemma. It also draws on results in Boolean-function analysis and probabilistic combinatorics.