Defining and Demonstrating Quantum Supremacy: Google's Experiment and the Limits of Classical Computation

The discussion centers on quantum supremacy, a term coined by John Preskill, defining the point where a quantum computer performs a well-defined task significantly faster than any known classical algorithm. A crucial distinction is made between a "useful" task and a "well-defined" task, with current quantum supremacy demonstrations falling into the latter category. The core argument is that while classical computers can theoretically simulate anything a quantum computer does, they do so exponentially slower, highlighting the quantum computer's ability to change what is "efficiently computable" from exponential to polynomial scaling.

The speaker, Scott Aaronson, clarifies three criteria for quantum supremacy: literal speed-up in seconds, better scaling behavior (polynomial quantum vs. exponential classical), and the observed speed-up being solely attributable to this scaling. He emphasizes that quantum supremacy does not require error correction, but rather serves to refute skeptics who doubt quantum computers' ability to ever outperform classical ones. A significant nuance is the shift from problems with a single right answer (like factoring) to "sampling problems," where the goal is to output a sample from a specific probability distribution, which is more amenable to current noisy quantum computers.

The practical demonstration of quantum supremacy, as exemplified by Google's 53-qubit experiment, involved applying a randomly chosen sequence of operations to generate samples from a complex probability distribution. Verifying these results required sophisticated statistical tests, such as Google's linear cross-entropy benchmark. This test, ironically, demands a massive classical computation (2^53 operations) to verify the quantum computer's output, pushing the limits of even the largest supercomputers like Summit. This explains why the number of qubits (53) was chosen – it's large enough to challenge classical simulation but small enough to allow for verification.

A major challenge is definitively proving that a classical computer *could not* have quickly spoofed the results. This delves into fundamental questions of complexity theory, akin to the P vs. NP problem. While absolute proof is elusive, theoretical computer science offers "reduction evidence," which shifts the burden of proof by demonstrating that if these quantum supremacy experiments *could* be classically spoofed, then other problems widely believed to be hard would also be easy. This ongoing work, blending theoretical math with empirical validation, underpins the confidence in current quantum supremacy claims and points towards future computational paradigms beyond current verification limits.

"quantum supremacy just refers to sort of the point in history when you can first use a quantum computer to do some well-defined task much faster than any known algorithm running on any of the classical computers that are available"

"everything that a quantum computer can do a classical computer can also eventually do... albeit exponentially slower"

"they do not solve the halting problem they cannot solve anything that is uncomputable in how an Turing sense what they what we think they do change is what is efficiently computable"

"we want first of all the quantum computer to be much faster just in the literal sense of like number of seconds... secondly we want it to be sort of a... problem where we really believe that a quantum computer has better scaling behavior... and then thirdly we want the first thing the actual observed speed-up to only be explainable in terms of the scaling behavior"

"quantum supremacy does not require error correction... but you could say quantum supremacy is already enough by itself to refute the skeptics who said a quantum computer will never outperform a classical computer for anything"

"if you just want to prove that a quantum computer is faster you know and not do something useful with it then there are huge advantages to sort of switching your attention from problems like factoring numbers that have a single right answer to what we call sampling problems"

"for this type of experiment we don't want a hundred qubits... because with a hundred qubits even if it works we don't know how to verify the results"

"we don't know how to rule out definitively that there could be fast classical algorithms for you know even simulating quantum mechanics... but we can give some evidence against that possibility"

"we don't know how to prove that most of the problems we care about are hard but we know how to pass the blame to someone else"