Quantum Computers, From First Principles: What They Are and What They Provably Run Faster

Every computer you have ever used — from the ENIAC to the phone in your pocket — is, mathematically speaking, the same machine. A supercomputer and a pocket calculator differ in speed and memory, but they compute the same class of functions in fundamentally the same way: by flipping bits, definite 0s and 1s, one deterministic step after another. Alan Turing formalized this in 1936, and for nearly a century, "computation" has meant "what a Turing machine does."

But here is a question that took surprisingly long to ask: why should the laws of computation be classical when the laws of physics are not?

Nature, at its lowest level, does not run on bits. An electron does not have a definite position until you measure it. A photon takes, in a meaningful sense, every path at once through an interferometer. Two particles can be correlated in ways that no theory of local classical variables can reproduce — a fact Bell proved mathematically in 1964 and experimenters have confirmed to exhausting precision since.

In 1981, Richard Feynman posed the problem bluntly at a conference at MIT: simulating quantum systems on classical computers appears to be exponentially hard. To track the full quantum state of just 300 interacting particles, you would need to store more complex numbers than there are atoms in the observable universe. Nature, meanwhile, "computes" this state effortlessly, in real time, just by existing. Feynman's provocation:

"Nature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical."

The idea sat there, half physics and half computer science, until 1985, when David Deutsch defined the universal quantum Turing machine and showed that the question "what can be computed efficiently?" has a physics-dependent answer. Then in 1994, Peter Shor detonated the field: he found a quantum algorithm that factors integers in polynomial time. Since the difficulty of factoring underpins RSA — the cryptosystem protecting most of the internet — quantum computing went from curiosity to geopolitical priority overnight.

So the honest framing is this: a quantum computer is not a "faster computer." It is a different kind of computer, one that manipulates information using superposition, entanglement, and interference. For most tasks it offers nothing. For a specific and precious set of tasks, it offers speedups so large that "faster" stops being the right word — the classical alternative simply never finishes.

The rest of this post builds that claim from the ground up: first the mathematics of quantum information, then the actual proofs of quantum advantage, then the honest map of what remains out of reach.

1. The mathematics of a qubit

1.1 From bit to qubit

A classical bit is an element of ${0,1}$. A qubit is a unit vector in a two-dimensional complex vector space (a Hilbert space) $\mathbb{C}^2$. In Dirac notation the two basis vectors are written

$$|0\rangle = \begin{pmatrix} 1 \ 0 \end{pmatrix}, \qquad |1\rangle = \begin{pmatrix} 0 \ 1 \end{pmatrix}$$

A general qubit state is a superposition — a complex linear combination

$$|\psi\rangle = \alpha|0\rangle + \beta|1\rangle, \qquad \alpha,\beta \in \mathbb{C}, \qquad |\alpha|^2 + |\beta|^2 = 1$$

The complex numbers $\alpha$ and $\beta$ are called amplitudes, and they are not probabilities — this is the single most important distinction in the whole subject. Probabilities are non-negative reals that can only add. Amplitudes are complex numbers that can cancel. Everything a quantum computer can do that a classical computer cannot traces back to this one fact.

1.2 Measurement

When you measure a qubit in the computational basis, you get a classical outcome governed by the Born rule:

$$\Pr[\text{outcome } 0] = |\alpha|^2, \qquad \Pr[\text{outcome } 1] = |\beta|^2$$

and the state collapses to the observed basis state. Measurement is irreversible and destroys the superposition. This is why quantum computing is subtle: the machine can hold a vast superposition internally, but any attempt to look at it yields a single random sample. Quantum algorithms are exercises in choreographing the state so that, by the time you measure, the answer you want holds nearly all of the probability.

1.3 The Bloch sphere

A global phase is unobservable — $|\psi\rangle$ and $e^{i\gamma}|\psi\rangle$ are physically identical — so a qubit's physical state has two real degrees of freedom. Every pure qubit state can be written as

$$|\psi\rangle = \cos\tfrac{\theta}{2},|0\rangle + e^{i\varphi}\sin\tfrac{\theta}{2},|1\rangle, \qquad 0 \le \theta \le \pi,\quad 0 \le \varphi < 2\pi$$

which maps qubit states one-to-one onto the surface of a sphere — the Bloch sphere:

The Bloch sphere: a qubit state as a point on a sphere, with polar angle theta and azimuthal angle phi

The poles are the classical states $|0\rangle$ and $|1\rangle$. The equator holds the maximally uncertain superpositions like $|+\rangle = (|0\rangle+|1\rangle)/\sqrt{2}$. A classical bit lives only at the poles; a qubit lives anywhere on the sphere — and single-qubit gates are exactly the rotations of it.

1.4 Many qubits: where the exponential lives

The state space of $n$ qubits is the tensor product of the individual spaces:

$$\mathcal{H} = \mathbb{C}^2 \otimes \mathbb{C}^2 \otimes \cdots \otimes \mathbb{C}^2 \cong \mathbb{C}^{2^n}$$

A general $n$-qubit state is

$$|\psi\rangle = \sum_{x \in {0,1}^n} \alpha_x, |x\rangle, \qquad \sum_x |\alpha_x|^2 = 1$$

This is the exponential Feynman was pointing at. Describing the state of $n = 300$ qubits requires $2^{300} \approx 10^{90}$ complex amplitudes — more numbers than there are atoms in the observable universe (about $10^{80}$). A classical simulator must track all of them; nature just is them.

Crucial caveat: this does not mean a quantum computer "stores $2^n$ values" in any usable sense. Measuring $n$ qubits yields exactly $n$ classical bits. The art is extracting global properties of all $2^n$ amplitudes — a period, a parity, an interference pattern — without ever reading them individually.

1.5 Entanglement

Some multi-qubit states factor into independent pieces: $|00\rangle = |0\rangle \otimes |0\rangle$. Some provably do not. Consider the Bell state:

$$|\Phi^+\rangle = \frac{|00\rangle + |11\rangle}{\sqrt{2}}$$

Matching coefficients with $|\Phi^+\rangle$ requires $a_0 b_0 = 1/\sqrt{2}$, $a_1 b_1 = 1/\sqrt{2}$, and $a_0 b_1 = a_1 b_0 = 0$. But $a_0 b_1 = 0$ forces $a_0 = 0$ or $b_1 = 0$, contradicting $a_0 b_0 \neq 0$ or $a_1 b_1 \neq 0$ respectively. $\blacksquare$

Such states are entangled: the qubits have no individual states, only a joint one. Measure the first qubit of $|\Phi^+\rangle$ and the second is instantly determined — perfectly correlated, regardless of distance. (This does not transmit information: each qubit's local statistics are 50/50 either way, so relativity survives.) Entanglement is what makes the $2^n$-dimensional state space irreducible — without it, $n$ qubits are just $n$ separate spheres, classically simulable in linear time.

2. Computation as unitary evolution

2.1 Quantum gates

Between measurements, quantum mechanics says closed systems evolve linearly and reversibly: states are mapped by unitary matrices ($U^\dagger U = I$). Unitarity is exactly the condition that preserves total probability. A quantum gate is a unitary matrix; a quantum circuit is a product of them. The workhorses:

$$X = \begin{pmatrix} 0 & 1 \ 1 & 0 \end{pmatrix}, \qquad Z = \begin{pmatrix} 1 & 0 \ 0 & -1 \end{pmatrix}, \qquad H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \ 1 & -1 \end{pmatrix}$$

The essential two-qubit gate is CNOT (controlled-NOT): flip the target qubit if and only if the control is $|1\rangle$:

$$\mathrm{CNOT} = \begin{pmatrix} 1&0&0&0 \ 0&1&0&0 \ 0&0&0&1 \ 0&0&1&0 \end{pmatrix}$$

Applied to a superposed control, CNOT creates entanglement. The two-gate circuit below manufactures the Bell state:

Bell state preparation circuit: Hadamard on the first qubit, then CNOT

Two gates take $|00\rangle$ to $(|00\rangle + |11\rangle)/\sqrt{2}$: the Hadamard creates the superposition, the CNOT correlates the second qubit with the first. The measured bits always agree, though each is individually random.

Universality (stated without proof): the gate set ${H, T, \mathrm{CNOT}}$, with $T = \mathrm{diag}(1, e^{i\pi/4})$, is universal — any $n$-qubit unitary can be approximated to arbitrary precision by circuits over these gates, and the Solovay–Kitaev theorem guarantees the overhead is only polylogarithmic in the precision. This is the quantum analogue of "NAND is universal."

2.2 The no-cloning theorem, with proof

Classical computers copy data constantly. Quantum computers cannot. This is not an engineering limitation — it is a theorem.

Proof. Suppose such a $U$ exists, and let $|\psi\rangle, |\varphi\rangle$ be any two states. By assumption:

Take the inner product of the two equations. Unitaries preserve inner products, so the left-hand sides give $\langle\psi|\varphi\rangle\langle 0|0\rangle = \langle\psi|\varphi\rangle$, while the right-hand sides give $\langle\psi|\varphi\rangle^2$. Hence

$$\langle\psi|\varphi\rangle = \langle\psi|\varphi\rangle^2$$

so $\langle\psi|\varphi\rangle \in {0, 1}$: the two states are either identical or orthogonal. A device that clones only orthogonal states is a classical copier, not a quantum one. No such $U$ exists. $\blacksquare$

The consequences ripple everywhere: error correction cannot simply triplicate qubits (it has to be cleverer — and, remarkably, it is; see §5), quantum states cannot be non-destructively eavesdropped (the basis of quantum key distribution), and quantum algorithms cannot "save a checkpoint" of an unknown state.

2.3 Interference: the actual engine of speedup

Here is the mechanism behind every quantum speedup, in its smallest form. Apply $H$ twice to $|0\rangle$:

$$|0\rangle \xrightarrow{H} \frac{|0\rangle + |1\rangle}{\sqrt{2}} \xrightarrow{H} \frac{1}{2}\big(|0\rangle + |1\rangle\big) + \frac{1}{2}\big(|0\rangle - |1\rangle\big) = |0\rangle$$

Watch the $|1\rangle$ term: it acquired amplitude $+\tfrac{1}{2}$ through one computational path and $-\tfrac{1}{2}$ through the other. The paths destructively interfere, and the outcome $|1\rangle$ becomes not merely unlikely but impossible. Both paths to $|0\rangle$ carry $+\tfrac{1}{2}$ and constructively interfere to certainty.

Path diagram for two successive Hadamard gates: amplitudes to outcome 0 add, amplitudes to outcome 1 cancel

A classical randomized computer can also "take both paths," but its path weights are probabilities — positive numbers that only add. It can never make a wrong answer cancel out.

Every algorithm in the next section is this trick, scaled up: arrange the computation so that paths leading to wrong answers arrive with opposing phases and annihilate, while paths to the right answer arrive in phase and reinforce.

One more identity before the algorithms — the effect of Hadamards on all $n$ qubits, used repeatedly below. For bitstrings $x, y \in {0,1}^n$, with $x \cdot y = \sum_i x_i y_i$:

$$H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y \in {0,1}^n} (-1)^{x \cdot y}, |y\rangle$$

(Proof: for one qubit, $H|x\rangle = \big(|0\rangle + (-1)^x |1\rangle\big)/\sqrt{2} = \sum_y (-1)^{xy}|y\rangle/\sqrt{2}$; tensor $n$ copies and the phases multiply.) In particular, $H^{\otimes n}|0^n\rangle$ is the uniform superposition over all $2^n$ bitstrings — one layer of gates, exponentially many terms.

3. What quantum computers provably run faster

Now the payoff. Each algorithm below comes with the actual argument for its speedup, in increasing order of practical importance.

3.1 Deutsch–Jozsa: an exact, provable, exponential separation

This algorithm is a toy, but it is the cleanest theorem of quantum advantage — the separation is exact and unconditional in the query model.

Problem. You are given black-box access to $f : {0,1}^n \to {0,1}$, promised to be either constant (same output on all inputs) or balanced (output 0 on exactly half the inputs, 1 on the other half). Decide which, minimizing queries to $f$.

Classical lower bound. A deterministic algorithm may query $2^{n-1}$ inputs, see all zeros, and still not know: the function could be constant, or balanced with all its 1s hiding in the unqueried half. Only the $(2^{n-1}+1)$-th query settles it. So the deterministic classical complexity is exactly $2^{n-1}+1$ queries — exponential in $n$.

Quantum algorithm: one query. Use the standard phase oracle $U_f|x\rangle = (-1)^{f(x)}|x\rangle$.

Deutsch–Jozsa circuit: Hadamard layer, one oracle call, Hadamard layer, measurement

Three stages: spread amplitude over every input, query once so every branch picks up its phase simultaneously, then interfere everything back together.

Analysis. Track the state through the circuit. After the first Hadamard layer:

$$|\psi_1\rangle = \frac{1}{\sqrt{2^n}} \sum_{x} |x\rangle$$

After the single oracle call — every branch of the superposition acquires its phase in one shot:

$$|\psi_2\rangle = \frac{1}{\sqrt{2^n}} \sum_{x} (-1)^{f(x)}, |x\rangle$$

After the second Hadamard layer, by the $H^{\otimes n}$ identity of §2.3:

$$|\psi_3\rangle = \frac{1}{2^n} \sum_{y} \left[, \sum_{x} (-1)^{f(x) + x \cdot y} \right] |y\rangle$$

Now read off the amplitude of the outcome $y = 0^n$, for which $x \cdot y = 0$ always:

$$\mathrm{amp}(0^n) = \frac{1}{2^n} \sum_{x} (-1)^{f(x)} = \begin{cases} \pm 1 & f \text{ constant (all } 2^n \text{ terms equal)} \ 0 & f \text{ balanced (terms cancel pairwise)} \end{cases}$$

So measure all $n$ qubits: if $f$ is constant you see $0^n$ with probability 1; if $f$ is balanced you see $0^n$ with probability 0. One query, deterministic answer, versus $2^{n-1}+1$ classically. $\blacksquare$

The fine print: a classical randomized algorithm solves this with high probability in $O(1)$ queries, so the separation is against deterministic computation. Its descendant fixed that — Simon's algorithm (1994) achieves an exponential separation even against randomized classical algorithms ($O(n)$ quantum queries versus $\Omega(2^{n/2})$ classical), and it was Simon's paper that directly inspired Shor.

3.2 Grover's search: quadratic speedup, provably optimal

Problem. Unstructured search: among $N = 2^n$ items, exactly one marked item $w$ satisfies $f(w) = 1$. Classically there is no structure to exploit, so nothing beats trying items: $\Theta(N)$ evaluations on average.

Grover (1996): $O(\sqrt{N})$ quantum queries. And this is not just an upper bound — it is tight, which makes unstructured search the rare problem whose quantum complexity is exactly known.

The algorithm. Work in the two-dimensional real plane spanned by the marked state $|w\rangle$ and the uniform superposition of everything else, $|s'\rangle = \frac{1}{\sqrt{N-1}}\sum_{x \neq w}|x\rangle$. The start state $|s\rangle = H^{\otimes n}|0^n\rangle$ lives in this plane:

$$|s\rangle = \sin\theta, |w\rangle + \cos\theta, |s'\rangle, \qquad \sin\theta = \frac{1}{\sqrt{N}}$$

For large $N$, $\theta \approx 1/\sqrt{N}$: the start state is almost orthogonal to the answer, tilted toward it by a tiny angle. Each Grover iteration applies two reflections:

Oracle $U_w = I - 2|w\rangle\langle w|$: flips the sign of the marked amplitude — geometrically, a reflection about $|s'\rangle$.
Diffusion $U_s = 2|s\rangle\langle s| - I$: "inversion about the mean" — a reflection about $|s\rangle$.

Two reflections compose into a rotation by $2\theta$ toward $|w\rangle$ — that is elementary plane geometry, and it is the entire algorithm:

Grover geometry: each iteration rotates the state by 2 theta toward the target; success probability oscillates as sin squared

Left: the state vector climbing toward $|w\rangle$ by $2\theta$ per iteration. Right: the exact success probability for $N = 1024$ — note the distinctly quantum failure mode: iterate past the optimum and the state rotates past the target, and the success probability falls again.

After $k$ iterations the state makes angle $(2k+1)\theta$ with $|s'\rangle$, so

$$\Pr[\text{measure } w] = \sin^2\big((2k+1)\theta\big)$$

We want $(2k+1)\theta \approx \pi/2$, i.e.

$$k \approx \frac{\pi}{4\theta} \approx \frac{\pi}{4}\sqrt{N}$$

at which point the success probability is $1 - O(1/N)$. About $\tfrac{\pi}{4}\sqrt{N}$ queries instead of about $N/2$. $\blacksquare$

Log-scale comparison of classical linear search versus Grover square-root search as the search space grows

For $N = 2^{64}$: about 3.4 billion quantum queries versus 9 quintillion classical ones.

Optimality (the BBBV theorem). Bennett, Bernstein, Brassard, and Vazirani (1997) proved that any quantum algorithm for unstructured search requires $\Omega(\sqrt{N})$ oracle queries. The proof is a hybrid argument: an algorithm making few queries cannot place enough amplitude on the marked item's position for the "marked" and "unmarked" worlds to become distinguishable — the deviation between the two runs grows at most linearly in the number of queries but must reach a constant, forcing $\sqrt{N}$ of them. Two consequences:

Grover is optimal — no quantum algorithm searches a black box exponentially fast.
Quantum computers cannot brute-force NP-complete problems into polynomial time. Relative to an oracle, NP ⊄ BQP. Quadratic help, not miracles.

Grover's speedup is generic: it accelerates any brute-force search — SAT solving, collision finding, symmetric-key cryptanalysis. A 128-bit key falls in roughly $2^{64}$ Grover steps, which is exactly why "post-quantum" symmetric cryptography just means doubling key lengths to 256 bits.

3.3 Shor's algorithm: the exponential speedup that matters

Problem. Given an $n$-bit composite integer $N$, find a nontrivial factor.

The best known classical algorithm — the general number field sieve — runs in sub-exponential but super-polynomial time:

$$\exp\left( \left(\tfrac{64}{9}\right)^{1/3} (\ln N)^{1/3} (\ln \ln N)^{2/3} ,\big(1+o(1)\big) \right)$$

Factoring a 2048-bit RSA modulus this way is estimated at $10^{20}$–$10^{25}$ core-years — effectively never. Shor's algorithm (1994) factors $N$ in $O((\log N)^3)$ time: polynomial, comfortably efficient. The same number: hours to days on a large fault-tolerant quantum computer.

Runtime scaling of the general number field sieve versus Shor's algorithm as the modulus grows

Sub-exponential versus polynomial on a log scale. At RSA-2048 the gap is about 25 orders of magnitude.

Step 1 — the classical reduction (pure number theory)

Factoring reduces to order finding. Pick a random $a$ with $1 < a < N$ and $\gcd(a, N) = 1$ (if the gcd is nontrivial you got lucky — that is a factor). Define the order $r$ of $a$: the least positive integer with

$$a^r \equiv 1 \pmod{N}$$

Suppose $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$. Then, writing $x = a^{r/2}$:

$$x^2 - 1 = (x-1)(x+1) \equiv 0 \pmod{N}$$

so $N$ divides $(x-1)(x+1)$. By the minimality of $r$, $N \nmid (x-1)$; by assumption $N \nmid (x+1)$. So the prime factors of $N$ split across the two terms, and

$$\gcd\big(a^{r/2} - 1,; N\big)$$

is a nontrivial factor — computable in polynomial time by Euclid's algorithm. A counting argument over the group $(\mathbb{Z}/N\mathbb{Z})^*$ shows a random $a$ satisfies both conditions with probability at least $1/2$ (for odd $N$ with at least two distinct prime factors), so a few repetitions suffice.

All of this has been known for decades. The wall is computing $r$: classically, order finding is believed as hard as factoring itself. This is where the quantum computer comes in.

Step 2 — quantum period finding

The function $g(k) = a^k \bmod N$ is periodic with period $r$, and Shor's quantum core finds the period of this exponentially long sequence in polynomial time.

Shor's period-finding circuit: Hadamards, controlled modular exponentiation, quantum Fourier transform, measurement

The modular exponentiation is ordinary classical arithmetic compiled into reversible gates — it is the $O((\log N)^3)$ bottleneck. The magic is what comes after.

With $M = 2^{2n}$, the state after the modular exponentiation is $\frac{1}{\sqrt{M}}\sum_k |k\rangle,|a^k \bmod N\rangle$. The second register's value is shared by exactly the exponents $k, k+r, k+2r, \dots$ — so the first register secretly holds a superposition with period $r$. Reading it directly would yield one useless random $k$. Instead, apply the quantum Fourier transform:

$$\mathrm{QFT}: \quad |k\rangle ;\mapsto; \frac{1}{\sqrt{M}} \sum_{y=0}^{M-1} e^{2\pi i, k y / M}, |y\rangle$$

The QFT is the interference machine par excellence: for $y$ near a multiple of $M/r$, the phases $e^{2\pi i k y/M}$ of the periodic branches align and add constructively; for every other $y$ they wind uniformly around the unit circle and cancel. It is the exact quantum analogue of a discrete Fourier transform picking the frequency out of a periodic signal — but computed over $2^{2n}$ amplitudes with only $O(n^2)$ gates. Here is the resulting measurement distribution, simulated exactly for the toy case $a = 2$, $N = 21$:

Exact simulated output distribution of Shor's period finding for a=2, N=21: sharp peaks at multiples of M/r

Nearly all probability concentrates at $y \approx j \cdot M/r$. Measure, run the continued-fraction expansion of $y/M$, and out comes $r = 6$ — from which $\gcd(2^3 - 1, 21) = 7$ and $\gcd(2^3+1, 21) = 3$. Factored.

Why this breaks cryptography. RSA's security is the hardness of factoring. The same period-finding engine solves discrete logarithms, breaking Diffie–Hellman and elliptic-curve cryptography — nearly all deployed public-key infrastructure. This is why NIST spent 2016–2024 standardizing post-quantum cryptography (lattice-based schemes such as ML-KEM), and why harvest now, decrypt later — recording encrypted traffic today to decrypt once machines mature — is treated as a live threat by security agencies.

Honest status check: the largest number faithfully factored by Shor's algorithm on real hardware remains laughably small (21, with caveats). Running Shor on RSA-2048 needs thousands of logical, error-corrected qubits — millions of physical qubits at current error rates. The algorithm is not the bottleneck; the hardware is (§5).

3.4 Quantum simulation: the original killer app

Feynman's original problem is also the most defensible speedup. A quantum system of $n$ particles requires a state vector in $2^n$ dimensions; exact classical simulation is exponential, full stop. A quantum computer represents the state natively with $n$ qubits.

Formally: a quantum system evolves under the Schrödinger equation with Hamiltonian $H$, and the state at time $t$ is $|\psi(t)\rangle = e^{-iHt}|\psi(0)\rangle$. For physically realistic Hamiltonians — a sum $H = \sum_j H_j$ of local terms — Lloyd (1996) showed the evolution compiles efficiently into gates via Trotterization:

$$e^{-iHt} = \lim_{m \to \infty} \left( \prod_j e^{-iH_j t/m} \right)^{m}$$

where each small step $e^{-iH_j t/m}$ touches only a few qubits and costs $O(1)$ gates; simulating to precision $\varepsilon$ costs polynomially many gates, and modern methods (qubitization, quantum signal processing) achieve essentially optimal scaling.

The expected applications are the ones where nature is quantum and classical approximations break down: strongly correlated electrons, transition-metal catalysis (the FeMo cofactor of nitrogenase — industrial nitrogen fixation — is the canonical target), high-temperature superconductivity, battery and materials chemistry, and lattice models in fundamental physics. Many researchers consider this, not cryptanalysis, the first economically real quantum advantage.

3.5 The rest of the zoo, briefly

Hidden subgroup problems. Period finding generalizes: the abelian cases (factoring, discrete log, Pell's equation) are solved; non-abelian cases (graph isomorphism, some lattice problems) remain open — which is precisely why post-quantum cryptography bets on lattices.
Quantum walks. Element distinctness in $O(N^{2/3})$, and the welded-tree problem's provable exponential walk speedup.
HHL (Harrow–Hassidim–Lloyd, 2009) solves linear systems $Ax = b$ in time polylogarithmic in the dimension — with serious caveats: the input must be efficiently loadable, $A$ sparse and well-conditioned, and the output is the quantum state $|x\rangle$, not the vector $x$. Several proposed exponential machine-learning applications of HHL were later dequantized by Ewin Tang (2018), who found classical algorithms matching them up to polynomial factors. A standing cautionary tale: always ask what the classical baseline really is.
Sampling problems (random circuit sampling, boson sampling): the basis of the 2019–2024 "quantum advantage" experiments. There is strong complexity-theoretic evidence that classical simulation of these tasks is intractable — but the tasks themselves are not, so far, useful.

4. The complexity-theoretic picture

Define BQP (bounded-error quantum polynomial time): decision problems solvable by a uniform family of polynomial-size quantum circuits with error probability at most $1/3$. It is the quantum analogue of BPP, the problems classical randomized computers solve efficiently.

What is actually proven:

$$\mathrm{P} \subseteq \mathrm{BPP} \subseteq \mathrm{BQP} \subseteq \mathrm{PSPACE}$$

The first two containments are easy — a quantum computer can run any classical computation reversibly, with Hadamards as coin flips. The last (Bernstein–Vazirani, 1997) holds because a classical machine can compute any final amplitude as a sum over exponentially many computational paths, reusing polynomial space per path: exponential time, polynomial space. An immediate corollary: quantum computers do not violate the Church–Turing thesis — they compute exactly the computable functions, and only the extended (polynomial-time) thesis is under attack.

Complexity class map: P inside BPP inside BQP inside PSPACE, with NP overlapping BQP but believed not contained in it

All drawn containments are proven; all strictness is conjectural. Factoring sits in the suggestive overlap: inside NP, inside BQP, believed outside BPP — and not believed NP-complete.

What is believed but unproven — and why proving it is hard:

BPP ⊊ BQP ("quantum computers are genuinely stronger"). Evidence: factoring is in BQP and appears not to be in BPP. Unproven because proving factoring hard would require lower-bound techniques nobody has; BPP = BQP is formally consistent with current knowledge. In the query model, separations are proven — Simon's problem, and Raz–Tal (2018) even exhibited an oracle relative to which BQP ⊄ PH.
NP ⊄ BQP ("quantum computers do not crack NP-complete problems"). Evidence: BBBV shows brute force gains only a square root, and thirty years of effort have produced nothing beyond Grover for SAT or TSP. Factoring, note, sits in NP ∩ co-NP — precisely the sort of structured intermediate problem quantum computers love, and not NP-complete.
Conversely, BQP ⊄ NP is also plausible: some quantum computations may not even have efficiently checkable classical certificates.

The pattern across every known speedup: exponential quantum advantage seems to require algebraic structure — periodicity, group symmetry, physical locality — that the QFT or a quantum walk can exploit through interference. Structureless problems get at most polynomial help. That is the honest, current answer to "what can they run faster."

5. Reality check: decoherence, error correction, timelines

Everything above assumed perfect qubits. Real qubits — superconducting circuits at 15 millikelvin, trapped ions, neutral atoms, photons — are catastrophically fragile. Any stray interaction with the environment acts as an unwanted measurement, collapsing superpositions: decoherence. Current hardware manages error rates around $10^{-3}$ per two-qubit gate; Shor on RSA-2048 needs circuits with $10^{10}$–$10^{12}$ operations. The gap is nine orders of magnitude.

The reason the field has not given up is the threshold theorem (Aharonov–Ben-Or, Kitaev, Knill–Laflamme–Zurek, c. 1996): if the physical error rate $p$ is below a constant threshold $p_{\mathrm{th}}$ (about 1% for the surface code), quantum error correction suppresses the logical error rate exponentially in the code distance $d$, at only polylogarithmic qubit overhead:

$$\varepsilon_{\mathrm{logical}} \sim \varepsilon_0 \left( \frac{p}{p_{\mathrm{th}}} \right)^{\lfloor (d+1)/2 \rfloor}$$

Error correction sidesteps no-cloning by never copying the state: it encodes one logical qubit into an entangled state of many physical qubits and measures only error syndromes — which error occurred — without ever measuring the data itself. The milestone of 2023–2025: Google and others demonstrated logical qubits whose error rate decreases as the code grows, the regime the threshold theorem promises. The field has crossed from "does error correction work?" to "scale it."

Roughly where that leaves timelines: useful error-corrected quantum simulation of chemistry, plausibly late this decade into the 2030s; cryptographically relevant Shor, most estimates say the 2030s. Uncertain — but no known physics forbids it, and the theory guarantees errors need only be good enough, never zero.

6. Summary: the honest scorecard

Task	Best classical	Quantum	Speedup	Status
Deutsch–Jozsa (deterministic)	$2^{n-1}+1$ queries	1 query	exponential, proven	toy problem
Simon's problem	$\Omega(2^{n/2})$ queries	$O(n)$ queries	exponential, proven	toy problem
Unstructured search	$\Theta(N)$	$\Theta(\sqrt{N})$	quadratic, provably optimal	needs cheap fault-tolerant ops
Factoring / discrete log	sub-exponential (GNFS)	$O((\log N)^3)$	superpolynomial vs. best known	needs ~10⁶ physical qubits
Quantum simulation	exponential (exact)	polynomial	exponential vs. exact methods	likely first real application
Linear systems (HHL)	poly	polylog, heavily caveated	partly dequantized	research
NP-complete problems	exponential	exponential (√ at best)	no exponential help (BBBV)	fundamental limit
Sorting, parsing, databases, your web app	fast	no better	none	quantum offers nothing

Three sentences to take away:

A quantum computer is a physics upgrade, not a speed upgrade — it computes with amplitudes that interfere, letting wrong answers cancel, and that mechanism only bites on problems with the right structure.
The proven wins are interference-shaped: algebraic periodicity (Shor — exponential), unstructured search (Grover — quadratic, and provably no better), and simulating quantum nature itself (Feynman's original point, and still the best bet for first real-world impact).
Everything else runs no faster — and in the query model that is a theorem, not a temporary shortage of cleverness.

Feynman's complaint — nature isn't classical, dammit — turned out to be a design document. We are, slowly and at 15 millikelvin, building the machine he ordered.

Quantum Computers, From First Principles: What They Are and What They Provably Run Faster