The Aaronson-Ambainis conjecture, open since 2008, is now a theorem. Physical Superintelligence (PSI) says a research system it developed internally, running a non-public Anthropic model, found the proof. Lean, a proof assistant in which a computer checks every step, accepted it.
The conjecture concerns when quantum computers can be exponentially faster than ordinary ones. In 1994, Peter Shor found a quantum algorithm that factors large numbers far faster than any known ordinary method, but it relies on a special structure: a repeating pattern. Whether quantum computers can be exponentially faster on random inputs, which almost never have such structure, was unknown. Scott Aaronson and Andris Ambainis stated a conjecture about polynomials and showed that, if true, quantum computers are at most polynomially faster on random inputs.
What the proof shows
Speed here is measured in looks: how often a computer reads its input, a string of 0s and 1s. Earlier work showed that after T looks, a quantum computer's probability of saying yes is a polynomial of degree at most 2T, with values between 0 and 1. The conjecture is about the influence of a bit, meaning the average change in the polynomial's value when that bit is flipped. The proof shows that if the polynomial is not constant, some bit has influence at least a fixed power of v/d, where v measures how much the value varies and d is the degree. Earlier bounds decayed exponentially in the degree.
As a result, an ordinary computer can estimate a quantum computer's chance of saying yes, on all but a small fraction of inputs, with a number of looks that grows at most like a fixed power of T, not exponentially. On yes-or-no questions, a quantum computer cannot save exponentially many looks unless the input has a rare pattern.
Researchers previously settled the conjecture's prediction in a special case. They have now read the full proof and are writing a shorter exposition, calling it "a huge result." Aaronson sent "huge congratulations" to PSI and Anthropic.
The result matters because the conjecture was counted among the central open problems of quantum complexity theory, the study of what quantum computers can and cannot do. It draws a firm line: exponential quantum speedups require structured problems. It is also a notable case of an artificial intelligence system producing a machine-checked proof of a major conjecture.