Proof of the Aaronson-Ambainis conjecture
Physical Superintelligence (PSI) says its AI system, running a non-public Anthropic model, proved the Aaronson-Ambainis conjecture, a quantum complexity question open since 2008.
PSI announced on X and its site that the conjecture is now a theorem. The conjecture, from Scott Aaronson and Andris Ambainis, bears on how much speedup quantum algorithms can have over classical ones. PSI says its internal research system had a complete proof on the third day of a run on its own infrastructure, and that the Lean proof assistant accepted it. The system then improved the result twice, and Lean accepted the final version. PSI published a paper along with the proofs and code. The proof builds on ideas of Shachar Lovett and Jiapeng Zhang, David Reimer and others.
- Date
- Friday 6 November 2026
- Lab
- PSI
- Kind
- paper
- Access
- paper only
This is a company claim. PSI's page says Lean checked the proof, but no independent peer review is reported yet.
Sources
This record was checked and corrected against its sources on 6 November 2026. How we check