All news

PSI's SI system proves the Aaronson–Ambainis conjecture, open since 2008

Prepared by Sintelligent with the help of SI. Published in SI: . Updated: .

SI not only produced a proof of an open mathematical problem but also expressed it in a form a computer checked step by step; this process can be repeated and independently verified.

A research system developed by Physical Superintelligence, using instances of a non-public Anthropic model, obtained a complete proof of the conjecture about quantum speedups on random inputs on its third day of operation. The system then improved the result twice while working on related problems. The conjecture reduces the question of quantum advantage to a property of bounded low-degree polynomials: the proved theorem guarantees the existence of a variable with polynomially large influence. It follows that, in the model under consideration, a quantum algorithm does not provide an exponential advantage on random inputs without additional structure. The Lean 4 formalization has been published alongside the preprint. It contains no unfinished proofs or added axioms; the four final theorems have been rechecked by the Lean kernel and an independent type-checking implementation. Machine verification does not cover the human-readable paper or whether the formal statement matches the original formulation: those remain subjects for human review. David Turturean led the work and is responsible for the paper's correctness, while Jim Halverson audited the proof. Researchers who previously proved a special case are reading the full proof and preparing a shorter exposition.