Questions: Quantum Supremacy and Quantum Advantage

Question 1

Google's quantum supremacy experiment used random circuit sampling. Why was this task chosen rather than a practically useful computation like factoring?

• A. Factoring is easier to verify classically, making it a less convincing demonstration
• B. Random circuit sampling requires the fewest qubits
• C. Random circuit sampling is believed to be classically hard even at moderate circuit depth, and it can be verified probabilistically using cross-entropy benchmarking — making it the most achievable supremacy demonstration on near-term hardware
• D. Random circuit sampling is the only task where quantum computers are faster

Answer: (C)

Random circuit sampling was chosen because: (1) computational complexity arguments (based on the polynomial hierarchy) suggest it is classically intractable even at moderate depth; (2) it does not require error correction, making it feasible on noisy hardware; and (3) cross-entropy benchmarking provides a way to verify the quantum output without full classical simulation. Factoring useful numbers requires thousands of error-corrected logical qubits, far beyond current capabilities.

Question 2

After Google's supremacy claim, IBM argued that the classical simulation could be done in 2.5 days rather than 10,000 years using a different algorithm and enough disk space. This invalidates the supremacy claim entirely.

• T. True
• F. False

Answer: False

IBM's response showed that the classical hardness estimate depends on assumptions about available classical resources and algorithms. The estimated classical time has shifted as better classical simulation methods have been found, and subsequent work by Chinese groups further reduced the gap. However, the fundamental point remains: as quantum circuits grow (more qubits, more depth), classical simulation costs scale exponentially while quantum execution does not. The specific threshold at which supremacy is 'achieved' is a moving target, but the asymptotic scaling argument is robust.

Question 3

What is the difference between quantum supremacy and quantum advantage, and why does the distinction matter?

Model answer: Quantum supremacy refers to performing ANY computational task faster than any classical computer, even if the task is artificial and has no practical use (like random circuit sampling). Quantum advantage refers to performing a USEFUL task faster or better than the best classical approach. Supremacy has arguably been demonstrated; practical advantage for real-world problems has not. The distinction matters because supremacy demonstrates that quantum computational power is real, but it does not yet translate to practical value for end users.

The path from supremacy to advantage is the central challenge of the field. Supremacy experiments validate the physical and computational principles, but the tasks they solve (sampling from random circuits) are chosen specifically because they are hard to simulate classically, not because anyone needs the output. Practical advantage requires quantum algorithms that solve problems people care about — molecular simulation, optimization, machine learning — faster than the best classical alternatives, which continues to be elusive on current hardware.