Types of Quantum Speedup

Not all quantum speedups are created equal. The word “speedup” can mean anything from an exponential reduction in runtime to a modest constant-factor improvement, or even an unverified claim that a quantum heuristic finds better solutions. Understanding the taxonomy of speedups is essential for evaluating quantum computing claims and deciding where quantum hardware is worth pursuing.

Superpolynomial and exponential speedups

A superpolynomial speedup means the quantum algorithm’s runtime scales as a function that grows slower than any polynomial of the classical algorithm’s runtime. The most powerful version is an exponential speedup, where a problem that requires time $2^n$ classically can be solved in time $\text{poly}(n)$ on a quantum computer.

Shor’s algorithm for integer factoring is the best-known example. The fastest known classical factoring algorithm (the general number field sieve) runs in sub-exponential time $\exp(O(n^{1/3} \log^{2/3} n))$, while Shor’s algorithm runs in polynomial time $O(n^3)$. This is not merely a constant or polynomial improvement; it is a qualitatively different scaling class. The exponential speedup is proven under the assumption that no faster classical algorithm exists, which is strongly believed but not proven unconditionally.

Other examples of superpolynomial speedups include the quantum Fourier transform (used as a subroutine in many algorithms), quantum phase estimation, and the hidden subgroup problem on abelian groups.

Polynomial speedups

A polynomial speedup means the quantum algorithm runs in time $O(f(n)^k)$ while the classical algorithm requires $O(f(n)^{k'})$ with $k < k'$, for some function $f$. The most important case is a quadratic speedup, where quantum algorithms require $O(\sqrt{N})$ operations for a problem that classically requires $O(N)$.

Grover’s algorithm is the canonical example. Searching an unstructured database of $N$ items requires $O(N)$ queries classically; Grover’s algorithm requires $O(\sqrt{N})$. This quadratic speedup applies broadly through amplitude amplification, a generalization that underlies many quantum algorithms.

Quadratic speedups matter less than exponential ones in the long run, because doubling classical hardware roughly halves runtime, and a quadratic quantum speedup can be matched by a moderate increase in classical resources. That said, for problems where even $O(\sqrt{N})$ is a meaningful saving (such as optimization over very large search spaces), quadratic speedups still have practical value.

Heuristic and problem-specific speedups

Heuristic speedups are claimed advantages that lack rigorous worst-case guarantees. Quantum annealing and QAOA (Quantum Approximate Optimization Algorithm) are primary examples. These algorithms may find good solutions to hard optimization problems faster than classical heuristics on specific problem instances or distributions, but no proof bounds their advantage across all instances.

Heuristic speedups are the most controversial category. Benchmark comparisons between quantum heuristics and classical optimizers are sensitive to the choice of instances, hardware conditions, and classical comparison algorithms. Many early claims of heuristic quantum speedup have not survived careful comparison against state-of-the-art classical solvers. This does not mean heuristic speedups do not exist, but it means they require rigorous empirical validation rather than back-of-envelope reasoning.

Oracle vs. physical speedups

An important subtlety is whether a speedup is defined relative to an oracle (a black-box function evaluated in a single step) or relative to physical computation time on real hardware. Grover’s quadratic speedup is proven in the oracle model: it requires $O(\sqrt{N})$ oracle queries. But on physical hardware, each oracle query has a cost that depends on the structure of the problem. Constant-factor overheads in quantum hardware (slower clock speeds, error correction overhead, higher gate counts) can erode or eliminate speedups that appear large in the oracle model.

See also

• Quantum Speedup
• Shor’s Algorithm
• Grover’s Algorithm
• Amplitude Amplification
• BQP
• Quantum Complexity Theory