Physical Superintelligence (PSI) has announced a proof of the Aaronson-Ambainis conjecture, a question about quantum speedups that had been open since 2008. The company says its internally developed research system found the proof using a non-public Anthropic model, and the Lean proof assistant accepted it.
According to PSI, the system produced a complete proof during the third day of a run. After being assigned related problems, it improved the result twice, and Lean accepted the final version.
The mathematical claim is narrower than a general ceiling on quantum computing: it concerns how often an algorithm reads its input, not all the computing work needed to produce an answer.
A limit on input reads, not computing time
The conjecture, named for Scott Aaronson and Andris Ambainis, concerns a framework called the query model. An ordinary computer reads one bit of input per query; a quantum query can be spread in superposition across many positions, PSI explains.
The reported proof would guarantee that an ordinary computer can approximate a quantum algorithm’s probability of answering yes, within a small error, on all but a small fraction of uniformly random inputs. For a fixed error and excluded fraction, the number of classical queries grows at most as a fixed power of the quantum query count, rather than exponentially.
That does not make the two computers equally fast. As Matt Swayne explains in The Quantum Insider, the query count excludes the work performed between reads. A classical algorithm could need relatively few reads and still require substantial computation.
The mathematical bridge
PSI’s explanation connects those queries to polynomials, mathematical expressions describing how the input bits affect the probability of a yes answer. After T quantum queries, that probability is a polynomial of degree at most 2T, with values between zero and one.
The conjecture guarantees that when such a polynomial varies meaningfully across inputs, at least one bit has a sufficiently large influence. Here, influence means the squared change caused by flipping that bit, averaged over all inputs. That guarantee lets a classical algorithm keep choosing informative bits to read until it can estimate the probability accurately enough, according to PSI’s account.
The company says the proof follows a plan developed by Shachar Lovett and Jiapeng Zhang, replacing an inequality they had left conjectural with a new inequality.
