Major quantum computing conjecture solved in three days after 18 years of uncertainty

An 18-year-old mathematical problem concerning the limits of quantum computing may finally have been solved in just three days. Physics research company PSI claims to have cracked the long-standing Aaronson-Ambainis conjecture, potentially shedding new light on when quantum computers can outperform conventional machines.

The company said its system completed the proof of the Aaronson-Ambainis conjecture in three days. The problem, first proposed in 2008, concerns the conditions under which quantum computers can achieve an exponential speed advantage over conventional computers.

PSI said its research system used a non-public model from Anthropic, running on the company’s own infrastructure. The system produced a mathematical proof that was accepted by Lean, a proof-assistant software used to check the logical correctness of formal mathematical arguments.

The company said the system subsequently improved the proof twice, with Lean accepting the final version as well.

However, the result has not yet undergone full independent academic review. While researchers at Stanford University have examined aspects of the work and provided feedback, wider scrutiny will be important in establishing whether the proof resolves the original conjecture.

A long-standing quantum question

The Aaronson-Ambainis conjecture addresses how much information a classical computer needs to simulate certain quantum algorithms.

More specifically, it concerns whether quantum algorithms with a particular mathematical structure can be efficiently approximated by classical computers. If the conjecture holds, classical computers could simulate a broad class of quantum algorithms on randomly selected inputs with only polynomial overhead. The distinction matters because polynomial and exponential growth can produce vastly different computing demands as the size of a problem increases.

That would help explain why some quantum algorithms may not deliver an exponential advantage over classical computing, even if quantum hardware can process information in fundamentally different ways.

The result does not mean quantum computers have no advantage over classical machines. Algorithms designed for particular problems, including Shor’s algorithm for factoring large numbers, are not ruled out by the conjecture.

Instead, the conjecture addresses a specific class of quantum computations and the conditions under which their apparent advantage can be reproduced classically.

Independent scrutiny remains

PSI said David Turturean led the work, developing the research system, defining the problem and running the process. He also reviewed the resulting draft and was responsible for the paper’s correctness.

The company said Jim Halverson audited the proof, while Phiala Shanahan provided comments on its Lean formalisation.

Researchers at Stanford, including Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan, have also been examining the result. The group previously proved a special case of the conjecturein August 2026 and is preparing a shorter exposition of PSI’s full proof for other experts.

Their involvement is significant because formal verification and independent mathematicalreview serve different purposes. Lean can check whether a formal proof follows logically from its stated assumptions, but researchers must also assess whether the formalized statement accurately captures the original conjecture.

PSI, which launched publicly in September 2026, describes itself as a physics research company building automatedsystems for scientific discovery. Its announcement marks a potentially important milestone, but the claim will need to withstand broader expert review before it can be treated as a settled result.

Source: https://interestingengineering.com/culture/psi-research-system-aaronson-ambainis-quantum-conjecture