Quantum Advantage: Definitions and Distinctions
Separating contrived sampling supremacy from practical, useful, and provable quantum advantage.
Why the words matter
Quantum advantage is used loosely, and the differences are important. A careful account separates several distinct claims: computational advantage on a contrived task, provable advantage under complexity assumptions, and practical advantage on a problem people actually want solved. Conflating them leads to overstatement.
A taxonomy
- Sampling advantage: a quantum device samples from a distribution classical machines plausibly cannot, as in random circuit and boson sampling. Contrived and hard to verify at scale.
- Provable advantage: complexity-theoretic separations, often conditional on conjectures like the non-collapse of the polynomial hierarchy.
- Practical advantage: solving a useful problem (chemistry, optimization, simulation) faster or better than the best classical method.
- Query advantage: fewer oracle queries than any classical algorithm, as in Grover and Simon, sometimes provable unconditionally in the query model.
The verification challenge
Advantage claims must state how the result was checked. Sampling tasks rely on cross-entropy benchmarking and extrapolation because the exact distribution is unavailable classically. Useful-problem advantage is easier to verify because the answer can be checked, but is far harder to achieve.
The dequantization lesson
Several quantum machine-learning speedups were later matched by classical algorithms operating under the same sampling-access assumptions, a process called dequantization. This is a reminder that an apparent exponential speedup can hinge on generous input assumptions rather than intrinsic quantum power. Rigorous advantage claims specify the input and output models precisely.
Honest current picture
As of the mid-2020s, demonstrated advantages are on contrived sampling tasks, contested by improving classical methods, and without error correction. Practical, fault-tolerant advantage on a valuable problem has not been demonstrated. Stating this plainly, alongside genuine progress, is the difference between rigor and hype. This framing applies to any computational use in engineering studies, including the classical and simulated design work behind fusion machines.