← Back to blog
AiAbout 7 min read

An 18-Year-Old Quantum Conjecture Fell in Three Days. The Proof Came With a Checker.

Published Nov 7, 2026
An 18-Year-Old Quantum Conjecture Fell in Three Days. The Proof Came With a Checker.

On November 6, Physical Superintelligence said its internal research system had proved the Aaronson-Ambainis conjecture. The run took three days to produce a complete argument. Lean, the proof assistant that makes a computer check every step, accepted it. The system then went after related problems, strengthened the result twice, and Lean accepted the final version too.

PSI published both a human-readable paper and a full Lean 4 formalization under Apache 2.0. The repository states that the development contains no proof placeholders and no added axioms, and that the four main theorems were replayed through Lean's kernel and through lean4lean, an independent implementation of the same type checker. A comparator using both the Lean and nanoda kernels accepted the finals. On a second machine, the same comparator accepted one correct toy solution and rejected four deliberately wrong ones.

That control test is the part I keep coming back to. It is what separates a claim from a receipt.

What the conjecture actually says

Most famous quantum speedups depend on structure. Shor's 1994 factoring algorithm works because the input hides a repeating period. Ask a quantum computer to answer yes-or-no questions about uniformly random inputs and that structure is gone, which is where the open question lived: can a quantum machine still be exponentially faster?

Aaronson and Ambainis turned the question into a statement about polynomials. In the query model, you count how many times an algorithm reads its input. After T queries, the probability that a quantum algorithm answers yes can be written as a polynomial of degree at most 2T whose values sit between 0 and 1. To simulate that algorithm classically, you need to estimate the polynomial without reading an exponential number of input bits.

The conjecture says every bounded low-degree polynomial that is not nearly constant has at least one coordinate with high influence. Flipping that one bit has to move the polynomial's value by a meaningful amount on average. If that holds, then a classical machine can simulate any T-query quantum algorithm on most inputs using polynomially many queries in T. No exponential speedup on unstructured inputs.

PSI's proof gives an explicit bound: some bit has influence of at least a constant times v to the 5/2 over d to the sixth, where v is the variance and d the degree, with the constant around 0.0025. In looser form, at least (v/d)^7.

The route follows a plan laid out by Shachar Lovett and Jiapeng Zhang, built on fractional certificates and level sets. Lovett and Zhang had left one inequality unresolved, stated as a conjecture. PSI's system replaced it with a new all-pairs inequality derived from a determinant-based pairing of input settings, which it says goes past David Reimer's earlier Butterfly Lemma by limiting how many coordinates can agree.

What got machine-checked, and what did not

Here is where I think most coverage of this story will go wrong. A Lean proof is a strong artifact. It is not a full certification of the result, and PSI says so itself.

Three things sit outside the machine check. The Lean kernel, compiler, Mathlib's definitions, and the hardware doing the checking are all part of the trusted base. The prose paper is not machine-checked, only the formal statements are. And a human still has to confirm that the formal statement matches the conjecture as Aaronson and Ambainis printed it in 2008.

PSI made that last step as easy as it could. The repository isolates a single definition named `PrintedConjecture` in a file that imports nothing but Mathlib, so a skeptical reader can open one file and compare it to the original paper. That is a thoughtful piece of interface design for verification, and it also tells you the authors knew where the weak joint was.

Blank paper sheets held flat by a slim brass straightedge on a dark wooden desk, lit by one shaft of afternoon light.

The audit was internal. Jim Halverson audited the proof and Phiala Shanahan commented on the formalization, and both are PSI advisors. There has been no peer review and no journal publication. The four Stanford researchers who proved a special case in August 2026, Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan, have read the full proof and sent comments, and are preparing a shorter exposition. Their quoted assessment calls it a huge result. Correspondence with interested experts is useful. It is not review.

The human roles are named, which I appreciate. David Turturean, a member of technical staff who studied physics and AI at MIT, built the research system, scoped the problem, ran it, prompted a non-public Anthropic model instance to package a first draft, reviewed that draft, and is named as responsible for the paper's correctness. The repository discloses that AI models produced the mathematical statements, the first draft, and the Lean formalization.

That division of labor is worth stating plainly, because it is going to become ordinary. A person picks the problem and carries the blame. A model produces candidate arguments. A checker rejects the ones that do not close. The output is a claim that can be re-run by anyone with a laptop and an afternoon.

Why the checker matters more than the model

Anthropic has not said when or whether the model behind this will ship. That detail is almost a distraction. The interesting object here is the pipeline, and the pipeline is reproducible in a way that a benchmark score is not.

Think about what a skeptical mathematician can do with this release. Clone the repo. Read `PrintedConjecture`. Run Lean. Run lean4lean. Run the comparator. Check that no axioms were added. Every one of those steps either passes or fails, and the failure modes are specific.

Compare that to the alternative. A lab posts a chart, a product page, and a paragraph about reasoning improvements. You either believe it or you don't.

Formal verification is not magic and it does not settle mathematics. It settles a narrower thing: whether a particular formal statement follows from particular axioms by particular rules. Everything about whether the statement is the right one, whether the axioms are the right ones, and whether the result matters stays with people.

PSI is a Cambridge, Massachusetts public benefit corporation that launched publicly in September with a $58 million seed round led by Breakthrough Energy Ventures. It describes itself as an AI-native physics lab staffed by virtual physicists meant to reason like theorists and validate like computational physicists. It says it solved five long-standing problems in quantum information theory last month, and this is its second major announcement in about two weeks. That pace is either impressive or a warning, depending on how much of it survives outside attention.

What it means for the quantum story

The result sharpens a boundary. For yes-or-no questions about unstructured random inputs, quantum machines cannot save exponentially many queries. Algorithm designers should look for problems with real structure, in the mathematics or in the physics, rather than hunting for speedups on generic inputs.

It does not tell you which applications will pay off. The query model counts input reads, not the work of loading and processing data, so it puts no general limit on total runtime or on the commercial value of a quantum computer. Anyone quoting this paper as proof that quantum computing is dead is quoting something that is not in it.

The other thing it does not do is end the argument about AI doing research. A single result, produced by an internal system, audited internally, on a problem where the surrounding literature had already narrowed the approach to one unresolved inequality, is a data point. Lovett and Zhang had the plan. Reimer had a lemma. The system closed a gap. That is real work and it is also a narrow slice of what mathematical research involves.

The remaining step is the one PSI cannot do for itself. Somebody in the field has to read the formal statement, agree that it is Aaronson and Ambainis's conjecture and not a convenient cousin of it, and say so in public. Until then, what exists is a machine-verified derivation of something very close to a famous claim, plus a repository built so that the last mile is short.

That is a better position than most announcements leave you in.

Related articles