AI-Assisted Proof Settles Longstanding Question About Quantum Speedups

Insider Brief

• A proof of the Aaronson-Ambainis conjecture establishes that exponential quantum advantages in input reads require structure when answering yes-or-no questions on most randomly generated inputs.
• PSI said its research system used a non-public Anthropic model to find the proof, which was checked in the Lean proof assistant and reviewed by researchers.
• The theorem limits data reads rather than total computing time, leaving room for practical quantum advantages and further work to strengthen its mathematical bounds.

A mathematical proof has resolved a conjecture open since 2008 about when quantum computers can achieve enormous advantages over conventional machines, establishing a limit on their ability to outperform classical algorithms on unstructured inputs.

The result proves the Aaronson-Ambainis conjecture, which connects a question about mathematical functions to whether dramatic speedups require special structure in the problems being solved, a central issue in quantum computing, namely.

For quantum computing, the practical implication is a clearer direction for quantum algorithm research toward problems whose mathematical or physical structure offers an advantage. The theorem strengthens the theoretical basis for that approach, although it does not ultimately determine which applications will deliver useful speedups.