Quantum Supremacy Is a Well-Defined Speedup, Not a Useful Task

Aaronson says the term 'quantum supremacy' was coined by John Preskill in 2012, though not everyone likes it and 'quantum computational advantage' is sometimes preferred. The underlying idea goes back to the early 1980s, when Richard Feynman, David Deutsch, and others began discussing quantum computing. In its broadest form, supremacy refers to the historical point when a quantum computer first performs some well-defined task much faster than any known algorithm running on any available classical computer.

Aaronson stresses that the task does not have to be useful. What matters is that it be well-defined: it must have right and wrong answers that can be known independently of the device. That independence is what lets researchers run the quantum device and then check whether it produced the right answer.

Aaronson clarifies that anything a quantum computer can do, a classical computer can eventually do too. A classical machine could, in principle, store the entire quantum state as a list of amplitudes and update it with linear algebra. The catch is that this simulation is exponentially slower, so quantum computers do not enter some magical realm outside Alan Turing's definition of computation.

They do not solve the halting problem or any other uncomputable problem. What they are thought to change is what is efficiently computable. Since the 1960s, 'efficient' in computer science has been a code word for polynomial scaling: time should grow like the input size raised to some power, not exponentially with input size.

Aaronson lays out three requirements for a convincing demonstration. First, the quantum computer must be faster in literal seconds on a well-defined problem. Second, researchers must believe the quantum algorithm has better scaling, with classical cost growing exponentially while quantum cost grows polynomially. Third, the observed speedup must be explainable only by that scaling behavior, not by an incidental hardware advantage.

He gives the example of a real problem solved by a quantum computer with roughly 50 qubits. No one should be able to explain the result except by noting that the device involved a quantum state with 2^50 amplitudes, while classical simulation would require tracking 2^50 numbers. The intuition is that if 50 qubits already produce that gap, moving to 100 qubits should make the quantum advantage even larger.

Aaronson notes that quantum supremacy does not require error correction. The field may not yet have true scalability or fault tolerance, but a supremacy demonstration is enough by itself to refute skeptics who said a quantum computer would never outperform a classical computer at anything. That is the context, he says, for the news about Google's experiment.

The experimental path came from work Aaronson and his students pursued over the previous decade. Around 2011, he and Alex Arkhipov at MIT—independently of Bremner, Jozsa, and Shepherd—realized that proving a quantum speedup becomes much easier if one switches from problems like factoring, which have a single right answer, to sampling problems. The goal is no longer to produce one correct output but to sample from a specified probability distribution.

In a sampling problem, the computer outputs a sample from a distribution over strings, such as strings of 50 bits. There are many possible valid outputs, and a perfectly running device might never produce the same output twice, but some outputs are supposed to be likelier than others. When the host asks whether there is a set of valid outputs, Aaronson clarifies that the target is a specific distribution.

With today's noisy quantum computers, Aaronson explains, one can apply a randomly chosen sequence of operations in a precisely specified random way. Repeating the exact same sequence produces another sample from the same distribution. The process creates a lot of garbage, but it is very specific garbage whose statistical structure can be analyzed.

Google's device had 53 qubits, so there were 2^53 possible outputs. Interference made some amplitudes smaller and others larger, meaning some outputs were likelier than others even though all were exponentially unlikely. Aaronson describes some outputs as perhaps two or three times likelier than others, which defines the probability distribution the experiment was trying to sample from.

Aaronson and his students, together with the Google team, developed statistical tests to check the outputs and gather evidence that a hard problem was being solved. Google used a test called the linear cross-entropy benchmark. Its drawback is that it requires a classical calculation over 2^53 possibilities—about nine quadrillion.

That calculation is just barely possible, Aaronson says, on Summit at Oak Ridge National Laboratory, the largest supercomputer currently on Earth. Ironically, the experimenters did not want 100 qubits: with 100 qubits they would not know how to verify the results. They wanted enough qubits that the biggest classical computers would have to sweat but could still keep up, which is part of why 53 was chosen.

Aaronson adds that 53 qubits also reflected where Google's hardware was in scaling at the time. That point will soon be passed, and larger sampling experiments will become less interesting because their results cannot be verified. The field will then have to switch to other types of computation.

The benchmark takes the generated samples—a very small subset of all possible samples—and uses a classical computer to calculate the probabilities they should have had. It then checks whether those probabilities are larger than the mean, meaning the quantum computer is biased toward the strings it is supposed to favor. In that sense, the test asks whether the device is sampling from the intended distribution rather than producing arbitrary outputs.

The crucial question is how to know a classical computer could not have quickly produced the same samples. Aaronson says we do not know for sure, because this reaches complexity-theory questions of the magnitude of P versus NP. We cannot definitively rule out fast classical algorithms for simulating quantum mechanics or experiments like these, but we can give evidence against that possibility. That evidence was the main thrust of work by Aaronson and colleagues over the previous decade and led to Google deciding around 2015 to run the experiment.

Most of the evidence is mathematical, but there is an empirical component as well. Researchers have to try all known methods for classically simulating quantum circuits and check that they scale exponentially on the actual parameters used in Google's experiment. The theoretical and practical checks are both needed because a simulation method that works in theory might still fail at the specific scale of the device.

On the theoretical side, computer scientists cannot prove that most problems they care about are hard, so they use reductions to pass the blame. If the target problem were easy, other problems believed to be hard would be easy too. This is the same basic strategy used throughout theoretical computer science and cryptography.

That reduction strategy has been central to NP-completeness, theoretical computer science, and cryptography since the 1970s. Aaronson and colleagues used it to give reduction evidence for the hardness of simulating sampling-based supremacy experiments. He is careful to say that such evidence is not as satisfactory as a proof and that improving it is a major open problem. Still, it implies that a fast classical algorithm capable of spoofing these experiments would have to be very unlike any algorithm currently known, in the same spirit as reasoning about P not equaling NP.