Physical Superintelligence, a research group that goes by PSI, says a system it built in-house has proved the Aaronson-Ambainis conjecture, a question about quantum computers that has sat open since 2008. The system ran on a non-public Anthropic model, according to a post on PSI Research’s own site dated 6 November 2026. The claim is big, and the post says fairly precisely how far it has been checked, so the status deserves care.
Start with what the conjecture is about. Quantum computers are known to beat ordinary ones by a huge margin on a few tasks, the best known being Peter Shor’s 1994 method for factoring large numbers. The trick is a repeating pattern buried in the numbers, which a quantum machine can pick out. Most dramatic quantum speedups depend on some hidden structure in the input like that. Nobody knew whether the same dramatic gain was possible on random inputs, and those almost never carry any such pattern.
Scott Aaronson and Andris Ambainis found a way to attack that question with pure mathematics. They conjectured something about a family of polynomials (formulas built from the bits of the input, with values that stay between 0 and 1): at least one bit always has a sizable influence on the output, with the size set by how much the output varies and how complicated the formula is. They also showed that if this holds, an ordinary computer can imitate a quantum one on random inputs using only a modestly larger number of peeks at the data. In plain terms, no exponential advantage.
PSI says its system had a complete proof by day three of the run, and that Lean accepted it. Lean is a proof assistant, software that verifies each logical step. The team then pointed the system at related open problems, which led it to strengthen the result twice, and Lean passed the final version as well. The proof follows a plan from Shachar Lovett and Jiapeng Zhang, who had left one inequality unproven, and replaces that gap with a new inequality.
The human checking is thinner and comes from inside the company. David Turturean, the PSI engineer who built the system and led the work, reviewed the paper and takes responsibility for its correctness. Jim Halverson, a PSI advisor, audited the proof, and fellow advisor Phiala Shanahan commented on the Lean version. A machine check settles whether each step follows from the last; a person still has to confirm that the formal statement says what the conjecture says.
Outside eyes are on it, though the post does not describe them as signing off. In August 2026, four Stanford University researchers, Li-Yang Tan, Guy Blanc, Jordan Docter and Carmen Strassle, proved a special case that covers quantum algorithms reading their input over a set number of parallel rounds. PSI says they have since studied the full proof, sent comments, and are preparing a shorter exposition for specialists. Their words to PSI, as quoted in the post: “This is a huge result. It resolves a decades-old conjecture with important implications for the nature of problems that admit quantum speedups.”
What the post leaves out matters for how to label this. It is a company write-up. It mentions no journal submission and no referee reports, and the Stanford exposition has not appeared yet. The accurate description today is a machine-checked proof, audited by the authors’ own advisors and being read by outside specialists, but not peer reviewed.
If it holds, the consequence reaches past one proof. Anyone selling quantum computing as a broad speedup for ordinary, unstructured data has a theorem against them, and the exponential gains stay confined to problems with hidden structure, like the factoring that Shor’s method exploits. The Stanford group’s shorter write-up is the next public checkpoint.
Reported by PSI Research on 6 November 2026.
