AI System Solves 18-Year Quantum Computing Conjecture

Physical Superintelligence has announced that an internal AI research system proved the Aaronson-Ambainis conjecture, a fundamental question in quantum computing that remained open since 2008. The system, running a non-public Anthropic model, completed the proof in three days with every step verified by the Lean proof assistant. The result settles whether quantum computers can achieve exponential speedups over classical computers on random inputs.

The Fundamental Question Resolved

The Aaronson-Ambainis conjecture addressed a core mystery in quantum computing: whether quantum computers can be exponentially faster than classical computers when processing random data without special structure. Scott Aaronson and Andris Ambainis posed the conjecture in 2008, framing the question through pure mathematics about polynomial functions. Researchers have considered it among the central open problems in quantum complexity theory for nearly two decades.

The proven theorem confirms that quantum computers cannot achieve exponential speedups on random inputs. Classical computers can predict quantum probabilities efficiently for all but a small fraction of inputs, with the number of operations growing polynomially rather than exponentially. This fundamentally limits the scope of quantum advantage to problems with specific structural properties.

How the AI System Found the Proof

David Turturean, Member of Technical Staff at Physical Superintelligence, led the work by developing the research system, scoping the problem, and running it on the company's infrastructure. The system used instances of a non-public Anthropic model throughout the run. Officially launched on November 6, 2026, the proof became complete during the third day of operation, with Lean accepting every step.

The system then continued working on related problems and refined the result twice before producing the final version. Jim Halverson, an advisor to PSI, audited the proof for correctness. Phiala Shanahan, also an advisor, commented on the Lean formalization that ensures computer verification of each logical step.

Mathematical Breakthrough Details

The proof establishes that for any polynomial function representing a quantum computer's probability of returning a yes answer, at least one input bit must have substantial influence on the output. Specifically, the theorem shows that if a function varies at all, some bit's influence must be at least a fixed power of the variance divided by the polynomial's degree.

The mathematical approach follows a framework proposed by Shachar Lovett and Jiapeng Zhang, replacing a conjectured inequality with a new proven inequality. The proof uses a determinant-based pairing of input settings that improves on David Reimer's Butterfly Lemma. Key results from Avantika Agarwal, Shalev Ben-David, Raghav Kulkarni, Avishay Tal, and others contributed to the complete argument.

Validation and Impact

In August 2026, Guy Blanc, Jordan Docter, Carmen Strassle, and Li-Yang Tan from Stanford University had proven the conjecture's prediction for a special case involving quantum algorithms that read input in fixed parallel rounds. The Stanford team has since reviewed PSI's complete proof and is preparing a shorter exposition for experts. They characterized the result as resolving a decades-old conjecture with important implications for understanding which problems admit quantum speedups.

The proof builds on techniques from Boolean function analysis and probabilistic combinatorics. While quantum computing retains many mysteries, this result clarifies that dramatic speedups like Peter Shor's 1994 factoring algorithm require inputs with rare structural patterns rather than random data.

What This Means

The proven theorem fundamentally constrains the types of problems where quantum computers offer exponential advantages. Classical computers can efficiently simulate quantum behavior on random inputs, limiting quantum superiority to structured problems with hidden patterns. This clarity helps researchers focus quantum algorithm development on domains where exponential speedups remain possible, while confirming that quantum advantage requires more than raw computational parallelism.