Quantum Advantage

Quantum advantage is the practical goal of quantum computing: demonstrating that a quantum system solves a real, useful problem better than any classical computer. The term has a complicated history. It is often conflated with “quantum supremacy,” used loosely in press releases, and claimed by results that later face serious classical challenges. Understanding the distinction between different types of claimed speedup is essential for reading quantum computing news critically.

The honest summary as of 2026: exponential speedups are mathematically proven for specific problems but require fault-tolerant hardware that does not yet exist. Demonstrated results on current NISQ hardware have either targeted problems specifically designed to be hard classically, or have been matched by improved classical algorithms shortly afterward.

The details

Several distinct categories of quantum speedup exist:

Exponential speedup (provable): Shor’s algorithm factors integers in $O((\log N)^3)$ time, compared to the best classical algorithms that require sub-exponential time $O(\exp((\log N)^{1/3}))$. This is an exponential improvement, but it requires millions of logical qubits and fault-tolerant hardware.

Quadratic speedup (provable): Grover’s algorithm finds a marked item in $O(\sqrt{N})$ queries instead of $O(N)$. This is optimal for unstructured search, provably better than any classical approach. It does not threaten symmetric cryptography if key lengths are doubled.

Heuristic speedup (unproven): Variational algorithms like VQE and QAOA are designed to give useful approximate answers on NISQ hardware. Whether they outperform the best classical heuristics on problem instances that matter is not established.

Sampling-based claims: Google’s 2019 Sycamore experiment and 2024 Willow results demonstrated quantum circuits whose outputs are hard to sample classically. These are genuine experimental achievements, but the sampling problem is specifically engineered to favor quantum hardware. No practical application is known for this task.

The quantum chemistry path is the most credible near-term candidate. Simulating the electronic structure of molecules scales exponentially on classical computers for large systems. A modest quantum advantage in this area, even before full fault tolerance, would have real value for drug discovery and materials design.

Why it matters for learners

Learning to evaluate quantum advantage claims is one of the most practically useful skills in quantum computing education. Three questions help cut through hype:

1. Is the speedup exponential or quadratic? Exponential speedups are transformative but require fault-tolerant hardware. Quadratic speedups are useful but often not enough to change practical conclusions.
2. Does the problem have classical competition? Has the best classical algorithm been used for comparison, or an obviously weak baseline?
3. Is the problem useful? Beating classical computers on a problem specifically designed to be hard classically is very different from beating them on a problem industry actually cares about.

The field is progressing. But “quantum advantage on a useful problem” remains an open research challenge, not an accomplished fact.

Common misconceptions

Misconception 1: Google’s 2019 result proved quantum advantage. Google demonstrated that their Sycamore processor could perform a specific sampling task faster than Summit supercomputer at the time. IBM subsequently showed classical algorithms could match the task faster than Google estimated, and classical algorithms have continued to improve. The 2024 Willow result is harder to match classically, but the problem is still not practically useful.

Misconception 2: Quantum speedup is always exponential. Only specific algorithms on specific problem types offer exponential speedups. Grover’s search is quadratic. Many proposed near-term applications offer polynomial improvements at best. The popular narrative that quantum computers are exponentially faster in general is incorrect.

Misconception 3: Quantum advantage is a permanent claim once achieved. Classical algorithms improve. A quantum result that seems advantageous today may be matched by a better classical algorithm next year. Genuine, durable quantum advantage requires a problem where the quantum speedup is provably asymptotic, not just empirically better on today’s hardware.

See also

• Shor’s Algorithm
• Grover’s Algorithm
• NISQ
• Fault-Tolerant Quantum Computing
• Variational Quantum Eigensolver