An AI Just Proved an 18-Year-Old Quantum Conjecture in 3 Days. Here’s What It Means.

by | Nov 7, 2026 | Artificial Intelligence, Quantum Computing, Quantum Mind | 0 comments

Label: Emerging Research — the result is machine-checked but not yet peer-reviewed. Read it as a milestone with an asterisk, not a settled verdict.

Eighteen years. That’s how long the Aaronson-Ambainis conjecture sat open — a question about the limits of quantum computing that some of the sharpest minds in theoretical computer science couldn’t close.

An AI system closed it in three days.

On November 6, 2026, a physics research company called Physical Superintelligence (PSI) announced that its research system, PSIntelligence, had found a complete proof of the conjecture — and that Lean, a program that checks every step of a mathematical proof by computer, had accepted it. The hardest few lemmas took eight hours. The system then improved the proof twice, and Lean accepted the final version.

If the result holds up under human review, it is one of the most consequential things an AI has ever done in mathematics. And the most interesting part isn’t the speed. It’s what the proof says about the limits of quantum computers themselves — and what it reveals about the new division of labor between human mathematicians and their machine collaborators.

What actually happened

PSI is a young company — it launched publicly in September 2026 — that describes itself as building automated systems for scientific discovery. Its research system ran on the company’s own infrastructure, using instances of a non-public model from Anthropic, with heavy prompt engineering, extensive test-time compute, and iterative AI reasoning: produce a proof attempt, test it, refine it, repeat.

The proof itself is public. PSI posted the paper and the full Lean formalization on GitHub the same day, under an open license. The numbers are striking: 84 Lean files, 761 declarations, 648 machine-checked theorems, no step left as a placeholder, no added axioms. The four final theorems were re-checked by two independent implementations of the Lean kernel.

David Turturean, a member of PSI’s technical staff, led the work — he built the research system, chose the problem, ran it, prompted the first paper draft, and is named as responsible for the paper’s correctness. Jim Halverson audited the proof. Phiala Shanahan commented on the Lean formalization. And the repository is blunt about authorship: the mathematical statements, the first draft of the paper, and the Lean code “were produced by AI models.”

That last line is the one to sit with. The human in the loop scoped the problem, built the system, and stands behind the result. The machine did the proving.

The conjecture, in plain English

The Aaronson-Ambainis conjecture was proposed in 2008 by Scott Aaronson and Andris Ambainis. It asks a deceptively simple question: when can a quantum computer be exponentially faster than an ordinary one — and when is that speedup impossible?

Here’s the intuition. A quantum algorithm works with a kind of mathematical object called a low-degree polynomial — a formula describing how the algorithm’s answer depends on its input. The conjecture says that any such polynomial has at least one influential variable: a single input bit that matters a lot. Flip it, and the answer swings.

Why does that matter? Because if every low-degree polynomial has an influential variable, then a classical computer can simulate the quantum algorithm efficiently — it just needs to pay attention to the influential bits. The quantum speedup, in that class of problems, evaporates. The classical machine needs only a polynomially larger number of queries (looks at the input), not an exponentially larger one.

The proof PSI’s system found establishes exactly that, with an explicit bound: some variable has influence of at least (ε/d)^7, where ε measures how much the answer varies and d is the degree of the polynomial. It follows a plan sketched by Shachar Lovett and Jiapeng Zhang, and builds on ideas from several earlier mathematicians.

In short: for this whole class of problems, quantum computers are not magically faster. Structure is what makes speedups possible — and structure is also what limits them.

Why it matters — and what it doesn’t mean

This is where careful reading pays off, because the headlines can mislead in both directions.

What it does mean: the boundary between quantum and classical computing just got sharper. Exponential quantum speedups require specific structure in the problem. For unstructured problems — the kind covered by the conjecture — a classical computer can keep up, at least in terms of how many times it needs to look at the data. That’s a genuine advance in our understanding of where quantum advantage lives.

What it doesn’t mean:

  • It doesn’t mean quantum computers are useless. Algorithms built differently — Shor’s factoring algorithm is the famous example — are untouched by this result. The conjecture covers one class of computations, not all of them.
  • It doesn’t apply directly to hardware. This is a statement about query complexity — how many times an algorithm reads its input — not about how fast a physical quantum chip runs, or whether one will ever be built at scale.
  • It doesn’t count total computing time. The theorem restricts data reads, not the total work of computing answers or deciding which bits to inspect. Practical room for quantum advantage remains.

Think of it like this: the proof doesn’t shrink the quantum computer. It maps the territory where the quantum computer is special — and the territory where it isn’t.

How the machine did it

The three-days framing is dramatic, but the real story is the method. PSI’s system didn’t just “ask the AI” for a proof. It ran an iterative loop: generate candidate proof steps, check them in Lean, keep what verifies, revise what doesn’t, and repeat — with extensive test-time compute, meaning the model spent a lot of computation thinking through each step rather than answering quickly.

This is a different kind of AI achievement from writing an essay or generating an image. A Lean-checked proof is either right or it isn’t. There’s no bluffing past a proof checker: every step must follow logically, or the whole thing fails. That verifiability is exactly what makes the claim hard to dismiss — and exactly why PSI published the full formalization instead of just announcing the result.

There’s also a human subplot worth noting. In August 2026, a Stanford team — Guy Blanc, Jordan Docter, Carmen Strassle, and Li-Yang Tan — had already settled the conjecture’s prediction in a special case: quantum algorithms that make their queries in a small number of parallel rounds. That team has since been reading PSI’s full proof and is writing a shorter exposition of it for other experts. Aaronson himself has noted that the August result was pre-AI — AI was used only for proofreading — while a separate team (Liu and Mutreja) independently achieved the same special case with more substantial AI involvement. The field was already converging on this problem from several directions. PSI’s system just got there first, and all the way.

The trust question

Here’s the part Quantum Self readers should care about most, because it cuts to the heart of how knowledge works now.

Lean can verify that a proof follows logically from its assumptions. What Lean cannot verify is whether the formal statement the machine proved is the same thing Aaronson and Ambainis meant in 2008. That matching step — comparing the machine’s precise statement to the human conjecture — still requires human experts. PSI has made that check as easy as possible: the formal statement lives in a short file that imports nothing but Lean’s mathematics library, so experts can read it and compare.

The prose paper, meanwhile, is not itself machine-checked. And the result has not yet undergone full independent academic review. Stanford’s analysis is incomplete. The outcome, as the coverage has stressed, remains provisional until independent experts complete their review.

That doesn’t diminish the result. It frames it correctly. A machine-checked proof is a new kind of evidence in mathematics — stronger than a claim, weaker than a consensus. The honest label for this story is the one at the top of this article: Emerging Research.

There’s a deeper question underneath, and it’s one this site will keep returning to: when machines can prove theorems humans can’t, what happens to mathematical understanding? A proof you can’t follow isn’t useless — Lean doesn’t care whether you follow it — but understanding has always been how mathematics earns trust over time. The Stanford exposition, when it arrives, matters as much as the proof itself. Verification tells us the logic holds. Explanation tells us why.

A very good week for quantum

The PSI announcement didn’t arrive in a vacuum. It capped a remarkable week for quantum computing:

  • November 3: Researchers at the University of Regensburg showed that a single additional measurement before a series of quantum operations can cut qubit error rates by more than half — from about 0.14% to 0.065% — a practical step toward more reliable quantum hardware.
  • November 2: Scientists reported in Nature a single-molecule spin-photon interface — a molecule whose spin state can be controlled and read out, with light frequencies stable for over an hour — a building block for future quantum networks.
  • November 1: A team led by Jiangfeng Du demonstrated an autonomous quantum error-correction system that beat the “break-even point,” where error correction actively improves qubit reliability rather than degrading it, published in Nature Physics.
  • November 3: Quantum X Labs demonstrated its Qatacomb quantum encryption scheme on a real IBM processor (the 156-qubit Heron r2), with the intended recipient recovering an encrypted image through real hardware noise while an adversary without the key gained no usable information.

Error correction, networking, encryption, and now machine-proved theory: the field is advancing on every front at once. That convergence is the real story of this week.

Watch: the conjecture’s co-author explains quantum computing

If the mathematics above felt abstract, start here. Scott Aaronson — the Aaronson in Aaronson-Ambainis — explains quantum computing in plain English in this short video from MIT. It’s the clearest twelve minutes you’ll spend on what a quantum computer actually is, and why it matters.

Watch: Scott Aaronson breaks down quantum computing (MIT CSAIL)

What to watch next

  1. The Stanford exposition. When Blanc, Docter, Strassle, and Tan publish their shorter version of the proof, watch for whether they endorse the formal statement as a faithful rendering of the conjecture. That’s the moment this moves from “machine-checked” toward “accepted.”
  2. Peer review. The paper is a preprint. Formal journal review will take months, and reviewers may find subtleties the machine check can’t see.
  3. What PSI’s system tackles next. The company says it set the system to work on related open problems after the proof — and it improved the result twice along the way. The next announcement will tell us whether this was a one-off or a pipeline.
  4. The model gap. The Anthropic model PSI used is non-public. The distance between what internal research systems can do and what the public can access is itself becoming a story — one we’ll keep tracking.

Keep exploring

Sources

This article is educational information. It distinguishes evidence from interpretation and does not offer medical, psychological, or financial advice. The PSI result described here is machine-checked but not yet peer-reviewed.