Quantum Speedup

Quantum speedup means a quantum algorithm solves a problem faster than any known classical algorithm, measured in computational complexity rather than raw clock speed. The nature of the speedup matters enormously: an exponential speedup (Shor’s factoring) is qualitatively different from a quadratic speedup (Grover’s search) or a polynomial speedup (quantum simulation). Not all claimed speedups survive rigorous scrutiny; some dissolve when better classical algorithms are found, and others apply only to artificial oracle models that do not reflect real computation.

Understanding what kind of speedup is claimed, and under what assumptions it holds, is as important as knowing that a speedup exists.

The details

Types of speedup by problem:

Algorithm	Problem	Classical best	Quantum	Speedup type
Shor’s	Integer factoring	Sub-exponential $e^{O(n^{1/3})}$	Polynomial $O(n^3)$	Super-polynomial
Grover’s	Unstructured search	$O(N)$	$O(\sqrt{N})$	Quadratic
HHL	Linear systems	$O(N)$ (dense)	$O(\text{poly}\log N)$	Exponential (conditional)
Quantum simulation	Chemical ground states	Exponential (in general)	Polynomial	Exponential
QSVT	Eigenvalue problems	$O(N^3)$	$O(N^2)$ (sparse)	Polynomial
BV	Hidden linear structure	$O(N)$	$O(1)$	Exponential (oracle)

Exponential speedup: Shor’s algorithm. The best classical algorithms for factoring an $n$-bit integer run in time $\exp(O(n^{1/3}))$, sub-exponential but much faster than polynomial. Shor’s algorithm runs in $O(n^3)$ quantum operations. This is a genuine super-polynomial speedup, not oracle-relative, because factoring is a real computational problem without any oracle abstraction.

Quadratic speedup: Grover’s algorithm. Grover’s algorithm searches an unstructured database of $N$ items in $O(\sqrt{N})$ oracle calls, provably optimal for quantum algorithms. The classical lower bound is $O(N)$. This quadratic speedup is real and proven, but it does not threaten symmetric cryptography in a practical sense: doubling the key length from 128 to 256 bits restores security.

Oracle separation vs real-world speedup. The Bernstein-Vazirani algorithm solves a hidden linear function in $O(1)$ quantum oracle calls vs $O(N)$ classical calls. This looks impressive but depends entirely on the oracle abstraction: if the function is given explicitly rather than as a black box, classical algorithms can often exploit its structure to achieve similar efficiency. Oracle separations prove quantum computers are faster in the oracle model; they do not prove speedups for specific natural problems.

Simon’s algorithm and exponential separation. Simon’s algorithm finds a hidden period $s$ in a function $f:\{0,1\}^n \to \{0,1\}^n$ in $O(n)$ quantum queries vs $\Omega(2^{n/2})$ classical queries, an exponential separation. This is the clearest oracle-model exponential speedup and directly inspired the development of Shor’s algorithm. However, Simon’s problem has no natural use case outside of this algorithmic role.

BQP, P, and NP. BQP is the class of problems solvable in polynomial time on a quantum computer. It contains P (polynomial classical time) and is contained in PSPACE. Quantum computers almost certainly do not solve NP-hard problems like 3-SAT or TSP in polynomial time. If BQP contained NP, the polynomial hierarchy would collapse, an outcome considered extremely unlikely by complexity theorists. Quantum computers are not magic: they provide speedups only where quantum interference can be exploited.

Dequantization. Several claimed exponential speedups in quantum machine learning (recommendation systems, principal component analysis, linear regression) were matched by classical randomized algorithms after Tang (2018) developed sampling-based classical methods that exploit the same low-rank structure. The lesson: speedup claims should be benchmarked against the best classical algorithms, not strawman comparisons.

Provable vs heuristic speedups. Some quantum speedups are proven unconditionally in query complexity (Grover, Simon). Others are unproven: QAOA is believed to outperform classical optimizers on some problems, but no rigorous speedup proof exists. Variational quantum algorithms (VQE, QAOA) may offer advantages in practice even without complexity-theoretic guarantees, or they may not.

Query complexity vs time complexity. Many quantum speedup proofs are stated in query complexity: the number of times an algorithm queries an oracle. This is a clean model for proving lower bounds and separations, but it differs from time complexity. An algorithm with fewer oracle queries may still be slower overall if each quantum oracle call is expensive to implement. When evaluating a claimed speedup, it is important to distinguish query complexity improvements (which are rigorous but may not translate to wall-clock time) from end-to-end runtime improvements (which account for all classical and quantum overhead).

Practical vs asymptotic speedup. Asymptotic speedups describe what happens as problem size $n \to \infty$. In practice, quantum hardware has large constant-factor overheads from error correction, qubit routing, and compilation. A quadratic speedup (Grover) means a quantum computer running on $N$ items is equivalent to a classical computer on $\sqrt{N}$ items, but if the quantum machine is 1,000x slower per operation due to error correction, the crossover point where quantum wins may require $N > 10^6$. For near-term devices, quantum advantage claims require careful accounting of these constants, not just asymptotic scaling.

The quantum machine learning debate. Between 2017 and 2022, dozens of papers claimed exponential quantum speedups for machine learning tasks: recommendation systems, linear systems, clustering, and generative models. Many were dequantized (Tang 2018, Chia et al. 2020): classical algorithms with comparable performance were found using sampling techniques. The lesson is not that quantum ML is useless, but that speedup claims require comparison against the best known classical algorithms, including randomized and approximation methods.

Where genuine speedups are expected. The most robust expected quantum speedups involve quantum simulation: modeling electrons in molecules, materials, and exotic states of matter. These problems involve Hilbert spaces that grow exponentially with system size, which is precisely where classical computers struggle and quantum computers have a structural advantage. Quantum simulation is the use case that Richard Feynman originally proposed in 1982, and it remains the most theoretically sound application for large-scale quantum computers.

Why it matters for learners

The question “does quantum computing provide a speedup?” has no universal answer. It depends entirely on the problem. Learning to distinguish exponential from quadratic speedups, and oracle-based from real-world speedups, is essential for evaluating quantum computing news and research claims. Most near-term quantum applications claim heuristic speedups without rigorous proofs; most far-term applications rely on fault-tolerant speedups that are rigorously proven but require hardware that is still years or decades away.

Developing a habit of asking three questions about any speedup claim makes most press releases easier to evaluate: Is the speedup proven or heuristic? Is it oracle-relative or for a natural problem? And is it compared against the best known classical algorithm, or a naive baseline? These three questions filter out a large fraction of overstated claims.

Common misconceptions

Misconception 1: Quantum computers are faster for all problems. Quantum computers are faster only for specific problem structures where superposition and interference provide an advantage. For most everyday computational tasks (sorting, text processing, database lookups, machine learning inference), classical hardware is faster and will remain so indefinitely. The set of problems where quantum computers excel is real but narrow, and finding new members of that set is an active research area.

Misconception 2: Quantum speedup and quantum supremacy mean the same thing. Quantum supremacy (or advantage) typically refers to a demonstration where a quantum device performs a specific task faster than classical hardware, regardless of the task’s usefulness. A meaningful quantum speedup requires advantage on a problem that matters. The Google 2019 supremacy experiment sampled from a random circuit distribution, a task with no known utility, and subsequent classical algorithms narrowed the gap significantly.

Misconception 3: Quantum speedups mean quantum computers always solve problems optimally. A quantum speedup over the best known classical algorithm does not guarantee optimality. New classical algorithms may reduce or eliminate the gap (as in the dequantization of quantum ML). The speedup is always relative to the current state of classical algorithmics, not an absolute claim. For many problems, neither the quantum nor classical optimal algorithm is known, and claims of speedup should be treated as provisional until both bounds are well-established.

See also

• Shor’s Algorithm
• Grover’s Algorithm
• Quantum Advantage
• Quantum Simulation
• Noisy Intermediate-Scale Quantum (NISQ)