In 2019, Google claimed quantum supremacy with their Sycamore processor, completing a calculation in 200 seconds that would take classical supercomputers 10,000 years. But supremacy is not the same as advantage. The real race is for practical quantum advantage — solving real-world problems faster than any classical computer.

Supremacy vs. Advantage¶

• Quantum supremacy: A quantum computer outperforms classical for any task (even an artificial one)
• Quantum advantage: A quantum computer outperforms classical for a useful task

Google’s random circuit sampling demonstrated supremacy but wasn’t useful. The goal now is advantage.

The Computational Complexity Landscape¶

Quantum computers are believed to occupy a specific place in computational complexity:

$$\text{BPP} \subseteq \text{BQP} \subseteq \text{PSPACE}$$

Where:

• $\text{BPP}$: Problems efficiently solvable by classical computers
• $\text{BQP}$: Problems efficiently solvable by quantum computers
• $\text{PSPACE}$: Problems solvable with polynomial memory

The key question: which useful problems are in BQP but not in BPP?

Known Exponential Speedups¶

Shor’s Algorithm¶

For factoring an $n$-bit integer:

• Classical (number field sieve): $O\left(e^{1.9 n^{1/3} (\ln n)^{2/3}}\right)$
• Quantum (Shor’s algorithm): $O(n^3)$

This exponential speedup threatens RSA encryption but requires millions of error-corrected qubits.

Quantum Simulation¶

Simulating a quantum system of $n$ qubits classically requires $O(2^n)$ resources. A quantum computer needs only $O(\text{poly}(n))$ — this is the “killer app” for quantum computing.

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector, SparsePauliOp
import numpy as np

def trotterized_evolution(n_qubits=4, n_steps=10, dt=0.1):
    """
    Simulate time evolution of a 1D Heisenberg chain
    using first-order Trotterization.
    H = Σ (XX + YY + ZZ)
    """
    qc = QuantumCircuit(n_qubits)

    # Initial state: |↑↓↑↓...⟩
    for i in range(1, n_qubits, 2):
        qc.x(i)

    # Trotter steps
    for _ in range(n_steps):
        for i in range(n_qubits - 1):
            # XX interaction
            qc.rxx(2 * dt, i, i + 1)
            # YY interaction
            qc.ryy(2 * dt, i, i + 1)
            # ZZ interaction
            qc.rzz(2 * dt, i, i + 1)

    return qc

circuit = trotterized_evolution()
sv = Statevector.from_instruction(circuit)
print(f"Final state has {sv.num_qubits} qubits")
print(f"Number of non-zero amplitudes: {np.count_nonzero(sv.data)}")

Hardware Progress (2019–2025)¶

The Road to Practical Advantage¶

Three conditions must be met:

1. Error rates below QEC threshold (~0.1% for surface codes) — achieved by Google Willow in 2024
2. Enough logical qubits for useful algorithms — requires millions of physical qubits
3. Algorithms with proven advantage for practical problems — active area of research

Near-Term Applications¶

While waiting for fault-tolerant machines, variational quantum algorithms (VQA) attempt advantage on noisy hardware:

• VQE: Variational Quantum Eigensolver for chemistry
• QAOA: Quantum Approximate Optimization for combinatorics
• QML: Quantum Machine Learning for kernel methods

The consensus is that practical quantum advantage will first appear in quantum simulation of chemistry and materials — the original application Feynman envisioned in 1982.

The question is no longer whether quantum computers will be useful, but when and for what they will first demonstrate undeniable advantage over classical supercomputers.