Quantum technology

AI system claims proof of 18-year-old quantum computing conjecture

Research company PSI has published a machine-checkable proof of the Aaronson–Ambainis conjecture. The formal mathematics is available for inspection, but independent expert review remains pending.

Concept illustration of abstract binary inputs and logical connections symbolizing a machine-checked mathematical proof.
Concept illustration of mathematical complexity and formal proof checking, not a figure from PSI's proof.Illustration generated with OpenAI for Progress Radar

An artificial intelligence research system may have solved a mathematical problem that had remained open since 2008. On November 6, Physical Superintelligence (PSI) announced that its system had found a proof of the Aaronson–Ambainis conjecture, a question about the limits of how much faster quantum computers can be than classical computers.

PSI has released both a mathematical paper and a formal version of the proof written for Lean, software that checks mathematical deductions. That makes the result more inspectable than an ordinary AI-generated claim. The proof has not been peer reviewed, however, and it remains important to establish that the formal statement precisely matches the original conjecture.

What was the open problem?

Scott Aaronson and Andris Ambainis proposed the conjecture in 2008. It concerns polynomials describing how the probability of a yes answer from a quantum algorithm depends on the bits of its input. In simplified terms, the claim says that a bounded low-degree polynomial with appreciable variation must have at least one input bit that influences its value by a sufficiently large amount.

This has implications for query complexity: the number of times an algorithm needs to inspect its input. If the conjecture holds, a classical algorithm can approximate a quantum algorithm's answer on almost all uniformly random inputs using at most polynomially more queries. The result concerns that particular model and average-case setting, not a universal limit on quantum computation or total running time.

An AI research system and a checkable proof

PSI says its internal research system used instances of a non-public model from Anthropic. According to the company, the system obtained a complete proof on the third day of a run and then strengthened the mathematical bound twice.

The published formalization establishes a specific bound: for a polynomial of degree d and variance at least ε, some bit has influence at least a constant times ε to the power 5/2 divided by d to the sixth power. PSI shows that this also implies the weaker bound (ε/d) to the seventh power required by the original conjecture.

The Lean files and checking instructions are public. PSI reports verification with multiple proof checkers and no additional axioms or unfinished steps in the main result. These checks are documented by the project itself. We have not independently rerun them, and machine verification does not automatically cover every explanation or consequence in the accompanying paper.

What would it mean for quantum technology?

A valid proof would settle an important theoretical limit: for typical unstructured yes-or-no inputs, quantum algorithms cannot obtain an exponential query advantage under the relevant assumptions. It would not rule out major quantum advantages on problems with special structure, nor change existing algorithms such as Shor's factoring method.

PSI says Stanford researchers who previously proved a special case have read and commented on the proof and are preparing a shorter exposition for specialists. An independently published verification and conventional peer review have not yet been documented. The announcement is therefore both a potential breakthrough in quantum complexity and a test of how AI-produced mathematics should be scrutinized.

Sources

← Back to all news