The Pulse

PSI research system proves Aaronson-Ambainis conjecture

An internally developed research system found a proof of the Aaronson-Ambainis conjecture, which concerns quantum speedups on random inputs, PSI says. The proof shows that a quantum computer cannot save exponentially many looks on yes-or-no

AI.info Team · Written with AI · fact-checked · 2026-11-07

On November 6, 2026, PSI said its internally developed research system had found a proof of the Aaronson-Ambainis conjecture, which has been open since 2008 and concerns whether quantum computers can be exponentially faster on random inputs.

Scott Aaronson and Andris Ambainis stated the conjecture and showed that, if it is true, quantum computers are at most polynomially faster on random inputs. In 1994, Peter Shor found a quantum algorithm that factors large numbers far faster than any known method for ordinary computers.

System had a complete proof during the third day of the run

The internally developed research system found the proof in a run on its own infrastructure, using instances of a non-public Anthropic model, PSI says. The system had a complete proof during the third day of the run. Lean, a proof assistant in which a computer checks every step, accepted it.

PSI then set the system to work on related open problems. The system improved the result twice, the company says, and Lean accepted the final version. David Turturean, Member of Technical Staff, led the work: he developed the research system, scoped the problem and ran the system, then prompted the model to package the results into a first draft of the paper. Turturean reviewed the draft and is responsible for the paper’s correctness, PSI says. Jim Halverson, Advisor, audited the proof, and Phiala Shanahan, Advisor, commented on the Lean formalization.

Proof limits quantum speedups on random inputs, PSI says

A quantum computer’s probability of answering “yes” after T looks at its input can be represented by a polynomial in the input bits with degree at most 2T, according to earlier work by Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca and Ronald de Wolf. The Aaronson-Ambainis conjecture concerns how much the polynomial changes when an individual bit flips. The proof lets an ordinary computer estimate the quantum computer’s answer probability for all but a small fraction of strings, using a number of looks that grows at most like a fixed power of T for any fixed error and fraction, PSI says.

The proof shows that a quantum computer cannot save exponentially many looks on yes-or-no questions about random strings unless the string has a rare pattern, PSI says. The proof follows a plan by Shachar Lovett and Jiapeng Zhang, replacing an inequality they had left as a conjecture with a new inequality proved in the manuscript. The proof pairs switch settings using a determinant. David Reimer’s Butterfly Lemma already gives a weaker pairing, PSI says; the proof’s pairing also limits how often paired settings agree on each switch. The proof also uses results by other researchers.

Stanford researchers are preparing an exposition of PSI’s proof, the company says

In August 2026, Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan of Stanford University settled the conjecture’s prediction in a special case, proving that there is no exponential speedup on random inputs for quantum algorithms that look at their input in a fixed number of parallel rounds. The Stanford researchers have since been reading PSI’s proof, have sent comments and are writing a shorter exposition of it for experts, PSI says.

“This is a huge result. It resolves a decades-old conjecture with important implications for the nature of problems that admit quantum speedups. The proof draws on and extends several lines of work in the analysis of boolean functions and probabilistic combinatorics. Everything is brought together in a rather magical way.”

Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan of Stanford University

If a polynomial f whose values stay between 0 and 1 is not constant, some bit i has influence Infᵢ(f) ≥ cv⁵ᐟ²/d⁶ ≥ (v/d)⁷, where v is the variance, d is the degree and c = 8√15/(125π⁴), about 0.0025, PSI says. Earlier bounds for general polynomials decay exponentially in the degree, PSI says, while the conjecture already followed for polynomials with values only 0 and 1.