AI-assisted proof establishes a limit on quantum speed-ups

An AI-assisted proof has settled a longstanding question about when quantum computers can dramatically outperform ordinary computers. Physical Superintelligence, or PSI, announced the result on 6 November, and researchers have since published an explanation of the mathematics.

The result establishes a boundary for yes-or-no questions about mostly random inputs. When performance is measured by how often an algorithm reads its input, a classical algorithm can approximate a quantum algorithm’s answer probability with at most a polynomial increase in those reads. A polynomial advantage can still be substantial; the theorem pins down a particular limit on much larger advantages.

The proof counts reads of the input

The Aaronson–Ambainis conjecture concerns quantum query complexity: the number of times an algorithm accesses information. Picture a long string of bits, each either zero or one. A classical query reads a position. A quantum query can access positions in superposition, allowing its calculation to combine information differently.

Scott Aaronson and Andris Ambainis connected the problem to mathematics about polynomials. The newly proved result lets a classical algorithm estimate the probability that a quantum algorithm answers yes, with a fixed small error, on all but a small fraction of uniformly random bit strings. If the quantum algorithm makes T queries, the classical query count grows as a fixed power of T for fixed accuracy requirements.

The independent exposition, published on 8 November by Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan, spells out that consequence. The quantity being bounded is the number of input queries. The classical calculation between those queries can itself be expensive, so the guarantee has a specific meaning when assessing real computer performance.

One influential bit unlocks the argument

The mathematical breakthrough proves that a bounded, low-degree polynomial with appreciable variation has an influential input variable. A polynomial combines variables through additions and multiplications. Here, its inputs are bits and its output stays within a fixed range.

A useful picture is a dial connected to switches. The switches are the input bits; the dial shows the polynomial’s value. Influence measures how much flipping one switch changes that value, squared and averaged across all possible inputs. The theorem guarantees an input whose influence is sufficiently large, even when the number of inputs grows.

Why does this help? A quantum algorithm’s probability of answering yes can be represented by a polynomial. A classical algorithm can inspect influential bits in succession, gaining enough information to predict that probability for most inputs. The original paper by David Turturean supplies the bound connecting the polynomial’s degree, its variation and an influential variable.

AI supplied the proof, and Lean checked it

PSI credits a research system developed by researcher David Turturean, working with a non-public Anthropic model. The company says the system found a complete proof during the third day of a run. Lean, a mathematical proof assistant, accepted it, and the system subsequently improved the result twice.

The public repository contains the paper, the formal statement and the proof. PSI reports checking the formalisation with separate implementations of the proof-checking machinery. These checks concern whether the stated mathematical claim follows from the specified foundations; researchers can also inspect how that claim matches the original conjecture.

Human responsibility is explicit. Turturean reviewed the paper and takes responsibility for its correctness. Jim Halverson audited the proof, and Phiala Shanahan commented on the formalisation. The four exposition authors worked to understand the argument and present its main steps; their paper says they received no financial compensation from PSI or Anthropic.

Structure still opens the door to dramatic speed-ups

Quantum algorithms retain powerful routes through structured problems and other kinds of computation. In his 8 November explanation, Aaronson points to Shor’s factoring algorithm, which exploits periodic structure, and to quantum simulation of physics and chemistry.

The type of answer also changes the problem. A decision problem asks for yes or no. Search and sampling ask a computer to produce something, and their quantum advantages require their own analysis. Aaronson highlights research demonstrating exponential quantum speed-ups for certain search problems even with random oracles.

For researchers designing algorithms, the theorem sharpens a practical question: which structure does the computation exploit, and what resource does it save? For AI research, it provides a concrete example of a system producing a new proof whose steps and final statement are available for mathematical scrutiny. The lasting result is a more precise map of where quantum advantages arise.