# Aaronson-Ambainis conjecture becomes a theorem after AI research system finds proof > A decades-old quantum computing conjecture has been proved by an AI system, confirming that quantum computers cannot achieve exponential speedups over classical machines on random, unstructured data. - Type: AI news - Page: https://completeaitraining.com/news/aaronson-ambainis-conjecture-becomes-a-theorem-after-ai/ - Published: 2026-11-07 - Updated: 2026-11-07 - Author: Jeroen Erne - Jobs: Education, Healthcare, Science and research - Reading time: 3 min A decades-old conjecture that defines the limits of quantum computing has been settled by an AI research system. The proof of the Aaronson-Ambainis conjecture, completed in November 2026 by a system developed at Physical Superintelligence (PSI) using a non-public Anthropic model, confirms that quantum computers cannot achieve exponential speedups over classical computers when working with random, unstructured data. The conjecture, open since 2008, was considered one of the central problems in quantum complexity theory. Scott Aaronson and Andris Ambainis originally posed it to determine whether quantum algorithms like Shor's famous factoring method owe their power to hidden structure in the input. The new proof says they do. #### What the conjecture actually says Peter Shor's 1994 algorithm factors large numbers exponentially faster than any known classical method. But it works because the problem contains a repeating pattern. The question Aaronson and Ambainis asked was whether quantum computers could be exponentially faster on random inputs, which almost never have such structure. They reduced the question to a statement about polynomials. After a quantum computer examines its input T times, its probability of answering "yes" becomes a polynomial in the input bits, with degree at most 2T and values between 0 and 1. The conjecture stated that in any such polynomial, some input bit must have large **influence** \- flipping it changes the output substantially, on average. If true, a classical computer can predict the quantum computer's behavior by reading only the most influential bits, needing at most polynomially many looks rather than exponentially many. The PSI system proved that for any non-constant polynomial of this type, some bit has influence at least roughly (variance/degree)⁷. That bound is enough to rule out exponential quantum speedups on random yes-or-no questions. #### How the proof came together The research system, developed internally at PSI, found the complete proof during the third day of its run. The proof assistant Lean verified every step. The system then improved the result twice more, with Lean accepting the final version. The proof follows a plan laid out by Shachar Lovett and Jiapeng Zhang, which required proving one remaining inequality. The PSI system replaced that conjectured inequality with a new one, proved using a pairing of input settings derived from a determinant. The work also draws on David Reimer's Butterfly Lemma and results from several other research groups. In August 2026, Guy Blanc, Jordan Docter, Carmen Strassle, and Li-Yang Tan of Stanford University had proved a special case of the conjecture for quantum algorithms restricted to a fixed number of parallel rounds. They have since reviewed the full proof. "This is a huge result," they wrote. "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 math behind the milestone Think of the polynomial as a dial wired to on-off switches, where each switch represents one bit of the input string. Groups of switches contribute to the dial's reading, which always stays between 0 and 1. The influence of a bit measures how much the dial's reading changes, on average, when that switch is flipped. The classical simulation method works by repeatedly finding an unread bit with large influence, reading it, and updating the prediction. Once the remaining variance is small, the algorithm stops and outputs the average reading. The conjecture guarantees that until that point, some unread bit always has large enough influence to keep the process efficient. Earlier bounds for general polynomials decayed exponentially with degree. Special cases had been proved - for polynomials taking only values 0 or 1, the conjecture followed from earlier theorems by O'Donnell, Saks, Schramm, Servedio and by Nisan and Szegedy. Other partial results came from Montanaro, Ivanisvili, Bansal-Sinha-de Wolf, and Escudero Gutiérrez. The new proof handles the general case. #### Why this matters for science and research professionals The result does not make quantum computers less interesting. It sharpens the picture of where they excel. For researchers working on quantum algorithms, the message is clear: look for structure. Exponential speedups require inputs with rare patterns - periodicity, hidden subgroups, or other mathematical properties that a quantum computer can exploit. Random or unstructured problems will not yield those dramatic gains. The proof also demonstrates that AI research systems can now tackle open problems in theoretical computer science that resisted human efforts for nearly two decades, with machine-checkable verification of every logical step. --- This is the Markdown form of https://completeaitraining.com/news/aaronson-ambainis-conjecture-becomes-a-theorem-after-ai/. The whole site is mapped at https://completeaitraining.com/llms.txt.