A research AI claims to have proven a 2008 conjecture
Physical Superintelligence claims to have obtained a proof of the Aaronson-Ambainis conjecture using an Anthropic model. The proof was formalized in Lean, but its exact correspondence with the statement remains to be verified.
Physical Superintelligence announced on November 6, 2026, that an internal research system, running on its own infrastructure and based on instances of a non-public Anthropic model, had found a proof of the Aaronson-Ambainis conjecture, an open quantum computing problem since 2008. The complete proof emerged on the third day of execution, then the Lean proof assistant accepted it. The stakes are high: this conjecture concerns when a quantum computer can truly outperform a classical one, and in which cases the gain remains limited.
Un résultat quantique qui regarde autant la théorie que la machine
The Aaronson-Ambainis conjecture concerns quantum speedups, that is, the speed gains a quantum computer can achieve compared to a classical machine. In the case of a structured problem, like factorization exploited by Shor’s algorithm in 1994, quantum computing can leverage a repetitive pattern. Here, the setting is different: the result targets random or unstructured inputs, where this type of shortcut often disappears.
In the query model, a classical algorithm reads one bit per query, whereas a quantum query can be spread in superposition over multiple input positions. PSI links this framework to polynomials: after T quantum queries, the probability of answering “yes” becomes a bounded polynomial of degree at most 2T. Simulating the algorithm then amounts to estimating this polynomial without reading an exponential amount of data. The kind of detail that makes you love math at 2 a.m., or avoid it forever.
Ce que la conjecture promettait, et ce que la preuve prétend maintenant tenir
In their original work, Scott Aaronson and Andris Ambainis formulated the following idea: every bounded low-degree polynomial has a highly influential variable. They showed that if this conjecture is true, every quantum algorithm with T queries can be simulated, on most inputs, by a classical algorithm using a polynomial number of queries in T. The consequence is clear: for a given approximation error and a fixed fraction of excluded inputs, growth remains polynomial rather than exponential. This does not close the door to quantum advantages, but confines them to problems where structure really matters.
The PSI repository formalizes this statement as follows: for a real polynomial p of degree at most d, whose values on the discrete cube remain between 0 and 1, if its variance on a uniform input is at least ε, then a coordinate has an influence of at least (8√15 / (125π⁴)) · ε^(5/2) / d⁶, and thus at least (ε/d)⁷. Influence denotes the expected squared change of p when flipping the bit of that coordinate.
Une preuve construite par morceaux, puis vérifiée dans Lean
According to the repository, the argument follows a plan proposed by Shachar Lovett and Jiapeng Zhang, based on fractional certificates and level sets, but replaces a conjectured inequality with a new “all-pairs” inequality. A determinant-type bound constructs a bijective mapping of input configurations. PSI argues that this correspondence goes beyond David Reimer’s butterfly lemma, as it also limits how often pairs agree on each coordinate.
The formal development is divided into four steps: deriving the all-pairs inequality from the determinant and bijection, integrating it over level sets, averaging over coordinates, then establishing a line bound with a pointwise sensitivity bound. The whole leads to the explicit influence bound.
The claimed formal verification is robust but not magical. The repository indicates it contains neither proof holes nor added axioms. Its statements have been replayed by the Lean kernel and by lean4lean, an independent implementation of the Lean type checker. During a sandbox run, a comparator using the nanoda and Lean kernels accepted the four final theorems; on a second machine, it accepted a small correct solution and rejected four deliberately false solutions.
Des garanties formelles, mais pas un blanc-seing total
These verifications have their limits. A reader must still confirm that the formal statement matches the printed conjecture. The natural language article itself is not machine-checked, while the Lean kernel, compiler, Mathlib definitions, and machines used for verification remain in the trust base. In other words, AI helped run the machinery, but did not remove the need for human reading.
Physical Superintelligence also specifies human roles. David Turturean, a technical team member, developed and ran the system, framed the problem, asked the model to produce a first version, reviewed this draft, and bears responsibility for the article’s accuracy. The repository indicates AI models produced the mathematical statements, the first draft, and the Lean formalization. Jim Halverson audited the proof, and Phiala Shanahan commented on the formalization.
The announcement follows a paper submitted on August 19, 2026, by Guy Blanc, Jordan Docter, Carmen Strassle, and Li-Yang Tan, who had already resolved a consequence related to classical simulation of parallel quantum algorithms. PSI reports that the four authors read the entire proof, sent comments, and are preparing a shorter version for specialists. The real test now will be less spectacular than the press release: having experts confirm that the formal statement matches the Aaronson-Ambainis conjecture and that the parts outside Lean also hold up.
By the numbers
- 2008 — year the Aaronson-Ambainis conjecture was stated.
- November 6, 2026 — date of the announcement by Physical Superintelligence.
- 3rd day — moment when the complete proof emerged on PSI’s infrastructure.
- 4 theorems — final elements accepted by a comparator during a sandbox run.
- 2 machines — verification setup mentioned in the repository.