Physical Superintelligence, a company known as PSI, says an AI research system has settled the Aaronson-Ambainis conjecture, one of the long-standing open questions about what quantum computers can and cannot do. The system, built on a non-public model from Anthropic, produced a complete proof within three days, and each step was formally verified by the Lean proof assistant, Quantum Zeitgeist reports.
The proof answers a basic question about the limits of quantum speedup. On random inputs, it shows, a quantum computer can be at most polynomially faster than an ordinary computer, not exponentially faster. Guy Blanc of Stanford University called it a resolution of a decades-old problem with important consequences for which problems allow quantum speedups.
"This is a huge result."
— Guy Blanc, Stanford University
How the proof was built
At the heart of the work is a new inequality. The proof needed an inequality that had previously only been conjectured. PSI's system swapped it for a fresh inequality that it proved inside the manuscript, drawing on existing research by Shachar Lovett and Jiapeng Zhang.
To establish that new inequality, the team matched pairs of switch settings one to one and used a determinant, a standard tool from linear algebra, to show the inequality holds. With that piece in place, the full proof of the conjecture followed.
According to the company, Lean accepted the system's first complete proof on the third day of the run. The system then refined the proof twice, and Lean accepted both versions. After that, the team moved on to related open problems.
What the conjecture says
The conjecture links quantum speedup to the behavior of polynomials. Earlier work by Beals, Buhrman, Cleve, Mosca and de Wolf showed that when a quantum computer examines its input a certain number of times, call it T, its probability of answering yes can be written as a polynomial of degree at most 2T.
The proof focuses on the influence of each input bit on that polynomial. Quantum Zeitgeist describes the polynomial as a dial wired to a row of on-off switches, one per bit. Groups of switches move the dial, which always reads between zero and one, and the polynomial's degree caps how large those groups can be. A bit's influence is how much the dial moves, on average, when that single switch is flipped.
A classical computer can keep up
PSI's result shows that an ordinary computer can predict a quantum computer's output, up to a small error, for nearly all possible inputs, as long as the polynomial's degree stays limited, the company says.
The ordinary computer does this by estimating the quantum computer's probability of saying yes. It concentrates on the bits with the largest influence, and once flipping further bits barely moves the dial, it can make its prediction. The number of input checks it needs grows only as a fixed power of the quantum computer's checks, not exponentially.
The proven inequality is what makes this efficient. It replaced a weaker earlier one and allows the simulation to run without an explosion in cost.
Why it matters
For quantum computing, the result draws a clear line. Quantum machines cannot get an exponential speedup on yes-or-no questions unless the input carries a rare, specific pattern. That does not rule out quantum computers beating ordinary ones on particular problems; it spells out the conditions under which such gains are possible, and gives researchers a rigorous framework for them.
For AI, the claim is just as notable: a model-driven system, according to PSI, took a 19-year-old open problem to a computer-verified proof in three days. The account comes from the company's own announcement, published on its research site. The next things to watch are independent review of the proof by mathematicians and progress on the related open problems PSI says it has begun working on.