umma.dev

Complexity theory gives every algorithm a growth rate, and that growth rate is what actually lets you compare a classical algorithm to a quantum one. Not “quantum is faster” in the abstract, but a specific classical bound next to a specific quantum bound, for the same problem. Some of those pairs show an exponential gap. One shows nothing changes at all. Lining four problems up this way is more informative than any general claim about quantum speedup.

Unstructured search

The problem: you have a black-box function $f: \{0, \dots, N-1\} \to \{0, 1\}$ with exactly one input $x_0$ where $f(x_0) = 1$, and no structure to exploit, no ordering, no hints. Find $x_0$.

Classical: nothing beats scanning:

def linear_search(f, N):
    for x in range(N):
        if f(x) == 1:
            return x

Worst case $N$ calls to $f$, average case $N/2$. There is no cleverer classical algorithm, an unstructured problem gives you nothing to divide-and-conquer or binary-search against.

Quantum: Grover’s algorithm (1996) finds $x_0$ in $O(N^{1/2})$ queries by repeatedly flipping the phase of the target state via an oracle call, then reflecting all amplitudes around their mean, amplitude amplification:

def grover_search(oracle, N):
    iterations = int((3.14159 / 4) * N**0.5)
    state = uniform_superposition(N)
    for _ in range(iterations):
        state = oracle_phase_flip(state)
        state = diffusion_reflect(state)
    return measure(state)   # returns x0 with high probability

$O(N) \text{ classical queries} \quad \text{vs} \quad O(N^{1/2}) \text{ quantum queries}$

For $N = 64$, that’s 64 classical calls against roughly 8 quantum ones. This gap is quadratic, not exponential, but it’s the tightest possible one. The Bennett-Bernstein-Brassard-Vazirani lower bound proves $\Omega(N^{1/2})$ queries are necessary for any quantum algorithm solving this problem, Grover’s algorithm isn’t just fast, it’s provably optimal.

Deciding constant versus balanced

The problem: $f: \{0,1\}^n \to \{0,1\}$ is promised to be either constant (same output on every input) or balanced (output 1 on exactly half the inputs). Which is it?

Classical: a deterministic algorithm has to check more than half the truth table to be certain, because an adversary could withhold the single output that breaks the tie until the last possible query:

$\text{worst case: } 2^{n-1} + 1 \text{ queries}$

For $n = 6$, that’s 33 queries out of 64 possible inputs.

Quantum: Deutsch-Jozsa (1992) answers it with exactly one query, by putting the input register into superposition, applying $f$ once as a phase oracle, and interfering the results through a layer of Hadamard gates before measuring:

def deutsch_jozsa(oracle, n):
    state = hadamard_all(zero_state(n))
    state = oracle(state)          # single call to f
    state = hadamard_all(state)
    return "constant" if measure(state) == 0 else "balanced"

$O(2^{n-1}) \text{ classical queries} \quad \text{vs} \quad O(1) \text{ quantum queries}$

This is the pair that matters most to complexity theory, not because the problem is practically useful, it isn’t, but because the exponential gap is proven, not conjectured. Most quantum speedups people ask about (does BQP really beat P? does factoring really need exponential classical time?) rest on unproven assumptions. Deutsch-Jozsa is one of the rare cases in all of complexity theory, classical or quantum, where “this is exponentially faster” is a theorem rather than a belief.

Period-finding and factoring

The problem: factor a large composite $N = pq$.

Classical: the best known classical algorithm, the general number field sieve, runs in sub-exponential time:

$\exp\left(O\!\left(n^{1/3} (\log n)^{2/3}\right)\right)$

where $n$ is the bit-length of $N$. Not exponential, but not polynomial either, and for cryptographic key sizes it’s far out of reach.

Quantum: Shor’s algorithm (1994) doesn’t attack factoring directly. It reduces factoring to finding the period $r$ of $f(x) = a^x \bmod N$, a much narrower problem, then solves that with the Quantum Fourier Transform:

from math import gcd

def shor_factor(N, a):
    r = quantum_period_find(a, N)   # O(n^2) gates via QFT
    if r % 2 != 0:
        return None
    x = pow(a, r // 2, N)
    if x == N - 1:
        return None
    p = gcd(x + 1, N)
    return (p, N // p) if 1 < p < N else None

$\text{sub-exponential classical} \quad \text{vs} \quad O(n^2) \text{ quantum gates}$

The reduction is the trick: period-finding is a problem the Quantum Fourier Transform is exactly suited to, because the QFT turns periodicity in the computational basis into a sharp peak in the frequency basis, readable out in polynomial time. It’s the same relationship the classical FFT has to periodic signals, just running on amplitudes instead of numbers.

Comparison sorting

The problem: sort $N$ items using only pairwise comparisons.

Classical: mergesort, heapsort and friends run in $O(N \log N)$, and there’s a proof that nothing does better. Any comparison-based sort is a decision tree distinguishing between $N!$ possible orderings, and a binary decision tree needs depth $\log_2(N!) = \Omega(N \log N)$ to have enough leaves.

Quantum: still $\Omega(N \log N)$. This is the pair that’s easy to miss, quantum computing doesn’t help here at all, and the reason is worth sitting with, because it explains why search and factoring do get a speedup and sorting doesn’t. Grover’s speedup comes from amplitude amplification against an oracle, quantum interference concentrates probability on the single answer among many candidates you’re searching over. Sorting’s lower bound isn’t a search problem in that sense, it’s an information-theoretic one, $\log_2(N!)$ bits of output have to come from somewhere, and no amount of interference manufactures information that isn’t in the input. Query-complexity lower bounds bend under quantum algorithms; information-theoretic ones don’t.

The comparison, in one table

Problem	Classical	Quantum	Gap
Unstructured search	$O(N)$	$O(N^{1/2})$	quadratic, proven optimal
Constant vs. balanced	$O(2^{n-1})$	$O(1)$	exponential, proven
Factoring	sub-exponential	$O(n^2)$ gates	exponential, believed
Comparison sorting	$\Omega(N \log N)$	$\Omega(N \log N)$	none

The pattern across all four: quantum algorithms don’t uniformly beat classical ones, they beat the classical bound exactly where the problem’s hardness comes from an oracle you have to query, search, promise problems, period-finding, and leave the bound untouched where the hardness comes from the information content of the answer itself. Complexity theory is what makes that distinction precise enough to state as a table instead of a slogan.

Zoom out from individual problems to the classes they live in and the same split shows up again, at a different scale.

Nothing in the search, Deutsch-Jozsa or Shor pairings above ever touches what’s decidable, every one of those problems was already computable classically, quantum only changes how many queries or gates it costs. Sorting is the reminder that even inside the computable world, cost doesn’t always move: some lower bounds are query-shaped and give way to interference, others are information-shaped and don’t.