AI just proved a quantum conjecture from 2008. Who checks the checker?

A machine-verified proof landed in three days. The catch is hiding in the word "verified".

Ok, you have to hear this one. On November 6, a startup called Physical Superintelligence said its research system, running a non-public Anthropic model, had proved the Aaronson-Ambainis conjecture. That is a question from quantum complexity theory that has sat open since 2008. Eighteen years. People built careers around chipping at the edges of it.

And the machine? According to the company, it had a full proof sometime on day three of the run.

What was the question, actually?

Picture a quantum algorithm that peeks at the bits of its input a limited number of times. The chance it says "yes" turns out to be a low-degree polynomial in those bits. The conjecture says every such well-behaved polynomial has at least one bit that really matters, one that moves the answer by a noticeable amount when you flip it.

Why should you care? Because if that is true, quantum computers cannot get an exponential edge on random, structureless inputs. The big quantum wins have to come from problems with structure. A paper from August, called "Quantum Speedups Require Structure or Depth", had already nailed a special case. Now someone claims the whole thing.

The proof is checked by a machine. So we're done, right?

And here is the part that should make you pause: if Lean accepted the proof, what is there left to argue about?

Fair question, and the answer is a bit sneaky. Lean is a proof assistant. It checks that every step of an argument is valid, down to the last logical atom. What it cannot check is whether the statement someone typed into Lean is the same thing the mathematicians actually meant. If the formal version is slightly easier than the real conjecture, Lean will cheerfully bless a proof of the wrong thing.

So humans still have to read the formal statement and confirm it matches. The human-readable paper is not machine-checked either. The company says a physicist audited the proof, and the team that proved the special case in August reviewed it too. Peer review has not happened yet.

So how big is this, really?

Big, if it holds. The AI was reportedly built on top of a known framework involving fractional certificates and level sets, and then it was pointed at neighbouring problems, which produced two further improvements before the final version was checked. That is not a lucky guess. It looks like a research loop.

But notice the shape of the story. The hard part used to be finding the proof. Now the hard part is trusting the thing that is standing next to it, smiling, with a green checkmark. The next few weeks of expert reading will decide whether November 6 is the day a conjecture became a theorem, or the day we learned how much "verified" can hide.