started · updated
Physical Superintelligence AI proves Aaronson-Ambainis conjecture
An AI research system developed by Physical Superintelligence (PSI) has produced a proof for the Aaronson-Ambainis conjecture, a mathematical problem in quantum computing complexity theory that has remained open since 2008.
Using an unreleased Anthropic model, the system identified the proof in three days. The result suggests that quantum computers do not provide an exponential advantage over classical computers for most unstructured decision problems in the query model. Instead, exponential speedups require specific mathematical structures in the input, such as those found in Shor’s factoring algorithm.
To ensure mathematical rigor, the proof was autoformalized using the Lean programming language and subsequently verified by leading scientists. Scott Aaronson, one of the original authors of the conjecture, stated that while he does not yet grasp every detail, he considers the proof to be correct.
Entities
Aaronson-Ambainis Conjecture · Andris Ambainis · Anthropic · Lean · Physical Superintelligence · Scott Aaronson · Stanford University