The Information Machine
ConcludedRan 1 dayin the edition since 10 Nov 20267 sourcesupdated 10 Nov 2026

AI proof of the Aaronson-Ambainis conjecture

The gist

Latest: PSI's AI System Proves 2008 Aaronson-Ambainis Quantum Conjecture

The result settles a foundational question in quantum complexity theory that had been open since 2008 and that a prior claimed proof failed to resolve. Researchers previously working on the problem called it a 'huge result'; the proof does not imply quantum computers are slower overall, as it concerns only query complexity on unstructured problems and does not affect algorithms like Shor's.

When stories like this move, I write about them in an email each morning.

One free email each morning, around 8 AM US Eastern.

The full picture

Physical Superintelligence announced on November 6, 2026 that an internal research system running a non-public Anthropic model produced a complete, formally verified proof of the Aaronson-Ambainis conjecture, an open problem in quantum complexity theory since 2008. The conjecture states that every bounded low-degree polynomial has a highly influential variable; proving it implies every T-query quantum algorithm can be classically simulated on most inputs by a classical algorithm making polynomially many queries. The Lean proof assistant confirmed every step of the proof. The system produced its initial proof on the third day of operation and subsequently continued on related problems, improving the result twice. PSI staff member David Turturean is listed as the paper's author and is responsible for correctness. The four Stanford researchers who had proved a partial case in August 2026 reviewed the full proof and are preparing an exposition for domain experts. Neither PSI nor Anthropic has publicly named the specific model used.

How it developed
First in the edition · 10 November 2026
9 November 2026

Import AI and The Neuron Daily published coverage, noting the system improved its result twice and continued on related open problems after the initial proof.

7 November 2026in the 10 Nov edition

Physical Superintelligence announced on November 6, 2026 that an AI system running a non-public Anthropic model proved the Aaronson-Ambainis conjecture, a 2008 open problem in quantum query complexity, with every step confirmed by the Lean proof assistant.

A prior claimed proof by Keller and Klein in 2019 had contained an error. Stanford researchers who settled a partial case in August 2026 reviewed the full proof and are preparing a domain-expert exposition; researchers previously working on the problem called it a 'huge result.'

Sources
2 more sources

Get the daily email

When stories like this move, I write about them in an email each morning.

One free email each morning, around 8 AM US Eastern.

See the latest edition · Privacy