Skip to content
Quantum.world

The Signal

Aaronson Says He Believes AI Proof of Quantum Conjecture Is Correct

Scott Aaronson says he believes a proof of the Aaronson-Ambainis Conjecture announced by Physical Superintelligence is correct, though he has not yet understood it himself. He says the result rules out a limited class of possible quantum query speedups, not quantum supremacy broadly or algorithms such as Shor’s.

Aaronson Says He Believes AI Proof of Quantum Conjecture Is Correct

PSI’s Proof and Aaronson’s Assessment

Scott Aaronson says he believes a proof of the Aaronson-Ambainis Conjecture announced by Physical Superintelligence (PSI) is correct, while making clear that he has not yet understood the proof himself. In a Nov. 8 post on Shtetl-Optimized, Aaronson reported that PSI had announced the result late the previous week. He said the effort was led by David Turturean and Jim Halverson at the startup.

PSI said it obtained the proof using a proprietary research harness on an internal Claude model. Aaronson wrote that he did not know what role the harness played compared with the model. He gave two reasons for his current confidence: a Lean certificate, and human experts who had already examined and understood the proof. “I haven’t yet understood the proof, although I hope to,” he wrote.

Aaronson also pointed readers to an exposition by Guy Blanc of MIT and Jordan Docter, Carmen Strassle and Li-Yang Tan of Stanford. He described it as a useful starting point for readers seeking to study the argument in greater depth. He said PSI’s own blog post was written clearly enough that he did not need to add much more explanation of the announcement.

What the Conjecture Says

The conjecture concerns degree-d polynomials in n Boolean variables that map inputs to values between zero and one and have constant variance. It predicts that some variable must have influence at least 1/poly(d). Aaronson and Andris posed it in 2009. The proof announced by PSI is reported as establishing a specific lower bound of approximately 1/d6.

A variable’s influence, in this context, measures how much changing that input can affect the polynomial’s value. Aaronson says he and Andris cared about the conjecture partly because they proved it would imply there is no superpolynomial advantage for quantum over classical query complexity on decision problems that work for most Boolean inputs. The implication concerns a particular setting for comparing how many oracle queries the two kinds of algorithms need.

The argument draws on a 1998 result by Beals and co-authors: if a quantum algorithm makes T queries to an oracle, its probability of accepting can be expressed as a polynomial in the oracle’s bits, of degree at most 2T. If the conjecture holds, Aaronson and Andris’ reasoning uses influential variables in that polynomial to construct a classical simulation. The simulation queries influential variables repeatedly until the polynomial is nearly constant, allowing it to learn the algorithm’s answer with high probability over most inputs, using a number of queries polynomial in T.

A Limited Implication for Quantum Computing

Aaronson connects the conjecture’s implication to the question of whether P and BQP can be separated relative to a random oracle, a question raised by Fortnow and Rogers in 1998. He stresses that the result does not rule out quantum speedups in general. Rather, it rules out a potential class of speedups for yes-or-no properties of exponentially many random bits, running superpolynomially faster than any classical algorithm.

That limit does not affect Shor’s factoring algorithm, Aaronson writes, because its key internal step uses a highly non-random, periodic oracle. Nor does he see an effect on quantum simulation of physics and chemistry, which generally does not depend on oracle algorithms. He also points to work by Yamakawa and Zhandry showing that exponential quantum speedups can occur for NP search problems relative to random oracles. Aaronson’s account therefore treats the proof as a result about a specific conjecture and a specific class of query problems, not as a verdict on quantum computing as a whole.

A Longstanding Open Problem

Aaronson says the conjecture became a central open problem in quantum query complexity, drawing interest from researchers who were focused on the polynomial question itself as well as its implications for quantum computing. Researchers had proved special cases, he writes, but a proof of the full conjecture remained a major goal. He also recalls a failed attempted solution that he discussed on his blog in 2019.

He describes his reaction to the announcement as mixed: satisfaction that the conjecture appears to be true, awe at AI’s ability to address open problems, disappointment that humans did not solve it first, and fatigue at the pace of new results. His assessment remains qualified: he believes the proof is correct based on the formal certificate and expert review, while saying he still hopes to understand the argument himself.

Source

  1. Shtetl-Optimized

Related stories

Explore

More articles