An AI system running an Anthropic model settled an almost 20-year-old conjecture with implications for “Quantum Speedup”

A US startup called PSI (Physical Superintelligence), not to be confused with the Paul Scherrer Institute, says its AI system, running an unreleased Anthropic model, has proved the Aaronson-Ambainis conjecture, a problem in quantum computing theory that has been open since 2008.

Using Lean, software or an ITP that verifies mathematical arguments, the team checked the proof step by step. In plain terms, when a quantum computer answers a yes-or-no question about random data with no hidden pattern, an ordinary computer can predict its answer for almost every input without needing exponentially more reads of the data.

That matters because the big commercial promise of quantum computing rests on exponential speedups, where the gap over ordinary machines keeps widening as problems grow, and the theorem shows that, at least for yes-or-no questions measured in reads of the data, those only turn up when the data has a pattern to exploit, as in Shor’s factoring algorithm. Anyone promising exponential gains on messy, unstructured data now has to say where the pattern is. The paper has not been peer-reviewed yet, and neither Aaronson nor Ambainis had commented as of 7 November.

The announcement

On 6 November 2026, a US startup called Physical Superintelligence, which goes by PSI and describes itself as an AI-native physics laboratory, published a short research note announcing that it had proved the Aaronson-Ambainis conjecture. The conjecture is a precise mathematical guess that the computer scientists Scott Aaronson and Andris Ambainis wrote down around 2008, and for eighteen years it sat among the central open problems of quantum complexity theory, the branch of computer science that sorts problems by how much effort quantum and ordinary computers need to solve them.

PSI says an internal research system running instances of a non-public Anthropic model produced a complete proof on the third day of a run on the company’s own computing infrastructure, and that Lean, a proof assistant that checks every logical step of an argument, accepted it. The system was then given related open problems and improved its own result twice; Lean accepted the final version too, and PSI has published the paper and the full formal proof on GitHub.

Aaronson has been making a version of this argument public for twenty years, and his blog’s banner still tells visitors that quantum computers won’t solve hard problems instantly by trying all solutions in parallel. The new theorem puts a proof behind part of that warning, at least for yes-or-no questions on random data.

Quantum speedups explained

A quantum speedup is the saving a quantum computer offers over the best ordinary computer on the same problem. Complexity theorists measure it by how the work grows as the problem gets bigger, because a quantum machine that needs a thousand steps where an ordinary one needs a million is only worth having if the gap holds up as the input doubles, and doubles again.

A polynomial speedup, where the quantum machine’s effort is a fixed power of the ordinary machine’s, is modest. Lov Grover’s 1996 search algorithm is the standard example: it finds a marked item in an unsorted list of N entries in roughly the square root of N steps, so a million entries take fewer than a thousand steps (Grover’s paper). An exponential speedup is the big prize, because the ordinary computer’s effort roughly doubles every time the input grows by a fixed amount while the quantum computer’s climbs far more slowly, and the best-known example is Peter Shor’s 1994 algorithm for factoring, splitting a large number into the primes that multiply to make it, which runs in polynomial time on a quantum computer while the best known classical methods need close to exponential time, and which is why it threatens the RSA encryption that protects much of the internet (Shor’s paper).

The chart plots how many steps each growth type needs as the problem gets bigger, and since each step takes time, more steps mean a longer wait. Linear growth, sometimes called arithmetic growth because each step up in size adds the same amount of work, is the simplest polynomial, and it flattens out along with n² and n³ on this scale, while the exponential curves keep climbing and 2ⁿ crosses the line for a full day of computing at a billion steps a second once the problem reaches a size of about 46. In those terms, Grover’s algorithm moves search lower within the grey family, while an exponential speedup such as Shor’s moves a problem from a blue line down to a grey one.

Quantum hardware runs far more slowly than a conventional chip, and error correction, the machinery that protects qubits, the fragile quantum counterparts of ordinary bits, eats up extra qubits and operations. In 2021, Ryan Babbush and colleagues at Google concluded that those costs mean quadratic speedups like Grover’s will not deliver an advantage on early error-corrected machines unless error correction improves dramatically, and urged the field to look for bigger ones (their paper).

Every known exponential speedup depends on input structure. Shor’s algorithm uses the hidden periodicity of a sequence of numbers and Daniel Simon’s 1994 algorithm uses a secret string concealed inside a function, and in both the quantum computer arranges its amplitudes, the numbers it attaches to each possible outcome, so that they cancel for wrong answers and add up for the hidden pattern, which a measurement then reveals. Grover’s algorithm needs no structure at all, and in 1997 Charles Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani proved that its square-root saving is the most any quantum computer can get from completely unstructured search.

Between those two cases sit the problems whose data has no planted pattern but is also more than a single marked item in a list, and that is the territory of the Aaronson-Ambainis conjecture. It asks how much a quantum computer can save on typical random inputs for any yes-or-no question, and the answer, now proved, is at most a polynomial amount.

How the conjecture works

Complexity theorists count these speedups in queries, which PSI’s write-up calls looks, meaning the number of times a computer reads part of its input, pictured as a long string of 0s and 1s. An ordinary computer reads one bit per look, while a quantum computer’s look can be spread in superposition across many positions, with an amplitude attached to each one.

When the string is promised to repeat, as in Shor’s case, a quantum computer needs exponentially fewer looks than any ordinary ‘classical’ machine. The open question was what happens when there is no such promise, and the string is effectively random.

Aaronson first worked on that question around 1999, after Lance Fortnow suggested it in one of his papers, and by his own account he never solved it directly (Aaronson’s history of the problem). Around 2008, he noticed that the answer would follow from a statement about polynomials, sums of terms in which each term multiplies some of the input bits together, where the degree is the largest number of bits multiplied in any one term. The link was a 1998 result by Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca and Ronald de Wolf, who proved that if a quantum algorithm makes T looks at its input, the probability that it answers yes is exactly such a polynomial, of degree at most 2T, with a value that always stays between 0 and 1 (Beals and colleagues).

PSI’s note pictures the polynomial as a dial wired to a row of on-off switches, one for each input bit. Each small group of switches adds its own positive or negative amount to the reading when every switch in the group is on, and the needle never leaves the range from 0 to 1. A switch’s influence is how far the needle moves on average when that switch alone is flipped, and the variance measures how much the reading changes across all possible settings. Aaronson and Ambainis conjectured that whenever the reading varies at all, at least one switch has an influence of at least some fixed power of the variance divided by the degree, no matter how many switches the dial has.

If that holds, an ordinary computer that knows how the quantum algorithm’s dial is wired can predict its answer by playing twenty questions. It reads the most influential bit it has not yet seen, updates the dial, and repeats; once the reading barely varies over the remaining switches, it stops and reports the average reading as its prediction. The conjecture guarantees that, for any fixed margin of error, this ends after a number of looks that grows only like a fixed power of T, so on nearly every random input the ordinary computer keeps up with the quantum one without needing exponentially more looks.

PSI’s theorem confirms the guess, with the power in question worked out explicitly. Every earlier bound for general polynomials shrank exponentially as the degree grew, which was far too weak to rule out exponential quantum speedups.

Scott Aaronson

Scott Joel Aaronson was born in Philadelphia on 21 May 1981, took his bachelor’s degree at Cornell, where he first fell for quantum computing, and earned his PhD at the University of California, Berkeley under Umesh Vazirani, one of the founders of quantum complexity theory (Wikipedia). After postdoctoral spells that included the Institute for Quantum Computing at the University of Waterloo, he joined MIT’s electrical engineering and computer science faculty in 2007 and stayed nine years. In the summer of 2016, he moved to the University of Texas at Austin as a chaired professor of computer science and the founding director of its new Quantum Information Centre, where he still works; in 2026, he was elected to the US National Academy of Sciences.

Outside academia, he is best known as a writer. His blog, Shtetl-Optimized, has run since October 2005 and mixes complexity theory with long, often funny posts that take apart overblown quantum claims; his 2013 book Quantum Computing Since Democritus, published by Cambridge University Press, grew out of the lecture notes for a graduate course he taught. Quantum Zeitgeist has profiled him before, and his posts keep coming back to the point that a quantum computer gets its power from amplitudes interfering with one another, since a machine that merely held every answer at once would be no use to anyone.

Two of his ideas have since been tested on real hardware. In 2011 he and his student Alex Arkhipov proposed BosonSampling, a task in which particles of light pass through a network of beam splitters and the pattern of where they land is believed to be extremely hard for an ordinary computer to reproduce, and his ACM Prize citation credits that line of work with the theoretical foundations of the sampling-based quantum supremacy experiments that followed, including Google’s on a superconducting chip in 2019 and photonic experiments in China (Aaronson on the ACM Prize). In 2018 he proposed a certified randomness protocol, a way of using a quantum computer to produce random numbers that can be mathematically shown to be fresh, and in March 2025 a team from JPMorganChase, Quantinuum, Argonne, Oak Ridge and UT Austin demonstrated it in Nature on Quantinuum’s 56-qubit H2 machine, which Quantum Zeitgeist covered at the time.

In 2020, he won the ACM Prize in Computing, a mid-career award worth $250,000 that he joked on his blog was not the Turing Award but one he would happily take. From 2022 to 2024, he was on leave at OpenAI working on AI safety, where his best-known project was a statistical watermark for spotting text written by GPT models.

Andris Ambainis and the history of the problem

Andris Ambainis was born in Daugavpils, Latvia, in 1975, won a gold medal with a perfect score at the International Mathematical Olympiad in 1991 and, after a doctorate at the University of Latvia, took a second PhD at Berkeley in 2001 under Umesh Vazirani, who later supervised Aaronson too (Theory of Computing author note). He spent time at the Institute for Advanced Study in Princeton and the University of Waterloo before going back to Riga as a professor at the University of Latvia, and his 2003 quantum walk algorithm for element distinctness, the problem of checking whether any two items in a list are equal, remains a standard tool in quantum algorithm design (Belovs on Ambainis’s algorithm).

Aaronson has written that around 2008, while he was working out the link between quantum algorithms on random inputs and influences in polynomials, Ambainis made a breakthrough on a separate problem Aaronson had mentioned to him, about quantum speedups for symmetric problems such as finding collisions, and the two decided to write up both results together. The paper, The Need for Structure in Quantum Speedups, was first posted in 2009, and Aaronson has said the polynomial half was the weaker part, since reviewers pointed out that it reduced one unsolved problem to another.

Specialists in the analysis of Boolean functions, the mathematics of functions whose inputs are strings of 0s and 1s, took up the polynomial question anyway and named it the Aaronson-Ambainis conjecture. Aaronson recalls that Ryan O’Donnell and Guy Kindler took a crack at it and that he once got Terence Tao, the Fields Medal-winning mathematician, to spend an hour or two on it during a visit to UCLA (Aaronson’s 2019 post).

In November 2019, Nathan Keller and Ohad Klein posted a preprint claiming a proof, titled Quantum Speedups Need Structure in a nod to the original paper, and Aaronson blogged that he expected it to hold up. About two weeks later, the authors withdrew it after Paata Ivanisvili found what looked like a fatal flaw in one of its lemmas, and Aaronson’s post still stands under its original title, which still gives the conjecture’s dates as 2008 to 2019.

Partial results trickled in over the following years, including a 2023 plan of attack from Shachar Lovett and Jiapeng Zhang that depended on one inequality they could not prove, and one in September 2026 from Ivanisvili, the man who had spotted the 2019 flaw. In August 2026, Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan of Stanford proved the conjecture’s prediction for quantum algorithms that read their input in a fixed number of parallel rounds (Quantum Speedups Require Structure or Depth), which left only the general case open.

PSI and the proof

PSI came out of stealth on 1 September 2026 with a $58 million seed round led by Breakthrough Energy Ventures (PSI’s launch announcement). The Cambridge, Massachusetts company was founded by Matt Pines, Alex Klokus and Alexander Wissner-Gross, and its main product is Emmy, a team of AI virtual physicists whose first commercial focus is designing more efficient data centres, which is some distance from quantum complexity theory.

The work was led by David Turturean, a member of PSI’s technical staff, who built the research system, scoped the problem and takes responsibility for the paper, the first draft of which the model wrote. PSI says the system, running instances of an unreleased Anthropic model it has not named, produced a full proof on the third day of the run, and Lean then checked it; every definition and step passed through a small trusted program called the kernel that rejects anything that does not follow. The physicists Jim Halverson and Phiala Shanahan, who advise PSI, audited the proof and commented on the Lean version respectively.

The argument follows the 2023 plan by Lovett and Zhang (their paper) and fills the gap they left by proving a different inequality, using a determinant, a single number computed from a square grid of numbers, to pair up switch settings one to one. That pairing sharpens one David Reimer used in a 2000 proof in probability theory, and it supplied the step the earlier plan had been missing.

The Stanford group that settled the fixed-round case in August has been reading the full proof, sending PSI comments and writing a shorter version for specialists. In a statement published by PSI they described it as a major result that settles a conjecture standing for decades, and said the argument draws on Boolean function analysis and probabilistic combinatorics, with everything brought together in a rather magical way.

The paper has not yet been through journal peer review. Lean guarantees only that the theorem as written in Lean has been proved, so experts still have to confirm that the formal statement says exactly what Aaronson and Ambainis conjectured, and to check the parts of the paper outside the formal proof. As of 7 November neither Aaronson nor Ambainis had published an assessment, although a reader had already posted a link to PSI’s note under Aaronson’s 2019 post about the withdrawn Keller and Klein proof, asking for his view.

The existential threat to quantum computing

Every claimed quantum speedup carries a risk that a cleverer classical algorithm, one nobody has found yet, could do the same job almost as quickly, in which case the advantage would only ever have measured how hard people had looked. Nobody can rule that out for the problems the industry cares about most, such as factoring or simulating molecules, because proving that no fast classical method exists would at the very least require proving that P, the set of problems an ordinary computer can solve efficiently, is different from PSPACE, the larger set that can be solved with a modest amount of memory but unlimited time. That question has resisted every attempt for decades, so for now quantum advantage on real-world problems rests on evidence and expert judgement, with no proof.

The worry has history behind it. In 2018, Ewin Tang, then an undergraduate at UT Austin working on a project Aaronson had set her, tried to prove that a well-known quantum algorithm for recommendation systems, the software that suggests products from a customer’s past choices, could not be matched classically, and instead found a classical algorithm that was only polynomially slower. Her method, which came to be called dequantization, went on to strip claimed exponential speedups from several other quantum machine learning algorithms, and classical simulation has kept chipping at hardware claims as well, as when IBM and IonQ researchers in 2024 found a way to compute a single output of Harvard and QuEra’s 48-qubit circuits in about 2.6 thousandths of a second, a result Quantum Zeitgeist reported at the time and has followed since under classical simulation.

The strongest reassurance is that Shor’s factoring algorithm has stood since 1994 without a classical rival, even though anyone who found one could break the RSA encryption behind online banking, which makes it one of the most heavily motivated searches in computer science. Some quantum advantages are also proved outright in restricted settings, including the 2018 result by Sergey Bravyi, David Gosset and Robert König showing that shallow quantum circuits, ones only a few layers of operations deep, can solve a problem that no classical circuit of fixed depth, built from ordinary logic gates with a limited number of inputs, can. The Aaronson-Ambainis theorem belongs to the same effort to replace hunches with proofs, and it draws the line clearly: classical computers keep pace on unstructured data, while structure is where quantum speedups survive.

Theorem-proving software could push in either direction. Interactive theorem provers such as Lean check proofs that people or AI models write, while automated provers search for proofs on their own, and PSI’s system combines the two by having an AI model write arguments that Lean then verifies. If systems like that are turned on quantum complexity theory at scale, they may find more dequantizations and close off speedups that companies are counting on, or they may prove the lower bounds that show certain quantum advantages are real, and both outcomes would give engineers and investors firmer ground than they have now.

Markets have been gloomy anyway. Over the thirty days to early November, IonQ fell 31.7 per cent, D-Wave 35.7 per cent and Rigetti 28 per cent, according to Zacks figures carried by Yahoo Finance, and on 2 November B. Riley cut its price targets on the group by up to 32.5 per cent, citing funding and dilution worries while keeping Buy ratings (Yahoo Finance). On 5 November, the day before PSI’s announcement, D-Wave and Rigetti dropped 18 per cent in morning trading and IonQ 15 per cent, with no D-Wave news behind the slide as a sell-off in chip stocks spread (Yahoo Finance), before the group bounced back the next day, with IonQ and Rigetti up about 18 per cent and D-Wave about 16 per cent after IonQ’s results beat expectations. Zacks blamed the October slide on weaker appetite for speculative technology stocks, stretched valuations and doubts about how long commercial adoption will take.

What the result means

Theorists get an explanation for decades of failed attempts to show a quantum computer pulling exponentially ahead on random black-box problems, where an imaginary device called an oracle answers questions instantly and both kinds of machine get the same help. Aaronson wrote in 2019 that a proof of the conjecture would explain why nobody had managed it with a random oracle, only with non-random ones, and now it does.

For businesses, the effect is less direct, since the theorem counts data reads and says nothing about runtime on real hardware, and Grover-style polynomial gains are still allowed. What it rules out is exponential gains on patternless data, so a company claiming those has to show where the hidden structure is, and Entangled Future’s quantum company directory and Quantum Zeitgeist’s quantum advantage coverage keep track of who is claiming what.

The theorem promises only that the ordinary computer’s extra reads grow as some fixed power of T, which can still mean a lot of extra work. Aaronson remarked in 2019, about the eighteenth-power overhead in the withdrawn Keller and Klein argument, that blowups like that can almost always be cut down a long way with further work, and PSI’s system has already improved its own result twice.

PSI has put up a Lean repository anyone can rerun and named a researcher to take responsibility for the paper. The next real tests are the Stanford group’s write-up and whatever Aaronson and Ambainis make of it.

PSI says it has already set its system to work on related open problems. It has not said which ones, but one natural family is studied in a September 2026 paper by Uma Girish, Kunal Mittal, Barak Nehoran and Ran Raz on distributional variants of the Aaronson-Ambainis conjecture, which PSI’s note cites and which, as its title suggests, looks at versions of the question where the random input follows other probability distributions.