A quantum computer will not be able to achieve an exponential speedup over an ordinary one when solving problems where the input data are nearly random and lack any special mathematical structure. This is not just another limitation — it is a proof obtained by artificial intelligence.
In November 2026, the US startup Physical Superintelligence (PSI) announced a proof of a conjecture that Scott Aaronson of the University of Texas at Austin and Andris Ambainis of the University of Latvia had formulated in 2011. The conjecture asserted that for low-degree polynomials taking values from 0 to 1 on the Boolean cube, there is always a variable with a noticeable influence. The proof was found by PSI's in-house research system based on a non-public Anthropic model. The full text passed verification in the Lean system, and the exposition was prepared by Stanford researchers Guy Blank, Jordan Docter, Carmen Strassle and Li-Yang Tan.
The system worked for four days: first it obtained a complete proof, then improved it twice, and each version was accepted by Lean without errors. This is not an experiment on a quantum processor but a purely mathematical proof in the field of query complexity theory. It shows that a quantum algorithm making T queries to the input can be simulated classically with high accuracy on most random inputs, using only a polynomial number of queries.
Imagine a huge warehouse with billions of boxes, where the needed item lies in a random place with no clues. Classical search goes through the boxes one by one. A quantum one could, it seemed, look into all of them at once — but the proof shows that without special structure, as in Shor's algorithm for factoring, such "peeking" yields only a polynomial speedup, not an exponential one. The influence of a single variable in a polynomial guarantees that a random input can almost always be predicted from a small number of bits.
The result changes ideas about the limits of quantum supremacy. It is now clear that for problems without built-in structure — random graphs, random functions — an exponential advantage should not be expected. Quantum computers retain their advantage where structure exists, as in cryptography or optimization with special properties. This does not cancel the practical construction of devices, but it directs efforts toward the search for precisely such structured problems.
An article in New Scientist dated 12 November 2026 and a preprint on arXiv dated 8 November describe in detail the course of the proof and its implications for the relationship between the classes BPP and BQP in the world of random oracles.
Quantum supremacy is now more clearly delineated: it is real, but it requires not randomness but a hidden regularity.


