Quantum Speedup

When a quantum algorithm solves a problem asymptotically faster than the best known classical algorithm.

Quantum speedup refers to a quantum algorithm outperforming classical algorithms, either provably or based on current knowledge.

Types of Speedup

Proven Speedup

Quantum is provably faster (information-theoretic lower bound for classical):

Problem	Classical	Quantum	Speedup
Unstructured search	$Ω (N)$	$O (N)$	Quadratic
Parity on OR tree	$Ω (N)$	$O (N)$	Quadratic

Superpolynomial (Believed)

Based on computational complexity assumptions:

Problem	Classical (best known)	Quantum
Factoring	$O (e^{n^{1/3}})$	$O (n^{3})$
Discrete log	$O (e^{n^{1/3}})$	$O (n^{3})$
Certain simulations	Exponential	Polynomial

Polynomial Speedup

Faster by a polynomial factor:

Problem	Classical	Quantum
Search	$O (N)$	$O (N)$
Collision finding	$O (N^{1/2})$	$O (N^{1/3})$

The Speedup Landscape

         Quantum Speedups
              │
    ┌─────────┴─────────┐
    │                   │
Exponential         Polynomial
    │                   │
 Factoring          Grover search
 Simulation         Many others
 Period finding

Important Caveats

Input/Output

Many quantum speedups assume quantum input or only require quantum output:

HHL: Exponential speedup… if you can prepare input and only need expectation values
Speedup may vanish with classical I/O overhead

Constant Factors

Quantum algorithms often have large constant factors:

Gate overhead
Error correction costs
Classical simulation may win for small problems

Problem Structure

Speedups exploit specific problem structure:

Shor’s uses periodicity
Grover’s uses function structure
Not all problems have exploitable structure

No Speedup

Some problems have no quantum speedup:

Sorting: Still $O (N lo g N)$
General NP-complete: No known speedup
PSPACE-complete: Quantum in PSPACE, so no exponential speedup

Measuring Real Speedup

For practical comparisons:

Wall-clock time on real problems
Include all overheads (error correction, I/O)
Compare to best classical hardware and algorithms

Current status: Still demonstrating quantum advantage on artificial problems.

Quantum Jargon Decoder