After 19 years, a research system at Physical Superintelligence has proven the Aaronson-Ambainis conjecture, a longstanding problem in quantum computing, the company says. The system, using a non-public model from Anthropic, completed a full proof within three days, with each step formally verified by the Lean proof assistant.
This result settles a fundamental question about the limits of quantum speedup on random inputs, determining that quantum computers are at most polynomially faster than ordinary ones. “This is a huge result,” says Guy Blanc of Stanford University, “It resolves a decades-old conjecture with important implications for the nature of problems that admit quantum speedups.”
Aaronson-Ambainis Conjecture Resolved by Physical Superintelligence System
Using existing work from Shachar Lovett and Jiapeng Zhang to replace a previously conjectured inequality with a novel inequality proven within the manuscript, Physical Superintelligence (PSI) verified a critical component of its proof. This substitution was not merely a workaround. The team paired switch settings one-to-one, using a determinant to establish the validity of the new inequality and complete the proof of the Aaronson-Ambainis conjecture.
The approach demonstrates a capacity to not only discover solutions but to integrate and validate them against established mathematical frameworks. Lean, a proof assistant, formally accepted the system’s initial proof on the third day of computation, a process that extended beyond simple acceptance to include verification of two subsequent refinements. This rigorous validation emphasises the system’s ability to produce results that meet the standards of formal mathematical proof, where every step is subject to computer-checked scrutiny.
The system had a complete proof of the conjecture during the third day of the run, and Lean accepted it. The team then began work on related open problems.
Quantum Speedup Limits Defined by Polynomial Complexity
The proven Aaronson-Ambainis conjecture establishes a mathematical boundary on quantum speedup by linking it to the behavior of polynomials, specifically how their values change with single bit flips. Researchers at Physical Superintelligence demonstrated that an ordinary computer can accurately predict the output of a quantum computer, up to a small error, for nearly all possible inputs, provided the polynomial’s degree remains limited, according to the company.
This prediction relies on estimating a probability. The team showed this estimation requires a number of computational “looks” that grows as a fixed power of the initial number of looks, not exponentially. This finding builds upon work by Beals, Buhrman, Cleve, Mosca and de Wolf, who previously established that after a certain number of looks, the quantum computer’s probability of a “yes” answer becomes a polynomial with a degree no higher than twice the number of looks.
The PSI system’s proof centers on a conjecture about the “influence” of each bit on this polynomial, visualizing it as a dial connected to on-off switches representing the bit values. Each group of switches contributes to the dial’s reading, which always falls between zero and one, and the degree of the polynomial dictates the maximum size of these groups. Understanding influence is key; it represents the average change in the polynomial’s value when a single bit is flipped.
The implication is that quantum computers cannot achieve exponential speedup on yes-or-no questions unless the input string possesses a rare, specific pattern. The number of computational steps required by the classical computer to simulate the quantum process does not increase exponentially with the problem size, effectively defining a limit to quantum advantage on random inputs. This result doesn’t negate the potential for quantum computers to solve certain problems faster. But it clarifies the conditions under which that speedup is possible and provides a rigorous mathematical framework for understanding those limits.
This is a huge result. It resolves a decades-old conjecture with important implications for the nature of problems that admit quantum speedups. The proof draws on and extends several lines of work in the analysis of boolean functions and probabilistic combinatorics. Everything is brought together in a rather magical way.
The Physical Superintelligence (PSI) system not only generated a proof of the Aaronson-Ambainis conjecture, but also refined it through two subsequent iterations, each formally accepted by the Lean proof assistant. Lean’s acceptance process involved a complete verification of each step in the proof, ensuring its logical soundness.
Influence of Bits Determines Quantum Look Complexity
Quantifying how much a single bit within the input string influences the final outcome of a quantum computation, a concept known as “influence”, forms the core of the proof. This influence isn’t simply a matter of whether the bit is on or off, but rather the degree to which changing that bit alters the probability the quantum computer reports. Researchers demonstrated that, during the simulation process, the ordinary computer can strategically focus on bits exhibiting the largest influence.
This approach relies on a key characteristic of the polynomials representing the quantum computation’s probability. These polynomials are limited in degree, specifically to at most 2T, where T represents the number of looks the quantum computer takes. Each group of at most d switches, representing the bit values, contributes to the polynomial’s value, and the system’s ability to identify high-influence bits hinges on this degree limitation.
Once the ordinary computer identifies a point where further bit flips cause minimal change to the polynomial’s reading, it can accurately predict the quantum computer’s output, the company says. The system’s method effectively mimics the quantum computer by estimating this probability, but it does so without requiring an exponential number of looks. The team’s success in establishing this new inequality allowed them to replace a previous, less effective one, enabling the simulation to proceed efficiently.
