The conjecture, named after Scott Aaronson and Andris Ambainis and traced to a 2008 lecture by Aaronson, asks whether a quantum computer can gain an exponential advantage even when the input is a random string of zeros and ones with no pattern to exploit. According to a paper by David Turturean of Physical Superintelligence (PSI), the answer is no within the "query model," which counts how often an algorithm reads its input: for yes-or-no questions, a classical algorithm can approximate a quantum algorithm's probability of answering yes on most random inputs without exponentially more reads.
PSI said its internal research system, running instances of a non-public Anthropic model, found a complete proof on the third day of a run. The main theorem and its formulation of the original conjecture were formalized in Lean, a proof assistant, and checked by its kernel, and the proof was also reviewed by researchers.
The result limits input reads, not total computing time, so it does not set a general limit on the practical value of quantum computers. According to The Quantum Insider, it strengthens the case for quantum algorithm research on problems with mathematical or physical structure, such as Shor's 1994 factoring algorithm, which exploits the periodicity of a function. There is still room to tighten the theorem's mathematical bounds.