PSI and Anthropic crack 18-year-old quantum computing conjecture

The popular fantasy around quantum computers is that they are magic boxes destined to make every calculation infinitely faster overnight.

Now, an AI system has slammed the door on a big chunk of that fantasy.

Physical Superintelligence (PSI) announced that its internal research system, running an unreleased Anthropic model on PSI's own hardware, has completely solved the Aaronson-Ambainis conjecture. The open problem had stumped theoretical computer science for 18 years. Even wilder: the proof was found on day three of the run, and the interactive proof assistant Lean formally verified every single mathematical step without complaint.

First formulated in 2008 by Scott Aaronson and Andris Ambainis, the conjecture is now officially a theorem.

Bursting the unstructured speedup bubble

To understand why this matters, you have to look at why quantum computers ever seemed fast in the first place.

Back in 1994, Peter Shor found a quantum algorithm capable of cracking prime factorizations exponentially faster than ordinary computers. But Shor's algorithm depends on finding hidden periodic patterns. It relies entirely on mathematical structure.

What happens when an input has no structure whatsoever, like completely random data? Could quantum superpositions still deliver an exponential speedup? For nearly two decades, no one could prove it one way or the other.

Aaronson and Ambainis reframed this into a question of pure mathematics involving low-degree polynomials. They showed that if their conjecture held true, an ordinary computer could mimic the quantum computer's output on random inputs with only a small number of looks. Exponential speedups would be impossible.

In August, a Stanford team cracked a narrow, special case of the conjecture. Now, PSI's machine-assisted run has settled the full thing. The Stanford researchers reviewed the complete proof and called it a huge result that brings several fields together in a rather magical way.

The mystery Anthropic engine under the hood

David Turturean, a member of technical staff at PSI, led the effort. He built the system, framed the problem, ran the experiment, and had the model package the findings into a first paper draft.

Naturally, the tech world immediately latched onto the unnamed model powering the run. Community buzz and industry watchers speculate that this engine may be Anthropic's unreleased Model 4. That speculation tracks with a recent METR investigation reporting that Anthropic's internal pace of model improvement has roughly doubled compared to prior periods, driven largely by AI systems participating in their own development.

Whether or not the Model 4 label is accurate, taking just three days to resolve a decades-old theoretical problem and passing Lean's rigorous verification is a staggering demonstration.

Why it matters

In our view, this announcement delivers a double shockwave to both physics and artificial intelligence.

For quantum computing, it sets a hard mathematical ceiling. It puts an end to the vague hype claiming quantum chips will magically accelerate arbitrary calculations. If a problem does not possess exploitable structural patterns, quantum hardware simply cannot outrun classical computers exponentially. That clarity will save billions of dollars in speculative research and force developers to focus on domains where quantum advantages are genuine.

For AI, this is proof that frontier models have graduated from writing boilerplate code to doing real, heavyweight theoretical science. Pairing an LLM's combinatorial intuition with a formal checker like Lean solves the hallucination dilemma in high-stakes reasoning. The AI brainstorms the proof; the machine verifier guarantees the math.

We think this pairing represents the blueprint for future scientific discovery. If autonomous systems can crack twenty-year-old conjectures in a weekend, the research velocity gap between teams adopting AI-assisted theorem proving and those relying solely on pen and paper is about to become unbridgeable.