The AI research firm Physical Superintelligence used an unreleased model from Anthropic to identify a proof for a long-standing problem in quantum complexity. The research system reached a complete proof of the Aaronson-Ambainis conjecture within three days of operation, and the firm subsequently verified the results using the Lean theorem prover.
The finding establishes that quantum computers cannot achieve exponential query speedups on almost all random yes/no inputs, defining the limits of when quantum machines can realistically outperform classical computers. The conjecture had remained an open problem in the field of quantum computing since 2008.
