On November 6, startup PSI (Physical Superintelligence) announced that its in-house research system, running an unreleased Anthropic model, has proved the Aaronson-Ambainis conjecture, open for 18 years. The complete proof was written down on the third day of the run and passed Lean, a proof assistant that checks every step. It is a landmark claim for AI tackling hard mathematics — but for now it is still one company's claim: the paper has not been peer-reviewed.
What is the conjecture actually asking?
The Aaronson-Ambainis conjecture asks how much faster quantum computers can be than classical ones on unstructured data. It asserts that, on unstructured inputs, quantum algorithms cannot achieve exponential speedups. The question has been open since 2008. In August, a Stanford team proved a special case; PSI says its system has now pushed the result to the full case. If the proof holds, it draws a firm line around what quantum computing can do.
How did the machine prove it — and how many times was it checked?
According to PSI, the research system ran continuously on the company's own infrastructure, produced a complete proof on day three, then improved the result twice on related problems, with Lean accepting the final version each time. PSI published the paper and the Lean 4 formalization together on GitHub: 648 machine-checked theorems, no proof steps left blank, and no extra axioms introduced; the statements were also replayed through the Lean kernel and the independent implementation lean4lean. PSI technical staff member David Turturean takes responsibility for the paper's correctness, and mathematicians have audited the proof.
Don't write it into the textbooks just yet
A machine-checked proof is not the same as acceptance by the mathematics community. Lean can guarantee that every step follows the rules, but it cannot confirm that the formal statement matches the conjecture as Aaronson and Ambainis originally posed it — that still needs expert checking by hand; the human-readable paper itself was not machine-checked; the proof counts queries, not total compute time; and the model used was not disclosed, with Anthropic declining to comment. Also on November 6, Google DeepMind announced that AI agents had found two new weaknesses in 1024-bit RSA encryption. AI is advancing on two fronts at once, mathematics and cryptography. Whether PSI's proof survives peer scrutiny, the expert reviews of the coming weeks will tell.
