A new proof rules out exponential quantum speedups on random inputs
The Aaronson-Ambainis conjecture is now a theorem: quantum computers are at most polynomially faster than ordinary computers on random inputs, narrowing where useful exponential speedups can exist. PSI says its internal research system found the proof during day three of a run using a non-public Anthropic model; Lean, a proof assistant that checks every step, accepted it and two later improvements. The proof builds on several earlier results in mathematics.