Two-Month-Old Startup Says It Cracked a 20-Year Quantum Puzzle

Physical Superintelligence says it has closed a question in quantum computing that sat open for nearly twenty years. The Cambridge, Massachusetts startup announced on November 6, 2026 that it proved the Aaronson-Ambainis conjecture, using its internal research system paired with a non-public Anthropic model. According to the company, the proof arrived on day three of the run.

The conjecture asks when quantum computers can actually beat classical ones on speed. It was floated around 2008 and given a formal statement in 2014. At its mathematical core, it holds that every bounded low-degree polynomial on the Boolean cube has an influential variable. The result, per the research findings, rules out exponential quantum advantage on random oracles for decision problems.

Even Scott Aaronson, one of the people who posed the problem, admits he doesn't completely follow the proof. He says he believes it is correct because it was autoformalized in Lean and walked through by top researchers who saw the result. That verification layer is the point: Lean writes proofs as code, and a small trusted kernel checks each step. PSI's formalization runs 9,454 lines across 648 theorems, with no added axioms or placeholders, and the research findings say it was independently rechecked with multiple kernels.

The work is published as a 13-page paper plus the full Lean formalization, both on GitHub under the physical-superintelligence organization. Turturean framed the outcome to TechCrunch in plain terms: it's a negative result that tells researchers where they no longer need to look.

The limits are spelled out too. The findings state the proof does not touch structured speedups like Shor's algorithm — it constrains quantum advantage on unstructured inputs, not every flavor of it. And the timing stands out: PSI launched in September 2026 with $58 million in seed funding led by Breakthrough Energy Ventures, then put out a result on a two-decade-old open problem by early November.