Quantum Supremacy and Computational Complexity

Core Idea

Quantum supremacy (or advantage) refers to the ability of quantum computers to solve problems faster than the best-known classical algorithms, ideally exponentially faster. Computational complexity theory formalizes this: BQP is the class of problems solvable by quantum computers in polynomial time. Strong evidence suggests BQP is larger than P (polynomial-time classical), supporting quantum advantages. Google's 2019 quantum supremacy claim demonstrated sampling a distribution from a random quantum circuit faster than classical simulation. However, supremacy claims require careful benchmarking; advantage is problem-specific, often requires asymptotic advantages (large problem instances), and practical value depends on application relevance.

Explainer

Quantum supremacy represents a paradigm shift: quantum computers fundamentally faster than classical computers for at least some problems. The concept is rooted in computational complexity theory, which formalizes what problems are efficiently solvable.

Complexity Classes:

• P: Problems solvable classically in polynomial time (efficiently).
• NP: Problems whose solutions can be verified in polynomial time (includes P and likely much more).
• BQP: Problems solvable by quantum computers in polynomial time.

The relationship between P and BQP is unknown. Strong evidence suggests BQP is larger than P, meaning quantum computers can solve problems (efficiently) that classical computers cannot (efficiently). This is the basis for quantum advantage.

Evidence for BQP > P:

• Shor's algorithm factors in polynomial time (believed hard classically).
• Grover's algorithm searches unstructured databases with quadratic speedup.
• Hidden Subgroup Problem solved by quantum computers in polynomial time.

Google's Quantum Supremacy Claim (2019): Google's 53-qubit Sycamore processor sampled from the output distribution of a random quantum circuit. The task: given a random circuit, sample from its output distribution. Google claimed the quantum computer solved this in 200 seconds; classical simulation would require 10,000 years on the world's fastest supercomputer. This was a significant milestone, but with caveats:

• Random circuit sampling is not a practical application.
• The classical benchmark (full simulation) is conservative; classical sampling heuristics may be faster.
• The advantage diminishes with error correction and larger circuits.

Caveats and Challenges:

1. Problem Specificity: Quantum advantage is often for artificial, designed problems (random circuits, specific structured instances), not real-world applications.

2. Asymptotic vs. Practical: Quantum advantage often applies to asymptotically large problem instances; for near-term problem sizes, classical methods may be faster.

3. Overhead: Error correction and quantum circuit compilation add significant overhead, reducing practical advantages.

4. Classical Improvements: As classical algorithms improve, the supremacy gap narrows. What looked like exponential advantage might be polynomial.

BQP and NP: A central open question is whether NP ⊆ BQP. If yes, quantum computers could solve NP-complete problems efficiently, revolutionizing cryptography and optimization. Evidence suggests NP ⊄ BQP (quantumly hard problems exist), but this is unproven.

Practical Quantum Advantage: Near-term quantum advantage is likely to be for domain-specific problems:

• Quantum Chemistry: Exponential classical cost, fundamental quantum advantage.
• Combinatorial Optimization: Potential speedup for specific instances, though not proven exponential.
• Machine Learning: Quantum machine learning algorithms show promise but are less developed.

Future Directions:

• Fault-Tolerant Quantum Computing: With error correction, demonstrating practical quantum advantage on useful problems.
• Hybrid Quantum-Classical: Combining quantum and classical for efficiency.
• Problem-Specific Advantages: Focusing on domains with clear quantum benefits rather than universal supremacy claims.

Quantum supremacy is a milestone demonstrating quantum computers can outperform classical ones. Achieving practical, economically valuable quantum advantage remains an open challenge.