Photo: Google DeepMind / Pexels
The Cambridge startup says its system proved the Aaronson-Ambainis conjecture in three days, with a Lean formalization to back it up
A startup that is barely two months old says it has settled a quantum computing question that stumped researchers for nearly two decades.
Physical Superintelligence, or PSI, announced on November 6, 2026 that it had proven the Aaronson-Ambainis conjecture. The work used its internal research system alongside a non-public Anthropic model, and the company says the proof landed on day three of the system’s run.
Even more striking is the reaction from one of the people who posed the problem. Scott Aaronson says he doesn’t fully follow the proof. He believes it anyway.
What PSI actually proved #
The Aaronson-Ambainis conjecture is about a basic question: when can quantum computers actually beat classical ones on speed? It was first floated around 2008 and given a formal statement in 2014.
Stripped to its mathematical core, the conjecture says that every bounded low-degree polynomial on the Boolean cube has an influential variable.
According to the research findings, the proof rules out exponential quantum advantage on random oracles for decision problems. Partial results had chipped away at the problem before. The full proof had never arrived until now.
PSI has published its work as a 13-page paper and a complete Lean formalization, both hosted on GitHub under the physical-superintelligence organization.
Why Lean is doing the heavy lifting #
Lean is a programming language built for mathematics. Rather than relying on a human referee to read and check every step, you write the proof as code and a small, trusted program called a kernel verifies that each step follows logically from the last.
AI, tech, and the markets they move—in one daily briefing.
Daily. Free. Join 34,000+ readers across crypto, finance, and policy.
The scale here is substantial. PSI’s formalization runs to 9,454 lines and 648 theorems, with no added axioms or placeholders.
The research findings also note that the formalization was independently rechecked using multiple kernels.
This verification layer is exactly why Aaronson is willing to sign off on something he doesn’t completely grasp. He says he believes the proof is correct because it was autoformalized in Lean and explained by a team of top researchers with whom PSI shared the result.
A negative result, and why that’s useful #
The finding doesn’t unlock a faster quantum algorithm. It closes a door.
Turturean described it to TechCrunch in practical terms:
“It’s a negative result that allows people to know, okay, we’re no longer looking there.”
The result also has clear limits. The research findings specify that it does not affect structured speedups such as Shor’s algorithm. The proof constrains quantum advantage on unstructured inputs, not every flavor of quantum advantage.
Who is PSI, anyway #
PSI is a public benefit corporation based in Cambridge, Massachusetts. It launched in September 2026 with $58 million in seed funding led by Breakthrough Energy Ventures.
That timeline is notable. A company that raised its first round in September put out a result on a nearly two-decade-old open problem by early November.
The Anthropic angle is also eye-catching. PSI used a non-public Anthropic model as part of its system, meaning the result came partly from AI capabilities that outside researchers cannot currently access.
Disclosure: This article was edited by Diego Almada Lopez. For more information on how we create and review content, see our Editorial Policy.