Physical Superintelligence (PSI) says an internal AI research system has proved the Aaronson-Ambainis conjecture, a problem in quantum complexity theory that has been open since 20081,2,3. The system ran a non-public Anthropic model on PSI's own infrastructure.
PSI announced the result in a thread on X on November 6 and published a research page the same day.
The conjecture, stated by Scott Aaronson and Andris Ambainis, concerns when quantum computers can be exponentially faster than classical ones. Most known dramatic quantum speedups, such as Peter Shor's 1994 factoring algorithm, rely on structured inputs that hide a repeating pattern. Whether quantum computers can achieve exponential speedups on random inputs, which almost never carry such structure, was unknown. Aaronson and Ambainis framed the question as a conjecture about polynomials and showed that, if true, quantum computers are at most polynomially faster on random inputs. Researchers have counted the conjecture among the central open problems of quantum complexity theory.
PSI describes the conjecture as "now a theorem". If the proof holds under outside scrutiny, it settles a foundational question about where exponential quantum speedups can occur and gives PSI's model a result the field can verify in Lean rather than take on trust. The proof has not yet undergone independent peer review, and PSI's claim rests on its own announcement.
PSI said instances of a non-public Anthropic model were used in the run, though the company did not disclose which model or further details about the system's architecture.
ANALYSIS The use of a non-public Anthropic model distinguishes this from results produced with generally available frontier systems and leaves outside observers unable to reproduce the pipeline independently until either the model or a full formal proof is released.
Anthropic, which separately struck a content licensing deal with AP earlier on November 6[2], has not commented publicly on PSI's claim in the available reporting.