LodeHQ
AI news for people who shipFree, by email

AI · psi.inc · Tuesday, 10 November 2026

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.

Read the source: psi.inc ↗In the 10 November issue →