Computer scienceMachine-checked

AI system proves the Aaronson–Ambainis conjecture on the limits of quantum speedups

Physical Superintelligence (PSI) · PSI research system running a non-public Anthropic model

The conjecture, open since 2008, says every bounded low-degree polynomial has at least one input bit with sizeable influence. PSI's system had a full proof by day three of its run and then tightened the bound twice, ending at an influence of at least about 0.0025·v^(5/2)/d^6 for variance v and degree d, where earlier bounds shrank exponentially with the degree. It follows that a quantum algorithm cannot save exponentially many input reads on typical random inputs to a yes/no problem.

Still openLean accepts the main theorem, but the paper sits on GitHub without peer review. The only outside readers so far are a Stanford group whose comments are known through PSI, and the model is not public. The result limits input reads, not total running time.

Machine-checked. A formal proof compiles in a proof assistant such as Lean. People have not yet confirmed that it proves what the announcement says. How entries are graded

Record

  1. Added to the ledger

AI Discovery Ledger Weekly

One email every Friday, about a three-minute read: the week's lead result, the grades that moved up or down, what else was logged, and what is still open.

Unsubscribe from any issue. Prefer a feed reader? Follow by RSS.