Quantum Supremacy

A quantum computer performing a task that’s practically impossible for any classical computer, regardless of usefulness.

Quantum supremacy (also called quantum computational supremacy) is the milestone where a quantum computer solves a problem that no classical computer can solve in reasonable time.

The Concept

• Not about usefulness: The problem can be artificial
• About capability: Demonstrating quantum beats classical
• Practical impossibility: Classical would take thousands/millions of years

Google’s 2019 Claim

Google’s Sycamore processor (53 qubits):

• Sampled from random quantum circuits
• ~200 seconds on quantum computer
• Claimed: 10,000 years on classical supercomputers

The Task

Sample outputs from a random quantum circuit. The output distribution is hard to simulate classically.

IBM’s Response

IBM claimed the classical simulation could be done in 2.5 days using different techniques (trading time for storage).

Why Random Circuit Sampling?

It’s designed to be:

1. Hard for classical: Deep random circuits are hard to simulate
2. Easy to verify: Statistical tests on output distribution
3. Achievable now: Doesn’t need error correction

Controversy Over the Term

Many researchers prefer “quantum advantage” because:

• “Supremacy” has problematic connotations
• It doesn’t imply practical advantage
• “Advantage” is more accurate

Subsequent Claims

Challenges to Claims

Classical algorithms keep improving:

• Tensor network methods
• GPU acceleration
• Approximate simulation

The bar for supremacy keeps moving!

What It Means (and Doesn’t)

Does Mean

• Quantum computers can do something classical can’t
• The physics works as expected
• Progress toward useful quantum computing

Doesn’t Mean

• Quantum computers are “better” at everything
• Useful problems are solvable
• Classical computers are obsolete

The Path Forward

Quantum supremacy (artificial tasks)
        ↓
[Quantum advantage](./quantum_advantage.md) (useful tasks)
        ↓
Practical quantum computing (real-world impact)

We’re still working on the middle step.

See also: Quantum Advantage, NISQ, Quantum Speedup