Algorithms where quantum beats classical (and where it doesn't)

Quantum algorithms are compared to classical algorithms by their complexity class membership — the asymptotic scaling of resource use as the problem size grows.

The relevant classes:

• P — problems solvable in polynomial classical time.
• NP — problems whose solutions are polynomial-time verifiable.
• BQP — bounded-error quantum polynomial time. Problems solvable by a quantum computer with bounded error probability in polynomial time.
• PSPACE — solvable with polynomial classical memory.

The key relations: $P \subseteq BQP \subseteq PSPACE$. It is widely believed (but not proved) that $BQP \not\subset P$ — that some problems in BQP are not in P. The factoring problem is the canonical example: known to be in BQP via Shor's algorithm, not known to be in P. Whether $BQP \supseteq NP$ is also open and is widely believed to be false. Quantum computers are not generally expected to solve all NP problems efficiently.

A 'quantum speedup' specifically means: the quantum algorithm has lower asymptotic complexity than the best known classical algorithm for the same problem. Exponential speedup moves the problem from exponential to polynomial classical complexity; polynomial speedup (most often quadratic) reduces a polynomial classical complexity by a power.

Shor's algorithm (1994) factors an $n$-bit integer $N$ in time polynomial in $n$ on a quantum computer. The best known classical algorithm (the general number field sieve) runs in time roughly

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

which is sub-exponential but superpolynomial. The quantum-vs-classical gap is exponential.

The algorithm's structure:

1. Reduce factoring to period finding: find the period $r$ of the function $f(x) = a^x \bmod N$ for a randomly chosen $a$.
2. Use the quantum Fourier transform (QFT) on $n$ qubits to extract the period. The QFT runs in $O(n^2)$ gates on a quantum computer; the classical fast Fourier transform on $2^n$ amplitudes runs in $O(n \cdot 2^n)$ time.
3. With high probability, the period $r$ yields nontrivial factors of $N$ via classical post-processing.

The exponential gap lives in step 2: a quantum computer applies the QFT to a superposition over $2^n$ values in $O(n^2)$ gates, while classically extracting the same information requires examining the values one at a time.

Resource estimates for cryptographically relevant key sizes (RSA-2048) currently project to several thousand logical qubits and roughly $10^9$–$10^{10}$ Toffoli gates, which translates (via the previous lesson's surface-code overhead) to millions of physical qubits.

If a fault-tolerant quantum computer of sufficient scale exists, Shor's algorithm breaks any cryptographic scheme whose security rests on the hardness of factoring or related problems.

Broken:

• RSA — security rests on factoring.
• Diffie–Hellman key exchange — security rests on the discrete logarithm problem, which Shor also solves.
• Elliptic-curve cryptography (ECC) — security rests on the elliptic-curve discrete log, which Shor also solves.

Not broken by Shor (some weakened by Grover):

• AES-256 and other symmetric ciphers — security rests on different hardness assumptions. Grover's algorithm gives at most a quadratic speedup, which AES-256 already over-provisions against.
• SHA-256 and other hash functions — same: Grover gives quadratic speedup against preimage and second-preimage attacks, manageable by larger output sizes.
• Lattice-based, code-based, hash-based, multivariate, isogeny-based crypto — these are 'post-quantum' schemes whose security rests on problems not known to be in BQP.

The last category is the target of the post-quantum cryptography migration, covered in the next lesson. The structural point: Shor breaks a specific class of cryptographic problems, not all cryptography.

Grover's algorithm (1996) finds a marked item in an unsorted list of $N$ items in $O(\sqrt{N})$ quantum queries. The classical lower bound for unstructured search is $\Omega(N)$ queries.

The algorithm's structure: amplitude amplification. Start with a uniform superposition over all $N$ items. Repeatedly apply two operations:

1. Mark the target — apply a phase flip ($-1$) to amplitudes of the target item(s). This is the oracle call.
2. Reflect about the mean — invert all amplitudes about their average value.

Each round rotates the state vector toward the target. After $O(\sqrt{N})$ rounds, measurement returns the target with high probability.

The speedup is quadratic, not exponential. For $N = 10^6$, classical search takes $10^6$ queries; Grover takes $10^3$. For $N = 10^{12}$, classical takes $10^{12}$; Grover takes $10^6$. The savings are real but bounded.

Critical structural caveat. Grover provides quadratic speedup for unstructured search. If the search has structure that admits a better classical algorithm (a sorted list with binary search, a graph problem with branch-and-bound, an integer with a known divisibility property), classical algorithms exploit the structure and may already beat Grover's asymptotic. Quadratic speedup against a baseline of $N$ is impressive; quadratic speedup against a baseline of $\log N$ is irrelevant.

A simple thought experiment shows the difference between quadratic and exponential speedup at the problem scales of practical interest.

Suppose classical solves a problem in time $T_C(n)$ on input size $n$ and quantum solves it in time $T_Q(n)$.

• Exponential speedup ($T_C = 2^n$, $T_Q = n^c$): for $n = 1000$, classical takes $2^{1000}$ steps (more than the lifetime of the universe), quantum takes a polynomial number. The qualitative regime changes.
• Quadratic speedup ($T_C = n^2$, $T_Q = n$): for $n = 10^6$, classical takes $10^{12}$ steps, quantum takes $10^6$. The savings are real but the regime is the same.

Fault-tolerant quantum computers will be far more expensive per operation than classical computers, both in capex (build a quantum computer) and in opex (control electronics, refrigeration, error-correction overhead). A quadratic speedup must overcome this per-operation cost differential to be practically useful.

Many analyses suggest that for symmetric cryptography and search-type problems, the threshold where Grover's quadratic speedup beats brute-force classical with realistic constants requires problem sizes large enough that the constants make the comparison unfavorable for quantum. Exponential speedup is the regime where the comparison is unambiguous in quantum's favor; quadratic speedup is contested in the realistic constants.

Hamiltonian simulation was Feynman's original 1982 proposal for the use of quantum computers: simulate the dynamics of a quantum system on another quantum system.

The problem: given a Hamiltonian $H$ describing a quantum system of $n$ particles, compute the time evolution $|\psi(t)\rangle = e^{-iHt}|\psi(0)\rangle$ for some time $t$.

Classical resources required to simulate a general $n$-particle quantum system grow exponentially with $n$ — the state vector has $2^n$ amplitudes. Many physical systems of practical interest (large molecules, materials, lattice gauge theories) have $n$ in the tens or hundreds, where exponential classical resources become infeasible.

Quantum algorithms (Lloyd 1996; later refinements by Berry, Childs, others) simulate Hamiltonian dynamics in time polynomial in $n$, the simulation time $t$, and the inverse precision $1/\epsilon$, using techniques such as Trotter decomposition, qubitization, and linear-combination-of-unitaries.

Applications.

• Quantum chemistry. Computing ground-state energies of molecules, particularly catalysts where electron correlation makes classical methods (DFT, CCSD(T)) struggle.
• Materials science. Properties of strongly correlated electron systems (high-T_c superconductors, frustrated magnets).
• Quantum field theory. Lattice simulations where the sign problem blocks classical Monte Carlo.

The regimes where the quantum advantage is sharpest are those where the classical method scales exponentially with the system size — strongly correlated systems where mean-field and perturbative approximations fail. The 'killer application' framing of quantum chemistry rests on these specific regimes, not on routine molecular calculations.

Several quantum algorithms claim speedups for problems beyond factoring, search, and simulation. Each comes with structural caveats.

HHL (Harrow–Hassidim–Lloyd) for linear systems. Solves $A\vec{x} = \vec{b}$ for sparse, well-conditioned matrices in time polynomial in $\log N$, where the classical best is polynomial in $N$. Claimed exponential speedup.

The asterisks:

• The output is a quantum state $|\vec{x}\rangle$, not the classical vector. Reading out all $N$ entries takes $\Omega(N)$ measurements.
• The input must be loadable in $O(\log N)$ time, which requires a 'QRAM' device whose construction is itself an open problem.
• The matrix must be sparse, well-conditioned, and admit specific operator-access oracles.

For problems where the output is a single number computed from the solution vector (an inner product with another known vector), HHL's speedup can survive the readout asterisk. For most practical linear-system tasks, the asterisks erase the speedup.

Quantum machine learning. Many proposals exist for quantum versions of linear regression, support vector machines, principal component analysis, neural networks. Most rely on HHL-style assumptions or on access to quantum state preparation that classically is no easier than the original problem. Claimed exponential speedups in this domain are an active research area where the gap between claim and end-to-end practical advantage is often substantial.

The lesson: a quantum algorithm's headline speedup is one number; the conditions under which the speedup survives end-to-end use (input loading, output extraction, problem structure) are several more numbers. The end-to-end picture is what matters.

Stepping back, the catalog of robustly established quantum speedups is small:

• Exponential: factoring and discrete logarithms (Shor); Hamiltonian simulation for systems whose classical complexity is exponential; sampling problems related to boson sampling and IQP circuits (proofs of quantum advantage in restricted settings).
• Polynomial (typically quadratic): unstructured search and many related problems via Grover; certain graph problems via quantum walks.

The structural feature shared by problems with exponential quantum speedup is algebraic or physical structure the classical algorithm cannot exploit:

• Factoring exploits the periodicity of $a^x \bmod N$, which the QFT extracts efficiently.
• Hamiltonian simulation exploits the quantum nature of the underlying problem — the quantum computer is structurally aligned with what is being simulated.
• Sampling problems exploit the difficulty of classically sampling from quantum output distributions.

For most problems — general optimization, machine-learning training, graph problems without special structure — no known exponential speedup exists, and several theorems rule out generic exponential speedup for entire problem classes. Quantum computers are a new computational substrate with specific capabilities, not a general-purpose accelerator that speeds up all algorithms.

The last lesson in this cursus examines how the cryptographic implications of Shor's algorithm are being addressed in practice — independent of any timeline for the quantum hardware to actually exist at the relevant scale.