Questions: Quantum Supremacy and Computational Complexity

Question 1

What is the difference between quantum supremacy and quantum advantage?

Model answer: Quantum supremacy is a specific claim: a quantum computer can solve a specific problem faster than any classical computer can. Quantum advantage is a broader term for quantum speedup, including cases where speedup is modest or problem-specific. Supremacy emphasizes the milestone of quantum computers outperforming classical; advantage acknowledges the spectrum of speedups. Both require rigorous benchmarking: comparing quantum vs. classical implementations, ensuring fair comparison (same hardware, same algorithm), and accounting for overhead (quantum error correction, compilation).

Terminology matters in research claims. Supremacy is a strong claim; advantage is more nuanced. Practical quantum computing likely sees advantage in specific domains before universal supremacy.

Question 2

Google's 2019 quantum supremacy result solved random circuit sampling. Why is random circuit sampling not directly useful, yet still significant?

• A. Random circuit sampling is completely useless; the supremacy result has no scientific value
• B. Random circuit sampling is not a real-world application, but demonstrates quantum speedup exists; it's a proof of concept motivating practical quantum algorithm development
• C. Random circuit sampling is the most important quantum application; no other quantum algorithms matter
• D. Supremacy requires solving practical problems; random circuits are too artificial

Answer: (B)

Random circuit sampling is a contrived problem designed to show quantum advantage with shallow circuits and high precision. It is not useful in practice, but the milestone matters: it demonstrates quantum computers can outperform classical ones for some task, proving quantum advantage is achievable. This motivates research into practical quantum algorithms and error correction. The significance is theoretical and aspirational, not practical.