A proof of Aaronson‑Ambainis conjecture.
* Physical Superintelligence (PSI) announced that its automated research system used an unreleased, non-public Anthropic model to prove the conjecture—a major open problem in quantum complexity theory and computing speedups that had remained unsolved since 2008.
* According to PSI, the AI system successfully generated a complete proof by its third day of operation, and the final proof was formally checked and verified using the Lean interactive theorem prover.
* The result sheds light on the exact conditions under which quantum computers hold an exponential advantage over classical computers, while also highlighting the performance gap between advanced internal AI research models and those currently available to the public.
Notes:
The (AA) conjecture, posed by Scott Aaronson and Andris Ambainis in 2008, addresses a fundamental question in theoretical computer science: When can a quantum computer run exponentially faster than a classical computer, and when is that exponential speedup impossible?
To understand the conjecture without getting lost in mathematical physics, it helps to look at how computer scientists evaluate quantum speedups through the Query Model (or “black-box” model).