Quantum Computing for Mathematicians: From Four Axioms to Shor’s Algorithm

In 2000, a European government hired my team at CyberAgency to assess a question almost nobody was asking at the time: does a quantum computer threaten the cryptographic infrastructure the country had just spent years standardizing? The people I ended up briefing were mostly mathematicians. Cryptographers, to be precise, the kind who can quote the constant in the number field sieve’s exponent from memory and who treat any sentence containing the word “photon” as an attempt to waste their afternoon.

I tried the physics-first explanation exactly once, the full menu of superposition, Schrödinger’s cat, and many worlds. I got nothing back but skepticism, and I understood why. I had not answered a single question a mathematician actually asks: what the machine computes, how an algorithm works step by step, and where exactly the exponential is supposed to be hiding. Those questions have good mathematical answers. The physics is almost decorative.

Quantum advantage comes from a single mathematical mechanism, amplitudes that cancel, and every algorithm with a real speedup is a way of giving a problem enough structure that the wrong answers cancel on purpose. With that mechanism in hand, the whole field is one short story. Deutsch saw it, Simon generalized it, Shor aimed it at the integers, and Grover found its universal form. I tell that story below as quantum computing for mathematicians. I assume comfort with linear algebra, finite groups, and complexity classes, and no physics whatsoever.

I give the physics one paragraph, later, clearly marked.

Quantum computing for mathematicians starts with four axioms

Everything a quantum computer does is generated by four rules. Anyone who has studied functional analysis will find them suspiciously familiar, because they’re the axioms of quantum mechanics stripped of every physical interpretation and kept only as operator theory.

A1, state space. The state of an $$n$$-qubit register is a unit vector in $$\mathbb{C}^{2^n}$$, defined up to a global phase. For one qubit the standard basis is written $$|0\rangle, |1\rangle$$, and a general state is $$|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$$ with $$|\alpha|^2 + |\beta|^2 = 1$$. The coefficients, called amplitudes, are complex numbers, and every algorithm below depends on that fact.

I’ll use Dirac notation throughout, because every paper in this field is written in it. A ket $$|\psi\rangle$$ is a column vector and a bra $$\langle\psi|$$ is its conjugate transpose. An inner product is written $$\langle\phi|\psi\rangle$$ and an outer product $$|\psi\rangle\langle\phi|$$. Physicists are inordinately proud of the pun (bra, ket, bracket). Mathematicians note, correctly, that we already had notation for all of this. Both are right. Learn the kets anyway.

A2, composition. Joint systems are described by the tensor product of state spaces. For $$n$$ qubits that product is $$(\mathbb{C}^2)^{\otimes n} \cong \mathbb{C}^{2^n}$$. Concretely, the tensor product is the Kronecker product on coordinates, and the basis states of the joint system are the $$2^n$$ strings $$|x_1 x_2 \dots x_n\rangle$$. A state $$|\psi\rangle$$ of a bipartite system is called entangled if it cannot be written as $$|\phi\rangle \otimes |\chi\rangle$$. The canonical example is the Bell state:

$$$|\Phi^+\rangle = \frac{1}{\sqrt{2}}\left(|00\rangle + |11\rangle\right)$$$

Entanglement takes one line to prove. If the state factored, its amplitudes would satisfy $$(\alpha_0 \beta_0, \alpha_0 \beta_1, \alpha_1 \beta_0, \alpha_1 \beta_1) = \frac{1}{\sqrt{2}}(1, 0, 0, 1)$$, but $$\alpha_0 \beta_1 = 0$$ forces either $$\alpha_0 \beta_0 = 0$$ or $$\alpha_1 \beta_1 = 0$$. Nothing occult has occurred. Entanglement, at this level, is a property of a tensor’s rank decomposition. It is one of two features that distinguish the quantum state space from a classical probability simplex, and it is necessary for an exponential speedup while nowhere near sufficient.

A3, evolution. A closed system’s state changes by unitary maps, $$|\psi\rangle \mapsto U|\psi\rangle$$ with $$U U^\dagger = I$$. A computation is a sequence of unitaries drawn from a small gate set acting on one or two qubits at a time, composed by tensoring with identities. The standard gates are the Hadamard gate $$H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \ 1 & -1 \end{pmatrix}$$, the Pauli matrices $$X$$ and $$Z$$, the phase gate $$T = \mathrm{diag}(1, e^{i\pi/4})$$, and controlled-NOT, which maps $$|a, b\rangle$$ to $$|a, b \oplus a\rangle$$.

The set $${H, T, \mathrm{CNOT}}$$ is universal. Any unitary on any number of qubits can be approximated to any precision by circuits over it, and by the Solovay-Kitaev theorem the overhead is only polylogarithmic in the inverse precision. The standard reference is Nielsen and Chuang’s Quantum Computation and Quantum Information, with a readable proof in Dawson and Nielsen.

Every gate is also invertible, because unitaries are. Quantum computation is reversible computation. A non-invertible function $$f$$ is embedded as $$|x\rangle|y\rangle \mapsto |x\rangle|y \oplus f(x)\rangle$$, which is its own inverse. Charles Bennett proved in 1973 that any computation can be made reversible at modest cost. That classical result is the direct ancestor of this trick.

A4, measurement. Measuring an $$n$$-qubit state $$|\psi\rangle = \sum_x \alpha_x |x\rangle$$ in the computational basis returns the string $$x$$ with probability $$|\alpha_x|^2$$ and leaves the post-measurement state at $$|x\rangle$$. Measuring a subset of the register projects the unmeasured part onto whatever is consistent with the outcome.

By the norm-squared rule, a global phase is unobservable, since $$e^{i\theta}|\psi\rangle$$ and $$|\psi\rangle$$ give identical measurement statistics forever, which is why A1 defines states up to phase. A relative phase is very much observable, because it changes what later unitaries do. The whole craft of quantum algorithm design is arranging relative phases. And no measurement returns an amplitude $$\alpha_x$$ itself. Popular writers on quantum computing usually miss that restriction.

These four axioms, with historical footnotes, are the content of the field’s founding papers – Richard Feynman’s 1982 observation, in Simulating Physics with Computers, that nature is expensive to simulate on classical hardware, and David Deutsch’s 1985 construction of the universal quantum computer in the Proceedings of the Royal Society A.

Even the anti-physicists should hear Deutsch’s framing. He argued that the Church-Turing thesis is an empirical claim about nature, and that classical physics doesn’t support it. A Turing machine cannot efficiently simulate an arbitrary physical system. A quantum Turing machine, conjecturally, can. The mathematician’s version of that claim is the complexity class BQP, defined near the end of this article.

Now the promised physics paragraph. Axioms A1 through A4 happen to be obeyed, to high approximation, by certain well-isolated physical systems – superconducting circuits, trapped ions, neutral atoms, photons, spins. Building devices in which the axioms hold at low error rates, over long coherence times, and across many qubits is the entire engineering program of quantum computing. I track that program against the requirements of a cryptographically relevant machine in my CRQC Quantum Capability Framework. The hardware routes are a separate subject, covered in my taxonomy of quantum computing modalities. I don’t return to physics below, and from here on everything is linear algebra, probability, and group theory.

Quantum parallelism and the readout limit

In the popular explanation, a classical bit is 0 or 1 and a qubit is both at once. On that account, $$n$$ qubits hold all $$2^n$$ inputs simultaneously and the machine evaluates a function on all of them in parallel. The usual conclusion is that a quantum computer is a massively parallel machine, with exponential parallelism for free.

The first half of the story is even true. Given $$f: {0,1}^n \to {0,1}^m$$ implemented as a reversible circuit, applying it once to the uniform superposition gives

$$$\frac{1}{\sqrt{2^n}} \sum_{x \in {0,1}^n} |x\rangle|0\rangle ;\longmapsto; \frac{1}{\sqrt{2^n}} \sum_{x \in {0,1}^n} |x\rangle|f(x)\rangle$$$

and the state on the right does, in a precise sense, contain every value of $$f$$.

The second half fails, because an answer has to come out and the only extraction tool in the axioms is A4. Measure, and the result is one pair $$(x, f(x))$$, sampled uniformly at random. A coin plus one classical evaluation of $$f$$ produces the same distribution. The exponentially large state is real, but each measurement returns only one random sample of it.

Engineers cannot remove that limit, because Alexander Holevo proved in 1973 that $$n$$ qubits can communicate at most $$n$$ classical bits, no matter how cleverly sender and receiver encode and measure. The state space has $$2^n$$ complex dimensions and the readout channel has $$n$$ bits of capacity. Every quantum algorithm has to get its answer out through those $$n$$ bits.

So what is the computational resource, if not parallel evaluation? There are two answers, and the second explains far more than the first. The first resource is entanglement, with a converse attached. If a pure-state computation stays approximately separable at every step, a classical computer can track it efficiently, so an exponential speedup requires entanglement somewhere. Richard Jozsa and Noah Linden proved this in 2003 and, in the same paper, proved the converse fails.

Clifford circuits generate enormous entanglement, and Daniel Gottesman showed with his stabilizer formalism that a classical machine simulates them in polynomial time. Entanglement is necessary for an exponential speedup and nowhere near sufficient. Escaping the Clifford world has a price, the single largest line item in the hardware budget, and I put a number on it in the error-correction section below.

The second resource is interference, which exists because amplitudes are complex, so they can be negative, or better, pointed at each other. The probability of an outcome is $$|\sum_i \alpha_i|^2$$ rather than $$\sum_i |\alpha_i|^2$$, which means computational paths ending at the same basis state add as complex numbers before anything becomes a probability. Paths ending at wrong answers can be made to cancel. Paths ending at right answers can be made to reinforce. A quantum algorithm prepares a superposition, then evolves it so that amplitude moves onto useful outcomes before the final measurement.

Every quantum algorithm that beats its classical competition is, underneath the details, a machine for making wrong answers cancel, which requires structure. On an arbitrary, unstructured function there is nothing for the phases to synchronize against. I make that claim precise twice below, once for Fourier-structured problems, where exponential advantage exists, and once for unstructured search, where the provable ceiling is quadratic.

Interference, from Deutsch to Simon

The first algorithm built on cancellation was David Deutsch’s from 1985, a single-qubit proof of concept, and the first with room to scale was his 1992 algorithm with Richard Jozsa. Black-box access is given to $$f: {0,1}^n \to {0,1}$$ with a promise that $$f$$ is either constant or balanced, taking each value on exactly half its inputs. The task is to decide which. A deterministic classical algorithm needs $$2^{n-1} + 1$$ queries in the worst case, because any smaller number of zeros is consistent with both promises.

The quantum circuit is three layers deep. Prepare $$|0\rangle^{\otimes n}$$, apply $$H^{\otimes n}$$ for the uniform superposition, apply the oracle once with the output register in $$|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle – |1\rangle)$$, and apply $$H^{\otimes n}$$ again. The middle step, called phase kickback, is also the core of Simon’s algorithm and Shor’s. Since $$|-\rangle$$ is an eigenvector of the bit-flip, writing $$f(x)$$ into it doesn’t change the output register at all. Instead the value of $$f(x)$$ is kicked back into a phase, and the state becomes $$2^{-n/2}\sum_x (-1)^{f(x)}|x\rangle \otimes |-\rangle$$. After the final Hadamards, a short calculation gives the amplitude of the all-zero string:

$$$\alpha_{0^n} = \frac{1}{2^n} \sum_{x \in {0,1}^n} (-1)^{f(x)}$$$

That sum is, up to normalization, the zero-frequency Fourier coefficient of $$(-1)^f$$. For a constant $$f$$ every term agrees, so the amplitude is $$\pm 1$$ and the full weight concentrates on one outcome. For a balanced $$f$$ the terms cancel pairwise and the amplitude is exactly 0. Measure, and you get the answer with certainty after a single oracle call.

The speedup is over deterministic classical algorithms. A randomized classical algorithm solves Deutsch-Jozsa with a constant number of queries at bounded error, so there is no separation once coins are allowed. The oracle is also a black box, so the separation is not guaranteed to hold in the unrelativized world. The algorithm is taught first anyway, because it is the smallest complete example of the interference trick: phase kickback plus a Hadamard, the same two moves Shor’s algorithm uses.

Ethan Bernstein and Umesh Vazirani upgraded the trick in 1993, in the paper with which they founded quantum complexity theory. Their function is $$f(x) = s \cdot x \pmod 2$$ for a hidden string $$s$$. Run the same circuit and the state after the oracle is $$2^{-n/2}\sum_x (-1)^{s \cdot x}|x\rangle$$, which is exactly the Hadamard transform of the delta function at $$s$$, so the final $$H^{\otimes n}$$ inverts it and deposits all amplitude on $$|s\rangle$$. One query returns the whole hidden string, where a classical algorithm needs $$n$$ queries to learn it bit by bit.

Underneath is group theory. The Hadamard transform on $$(\mathbb{Z}/2)^n$$ is the Fourier transform of that group, and the algorithm works because the secret is a character of the group. Fourier sampling reads out hidden linear structure in one shot.

Daniel Simon pushed the same idea past linear structure in 1994, in On the Power of Quantum Computation. His promise is that $$f: {0,1}^n \to {0,1}^n$$ satisfies $$f(x) = f(y)$$ if and only if $$x \oplus y \in {0, s}$$ for a hidden mask $$s$$, and the task is to find $$s$$. Classically this is a collision problem, and a birthday argument gives a lower bound of order $$2^{n/2}$$ queries for bounded-error classical algorithms.

Simon’s algorithm runs the Deutsch-Jozsa circuit, then measures the value register, which projects the input qubits onto $$\frac{1}{\sqrt{2}}(|x_0\rangle + |x_0 \oplus s\rangle)$$ for some random $$x_0$$. Apply $$H^{\otimes n}$$ and the two terms interfere, and the amplitude on $$|y\rangle$$ becomes proportional to $$(-1)^{x_0 \cdot y}\big(1 + (-1)^{s \cdot y}\big)$$, zero on every $$y$$ with $$s \cdot y = 1$$ and uniform on those with $$s \cdot y = 0$$. Measurement now samples uniformly from the hyperplane orthogonal to $$s$$. Collect about $$n$$ independent samples, solve an $$n \times n$$ linear system over $$\mathbb{F}_2$$, and $$s$$ falls out. Simon spends about $$n$$ quantum queries where a classical algorithm spends exponentially many. In 1994 that was the strongest evidence yet of an exponential speedup from interference.

Simon’s algorithm contains the whole template in four moves. Superpose over a group, evaluate the function into a phase, Fourier-sample, and clean up with linear algebra. Everything in the next section is this template with $$(\mathbb{Z}/2)^n$$ replaced by a much richer group.

Shor’s algorithm is Fourier analysis on a finite group

Peter Shor announced his factoring algorithm in 1994, at the same FOCS conference as Simon’s result. I’ve written before about what it means for cryptography and which specific schemes it breaks, RSA, Diffie-Hellman, DSA, and their elliptic-curve descendants, all of them. Here I take the algorithm apart as mathematics, because once disassembled it contains no quantum mystique at all. It contains a classical number-theoretic reduction from 1976, a unitary whose eigenvalues encode a period, and the Fourier transform that reads them out. Shor’s paper in the SIAM Journal on Computing remains the standard reference.

From factoring to period finding

Let $$N$$ be the odd composite to be factored. The bridge from factoring to periodicity is elementary modular arithmetic, the difference of squares $$a^r – 1 = (a^{r/2} – 1)(a^{r/2} + 1)$$. Pick a random $$a$$ coprime to $$N$$ and let $$r$$ be its order modulo $$N$$, the least positive integer with $$a^r \equiv 1 \pmod{N}$$. If $$r$$ is even and $$a^{r/2} \not\equiv -1 \pmod{N}$$, then $$N$$ divides the product $$(a^{r/2}-1)(a^{r/2}+1)$$ while dividing neither factor, so $$\gcd(a^{r/2} \pm 1, N)$$ reveals a nontrivial factor of $$N$$.

The reduction first appeared in Gary Miller’s 1976 paper. A counting argument shows that for $$N$$ with at least two distinct odd prime factors, at least half of all choices of $$a$$ work. Factoring therefore reduces to finding the order $$r$$ of $$a$$, which is the period of $$f(x) = a^x \bmod N$$, a periodic function on the integers.

Classically, finding that period is as hard as factoring, with no known shortcut. On a quantum computer, period finding becomes a spectral problem. Define the unitary $$U_a: |y\rangle \mapsto |ay \bmod N\rangle$$ on the computational basis states coprime to $$N$$. It is a permutation matrix of order $$r$$, and its eigenvalues are the $$r$$-th roots of unity. For each $$k \in {0, \dots, r-1}$$, the vector

$$$|u_k\rangle = \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} e^{-2\pi i k s / r} |a^s \bmod N\rangle$$$

satisfies $$U_a |u_k\rangle = e^{2\pi i k / r} |u_k\rangle$$. The period is encoded in the eigenphases, and anyone who can estimate the phase $$k/r$$ to enough digits can recover $$r$$.

Phase estimation and the quantum Fourier transform

Alexei Kitaev solved the general problem, estimating an eigenphase of a unitary one can apply, in a 1995 paper in which he also generalized Shor’s construction to arbitrary finite abelian groups. Phase estimation is now the engine of half the quantum algorithm literature. Its tool is the quantum Fourier transform:

$$$\mathrm{QFT}{2^n}: |j\rangle \mapsto \frac{1}{\sqrt{2^n}} \sum{k=0}^{2^n – 1} e^{2\pi i j k / 2^n} |k\rangle$$$

The QFT is fast because it has the recursive structure of the Cooley-Tukey FFT, so $$\mathrm{QFT}_{2^n}$$ can be built from $$O(n^2)$$ one- and two-qubit gates, Hadamards and controlled phase rotations. Don Coppersmith showed that dropping the small-angle rotations leaves an approximate QFT good enough for factoring at even lower cost. Against the classical FFT’s $$O(n,2^n)$$ operations on $$2^n$$ coefficients, that is a transform of an exponentially long vector for polynomial effort.

That speed is not directly usable, because the output of the QFT is another quantum state. Measuring that state yields one sample from the spectral distribution rather than the $$2^n$$ Fourier coefficients. This is Holevo’s bound again.

In Shor’s algorithm the QFT is a subroutine whose output is sampled once per run. The spectrum of a periodic function concentrates on approximations of multiples of $$2^n / r$$, so a single sample already contains information about the period. Run the estimation to obtain a fraction near $$k/r$$ for a random $$k$$. Round it with the continued-fraction algorithm to recover $$r$$ in lowest terms, and repeat a few times to cover $$\gcd(k, r) > 1$$. All of it is elementary, and the only non-classical ingredient is interference, the amplitude cancellation introduced with Deutsch and Simon.

For the cryptographers in the room, most of the cost is in modular exponentiation, done reversibly. With schoolbook arithmetic the whole algorithm runs in about $$O(n^3)$$ gates for an $$n$$-bit modulus with $$O(n)$$ logical qubits, and the constants have been driven down steadily for three decades. The current state of knowledge, tracked in the Quantum Algorithm Zoo, is $$\widetilde{O}(n^3)$$. The best classical factoring algorithm, the general number field sieve, runs in heuristic time $$\exp!\big(O(n^{1/3} \log^{2/3} n)\big)$$. That gap, polynomial against subexponential, is the entire technical content of the quantum threat to public-key cryptography.

The hidden subgroup problem, abelian and non-abelian

In Kitaev’s reformulation, factoring and discrete logarithms are instances of one problem, the hidden subgroup problem. Given a function on a group $$G$$ that is constant on cosets of an unknown subgroup $$H$$ and distinct across cosets, find $$H$$. For every finitely generated abelian $$G$$, the problem can be solved in quantum polynomial time with the Simon template, by Fourier analysis on the group. The standard survey is Childs and van Dam in Reviews of Modern Physics.

Discrete log in $$\mathbb{Z}_p^\times$$ and on elliptic curves is solved by the same machinery. The elliptic-curve variants of Diffie-Hellman and DSA are therefore just as vulnerable, and researchers in the qubit-reduction race described below have now turned to ECC as well.

For non-abelian groups the problem is open in general. A polynomial-time algorithm for the hidden subgroup problem over the symmetric group would solve graph isomorphism. Over the dihedral group, such an algorithm would break certain lattice problems. Nobody has found one. Greg Kuperberg’s dihedral algorithm runs in time $$2^{O(\sqrt{\log N})}$$, subexponential but not polynomial. In two decades nobody has moved that exponent. Whether quantum Fourier sampling can settle the non-abelian cases is a pure representation-theory question, and I count it among the best open problems in the field. Mathematicians are welcome, obviously.

Improvements to Shor’s algorithm since 2023

Shor’s algorithm hasn’t been replaced, but researchers have rebuilt its arithmetic twice recently, and anyone planning against it needs to follow those changes. In 2023 Oded Regev gave a factoring algorithm using $$O(n^{3/2})$$ quantum gates instead of $$O(n^3)$$, at the price of running a smaller circuit $$\sqrt{n}$$ times plus a number-theoretic heuristic, and Seyoon Ragavan and Vinod Vaikuntanathan then cut its space requirements.

In 2024 Clémence Chevignard, Pierre-Alain Fouque, and André Schrottenloher broke the folklore barrier that modular arithmetic needs an $$n$$-qubit work register. With their method, an $$n$$-bit RSA modulus can be factored with $$n/2 + o(n)$$ logical qubits. For RSA-2048, the version published at CRYPTO 2025 needs 1,730 logical qubits and $$2^{36}$$ Toffoli gates per run, at roughly 40 runs on average. Regev and Chevignard, Fouque, and Schrottenloher left the asymptotic threat model unchanged and shrank the machine required to realize it.

Craig Gidney at Google Quantum AI keeps the physical-resource ledger. In 2021 he and Martin Ekerå estimated that 20 million noisy physical qubits, at a 0.1% gate error rate and a one-microsecond surface-code cycle, could factor RSA-2048 in eight hours. I covered that estimate in Breaking RSA-2048 with 20M Qubits.

In May 2025 Gidney cut the number by a factor of 20. The new machine needs fewer than one million noisy qubits and 1,409 logical ones at peak, and it runs in under one week on the same hardware assumptions. The design is built on the Chevignard-Fouque-Schrottenloher arithmetic, yoked surface codes, and magic state cultivation. My analysis of that estimate is here, and researchers have kept cutting the number since. The authors of the 2026 Pinnacle Architecture proposal sketch RSA-2048 broken with roughly 100,000 physical qubits on quantum LDPC codes, with caveats I lay out in that piece.

It took four years and no new physics to get that factor of 20. All of it came from improved arithmetic circuits, codes, and resource accounting. Gidney closes his paper with the cryptographers’ proverb that attacks always get better, and adds that he’d rather security not depend on progress staying slow. So would I.

What the hardware has factored so far

The largest integers factored on quantum hardware by anything resembling a faithful run of Shor’s algorithm remain embarrassingly small. The records are 15, in the 2001 NMR experiment by Lieven Vandersypen and colleagues at IBM, and 21, in a later photonic demonstration. Even those runs were compiled down to fit their devices. John Smolin, Graeme Smith, and Alexander Vargo showed in Nature that such compiling can simplify the quantum part to the point of vacuity. Their title, “Oversimplifying quantum factoring,” says most of it.

Larger records exist, like the 48-bit number factored with a hybrid quantum-classical optimizer, but conventional computers did most of the work in them. I dissected that claim in 48-Bit RSA vs. RSA-2048, and Scholten and colleagues reach the same conclusion in their sober survey. On digital quantum hardware, the factoring record with the full algorithm is a number you can factor in your head. The classical record now belongs to Eric Lu at Cognition, who factored RSA-260 at 862 bits in September 2026 with a GPU-accelerated number field sieve. Boudot, Gaudry, Guillevic, Heninger, Thomé, and Zimmermann had held the previous record, RSA-250 at 829 bits, since 2020. That is 33 bits in six years. RSA-2048 is 1,186 bits longer than RSA-260, and the classical cost of factoring grows subexponentially with that length. I keep the running tally in Quantum Computers Have Only Factored 15 and 21.

In 1994, the year Shor published, about 600 volunteers on the early internet finished factoring RSA-129, a 426-bit challenge number, after eight months of distributed sieving, and the recovered plaintext read “the magic words are squeamish ossifrage,” as Atkins, Graff, Lenstra, and Leyland reported. Three decades on, the classical record is 862 bits and the quantum record is 5 bits. The algorithm is proven correct, but nobody has yet built a machine that can run it at a useful size.

Grover and the ceiling on black-box search

Lov Grover published the second famous quantum algorithm in 1996, and it is the interference trick in its purest form, with no number theory or group structure, only geometry. The problem is unstructured search. An oracle $$\chi$$ marks one of $$N$$ items, $$\chi(x) = 1$$ if and only if $$x = w$$, and the task is to find $$w$$.

You can do the whole analysis in a plane. Only two states are involved, the marked state $$|w\rangle$$ and the uniform superposition over everything else. The initial uniform superposition $$|s\rangle$$ is a vector in the two-dimensional space they span, at angle $$\theta$$ to the unmarked axis, with $$\sin\theta = 1/\sqrt{N}$$. One Grover iteration is a pair of reflections. Flip the phase of the marked state, one oracle call using the same phase kickback as before, then reflect about $$|s\rangle$$. Two reflections compose to a rotation through $$2\theta$$, and after about $$\frac{\pi}{4}\sqrt{N}$$ iterations the state vector has rotated onto $$|w\rangle$$, so measurement returns the marked item with probability near one. That is $$O(\sqrt{N})$$ oracle calls against the classical $$\Theta(N)$$.

I’ve written separately about what Grover’s algorithm does to symmetric cryptography. It halves the security exponent, so AES-128 drops to 64-bit security against a large fault-tolerant machine while AES-256 keeps 128 bits, comfortably out of reach. Shor breaks public-key schemes outright and Grover only weakens symmetric ones, which is why the post-quantum transition is mostly a public-key story.

Charles Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani proved in 1997 that any quantum algorithm for unstructured search needs $$\Omega(\sqrt{N})$$ black-box queries, so Grover is exactly optimal. That optimality is the mathematical answer to the most common misconception about quantum computing: without structure in the problem, the best possible improvement is quadratic.

Exponential speedups require structure, periodicity, hidden subgroups, spectral gaps, something the phases can synchronize with. Because of the same bound, the sane default assumption is that quantum computers won’t solve NP-complete problems efficiently. Grover applied to Boolean satisfiability gives $$O(2^{n/2})$$, which beats naive brute force and remains exponential. The BBBV bound applies to structureless search on any quantum hardware.

Brassard, Høyer, Mosca, and Tapp generalized Grover’s construction into amplitude amplification, one of the most used primitives in the field. Any classical randomized procedure succeeding with probability $$p$$ can be boosted to succeed in $$O(1/\sqrt{p})$$ repetitions quantumly, and quadratic speedups for estimating means, counts, and partition functions follow from the same rotation machinery. When a vendor advertises quantum-accelerated Monte Carlo risk simulation, amplitude amplification is what they mean. The “quadratic” in the fine print comes from the BBBV bound, so their engineers cannot improve on it.

Three families of exponential speedup

Exponential advantage requires structure, and most of the known exponential speedups fall into three families. I map the full territory, including everything quantum computers are for beyond cryptography, in a companion piece, What Quantum Computers Are For.

Simulating quantum systems

Simulation is the problem the field was invented for. Feynman’s 1982 observation was that the state space of $$n$$ quantum particles has $$2^n$$ dimensions, so a classical simulation of it is exponentially expensive, while a quantum system undergoes that evolution at no extra cost. Seth Lloyd turned the remark into an algorithm in a 1996 paper in Science. For a local Hamiltonian $$H = \sum_j H_j$$, where each $$H_j$$ acts on a constant number of qubits, the Lie-Trotter formula gives

$$$e^{-iHt} \approx \left(\prod_j e^{-iH_j t/m}\right)^m$$$

with error controlled by standard product-formula bounds, so time evolution under $$H$$ decomposes into polynomially many local unitaries. The exponential advantage here is believable in a way most exponential claims are not, because the output is itself a quantum state, or a spectral quantity extracted from one by phase estimation. There is no readout bottleneck. Ground-state energies, reaction dynamics, and correlation functions are already quantum-shaped questions. Simulating local Hamiltonian evolution is, in the precise complexity-theoretic sense, a complete problem for quantum computers, which means every problem they solve efficiently reduces to it. The standard reference is Kitaev, Shen, and Vyalyi.

The flagship targets are in chemistry and materials, such as the FeMo cofactor of nitrogenase, high-temperature superconductors, and battery electrolytes. In 2017 Reiher, Wiebe, Svore, Steiger, and Troyer priced the FeMo cofactor in fault-tolerant resources, and with that paper they put a concrete molecule on the roadmap. If quantum computers transform an industry before they affect cryptography, chemistry and materials are the most plausible candidates.

The HHL algorithm for linear systems

The 2009 HHL algorithm of Aram Harrow, Avinatan Hassidim, and Seth Lloyd solves an $$N \times N$$ sparse, well-conditioned linear system in time polynomial in $$\log N$$, the condition number $$\kappa$$, and $$1/\epsilon$$, an exponential speedup over classical Gaussian elimination. It works by phase-estimating $$e^{iAt}$$ and rotating each eigenvalue $$\lambda_j$$ into its inverse, spectral calculus on $$A^{-1}$$ performed in amplitude space.

The speedup comes with four asterisks, and Scott Aaronson spells them out in his essay Read the Fine Print. The input vector $$|b\rangle$$ must be cheaply preparable as a quantum state, the matrix must be sparse or otherwise efficiently simulable, the condition number must be small, and the output is the state $$|x\rangle$$ rather than the vector $$x$$. Reading out all $$N$$ components destroys the exponential advantage. HHL is a superb subroutine inside larger quantum computations. As a replacement for a classical solver in numerical analysis, it is usually a rounding error with a press release.

Dequantization and auditing quantum claims

In 2017 Iordanis Kerenidis and Anupam Prakash published a quantum recommendation-systems algorithm exponentially faster than any classical algorithm then known for this machine-learning staple. In 2018 Ewin Tang, then an undergraduate at UT Austin, found a classical algorithm with the same polylogarithmic dependence on dimension. Her key move was to grant the classical algorithm the same sampling access the quantum algorithm implicitly assumed, and with that access there is no exponential advantage left. Tang and others then dequantized most of the early quantum machine-learning literature, and I know of no better short read on the episode than her own overview of quantum-inspired sampling.

From the dequantization episode I take the claim-evidence test I apply on this blog whenever a vendor announces a breakthrough. Ask where the input data comes from and at what cost, and where the output goes and at what cost. Then ask whether the classical baseline was allowed the same concessions. An exponential speedup located entirely in the data-loading assumptions is an accounting choice, and RSA is safe from it.

BQP and the complexity map

Complexity theory is the part of this subject mathematicians usually enjoy most, and once the definitions are stated little remains to add. Bernstein and Vazirani defined BQP, bounded-error quantum polynomial time, in their 1993 paper. It is the class of languages decidable by a uniform family of polynomial-size quantum circuits with two-sided error at most $$1/3$$. The constant is arbitrary, repeat and amplify, and the class doesn’t depend on the choice of universal gate set, by Solovay-Kitaev. The known inclusions are $$\mathrm{P} \subseteq \mathrm{BPP} \subseteq \mathrm{BQP} \subseteq \mathrm{PP} \subseteq \mathrm{PSPACE}$$, with BQP $$\subseteq$$ PP due to Adleman, DeMarrais, and Huang.

We cannot yet prove the separations we believe. Anyone who proves BPP $$\neq$$ BQP will also have proved P $$\neq$$ PSPACE, which is beyond current technique, so the evidence is relativized and circumstantial. As such evidence goes, it is unusually good. Simon’s problem gives an oracle relative to which BQP separates exponentially from BPP. Ran Raz and Avishay Tal proved in 2018 that an oracle exists relative to which BQP is not contained in the entire polynomial hierarchy, and with that they settled a conjecture Scott Aaronson had framed around the forrelation problem. The write-up is ECCC TR18-107, presented at STOC 2019 and published in the Journal of the ACM in 2022.

In the other direction, BBBV gives an oracle relative to which NP is not in BQP. Factoring is in NP $$\cap$$ co-NP and is not believed to be NP-complete. It is structured enough for a quantum attack by Fourier analysis, yet it has resisted four decades of classical effort. The current map is in the Complexity Zoo, for the two of you who don’t already have it bookmarked.

The sampling experiments of the last few years are in a different corner of this map. In 2019 Google’s team used the Sycamore processor to sample the output distribution of a random 53-qubit circuit in 200 seconds and estimated the classical cost at 10,000 years. IBM’s team replied that with enough disk it was more like two and a half days, and by 2022 Pan and Zhang were simulating larger instances on a GPU cluster with tensor networks. USTC’s team went through the same cycle with boson sampling, Aaronson and Arkhipov’s proposal, in its Jiuzhang photonic experiments.

The teams behind these experiments demonstrated advantage on contrived sampling tasks whose classical hardness depends on plausible but unproven assumptions, which is a result for complexity theory. After every claim so far, classical researchers have narrowed the gap. None of it is evidence about factoring, simulation, or optimization, and a sampling milestone is still far from a cryptographically relevant quantum computer.

Decoherence, error correction, and the state of the hardware

The four axioms describe an idealization that real devices obey only approximately, and they depart from it in a specific, stateable way. No system is isolated. Each one couples to an environment $$E$$, and the joint evolution entangles the two. Tracing out $$E$$ turns the system’s pure state into a mixed one, a density operator $$\rho$$ whose off-diagonal entries decay. That decay is decoherence. It is fatal precisely where quantum computation happens, because the interference terms are the off-diagonal entries. A decohered superposition is a classical probability distribution, and one over $$2^n$$ outcomes is exactly as useful as it sounds.

Every quantum computation is a race to finish the interference before the off-diagonal entries decay.

The escape is quantum error correction, and I consider its existence the single most important theoretical fact about the feasibility of quantum computing. The idea comes from classical coding theory, with one twist. The encoded data cannot be inspected directly, since measurement disturbs it, so only syndromes are read out, parities that reveal which error occurred without revealing the encoded state. Peter Shor built the first code in 1995, 9 physical qubits protecting 1 logical qubit. Andrew Steane’s 7-qubit code followed, and Daniel Gottesman turned the construction into algebra with his stabilizer formalism.

Then came the threshold theorem, proved independently by Aharonov and Ben-Or, by Knill, Laflamme, and Zurek, and by Kitaev: if the physical error rate per gate is below a constant threshold $$p_{\mathrm{th}}$$, encoding into ever larger codes drives the logical error rate down exponentially in the code size, at only polylogarithmic overhead. Arbitrarily long quantum computation on noisy hardware is possible in principle. With the threshold theorem, a physics problem becomes an engineering budget. My standing explainer on it is Capability B.1, Quantum Error Correction.

Physical qubits are the noisy devices and logical qubits are the error-corrected units a computation uses, and the ratio between them is the overhead. For the leading candidate, Kitaev’s surface code, with its forgiving threshold near 1% per gate in the standard noise models, per Fowler, Mariantoni, Martinis, and Cleland, the overhead runs from hundreds to thousands of physical qubits per logical qubit, depending on the error rate and the required logical fidelity. When a company announces “a 1,000-qubit processor,” the first question is which kind, and today the answer is almost always noisy physical ones.

As of mid-2026, hardware teams have demonstrated error rates below the threshold, which nobody had done five years ago. Google’s team demonstrated below-threshold operation on its Willow processor and reported it in Nature. Logical error per cycle fell by a factor of 2.14 for every two steps of surface-code distance, a logical qubit of code distance 7 outlived its best physical qubit by a factor of 2.4, and a real-time decoder kept pace at a million cycles per second.

Quantinuum encoded 98 physical qubits into 48 fully error-corrected logical qubits on its trapped-ion Helios system, at a two-to-one encoding ratio, with logical performance better than the underlying physical qubits. I covered the launch in Quantinuum’s logical-qubit milestone. Before Helios, Quantinuum and Microsoft had cut logical error rates by a factor of 800 in a joint run. Neutral-atom teams have demonstrated 48 logical qubits and, the bigger deal in my view, magic-state distillation performed entirely at the logical level.

IBM, betting that quantum LDPC codes need less overhead than the surface code, published the gross code – 144 data qubits encoding 12 logical ones, 288 physical once the check qubits are counted – and committed to a 200-logical-qubit machine called Starling by 2029 with a 2,000-logical-qubit successor targeted for the early 2030s. I cover that bet in my primer on quantum low-density parity-check codes.

Clifford gates, the cheap transversal ones, are by Gottesman-Knill the classically simulable part of the gate set, so universal computation needs non-Clifford resources like the $$T$$ gate. Fault-tolerant $$T$$ gates are manufactured from many noisy $$\frac{1}{\sqrt{2}}(|0\rangle + e^{i\pi/4}|1\rangle)$$ states inside dedicated factory blocks that take up most of the floor plan of current designs.

The factory economics come from Fowler and Gidney. The recent cost reductions come from magic state cultivation by Gidney, Shutty, and Jones and from the yoked surface codes of Gidney, Newman, Brooks, and Jones. I track the requirement in my framework as Capability C.2, Magic State Production. Gidney’s million-qubit factoring machine is, by floor area, mostly a magic-state farm with some arithmetic attached.

To build a machine that factors RSA-2048, hardware teams still have to get from roughly $$10^2$$ logical qubits today to Gidney’s 1,409 at much higher fidelity, from magic-state demonstrations to factories producing on the order of $$10^9$$ distilled non-Clifford states, and from microsecond-cycling lab devices to a system that executes $$10^{12}$$ gates without an uncorrected error. That gap is enormous, and for the first time in the field’s history it consists of named engineering problems with measured exponents attached. None of them is an open question of principle.

Defenders already work to regulatory deadlines: in its draft transition guidance, NIST sets 2030 for deprecating 112-bit classical security and 2035 for disallowing it, and under federal policy the 2030 date is already a compliance deadline for high-value systems. So Q-Day deadlines are set whether or not the hardware arrives on schedule. Because adversaries can harvest encrypted data now and decrypt it later, the effective deadline is earlier than the nominal one.

The scarce resource is mathematicians

At this point in the field’s history, I think the rate-limiting talent is mathematical rather than physical, and I base that opinion on two episodes.

On the defense side, the post-quantum standards are mathematics all the way down. NIST’s first three finalized standards, published in August 2024, are ML-KEM, standardized as FIPS 203 from CRYSTALS-Kyber with security based on module learning-with-errors over lattices; ML-DSA, FIPS 204, from CRYSTALS-Dilithium on the same foundation; and SLH-DSA, FIPS 205, the SPHINCS+ hash-based signature. FN-DSA, the NTRU-lattice signature built from FALCON, remains in draft as FIPS 206, and in March 2025 NIST selected HQC, a code-based scheme, as the backup key-establishment mechanism. I walk through the whole portfolio in Post-Quantum Cryptography and the NIST Standards.

Every one of those schemes is exactly as strong as one mathematical problem is hard, and the only security audit such hardness assumptions ever get is mathematicians trying to break them. In 2022 Wouter Castryck and Thomas Decru broke SIKE, a fourth-round isogeny-based candidate, with a classical attack that ran on a single core in about an hour. Two number theorists found the right theorem of Ernst Kani’s to aim at SIKE, and a decade of parameter engineering was over.

On the offense side, Yilei Chen of Tsinghua posted, on April 10, 2024, a polynomial-time quantum algorithm for lattice problems that, if correct, would have threatened the LWE assumption behind ML-KEM and ML-DSA. By April 18 Chen had added a withdrawal note to the paper. Hongxun Wu and, independently, Thomas Vidick had found a bug in Step 9 that Chen didn’t know how to fix, and by his own note the headline claim “does not hold.” The whole episode took eight days.

The lattice standards stayed as they were because the world’s lattice mathematicians read the paper. That is a fragile control to rely on forever. Someone will write the next paper in that genre, and the defense would be stronger if more of the people equipped to find the bug were already working on lattices before it appears.

Mathematicians also drive progress inside quantum computing itself. The people who moved the factoring numbers in the last three years were Regev with his multidimensional arithmetic, Chevignard, Fouque, and Schrottenloher with their qubit reduction, Gidney with his circuit and factory accounting, and the algebraic coding theorists behind better LDPC codes.

Those advances came from number and coding theory and from combinatorics, aimed at a quantum target, and none required a new qubit. To a mathematician, the Quantum Algorithm Zoo is a list of open invitations, such as hidden subgroup problems over non-abelian groups, quantum algorithms for lattice problems after Chen, the true boundary of dequantization, and improved decoders for newer codes. Meanwhile the hardware keeps improving on schedule, and understanding it does not require more physicists.

The interesting unsolved problems in quantum computing are now mathematics problems with a physics budget attached. The cryptanalysis of the replacement standards is mathematics, and so is the quantum-algorithm frontier. The error-correction overhead is fast becoming a problem in algebraic coding theory. A mathematician wondering whether there is room in the field should know that the invitation has been open since roughly 1994, and it is considerably more concrete now than it was then.

A reading path for mathematicians

Ordered roughly by on-ramp steepness, all free unless noted:

1. Andy Matuschak and Michael Nielsen, Quantum Computing for the Very Curious. The fastest honest zero-to-one I know of, written as an essay with spaced-repetition prompts on exactly the axioms-to-Shor arc of this article.
2. Ronald de Wolf, Quantum Computing: Lecture Notes. Written from the theoretical computer science side, closest in spirit to this article, with the query-complexity machinery done properly.
3. Michael Nielsen and Isaac Chuang, Quantum Computation and Quantum Information. The standard reference since 2000. Not free, but every library has it, and chapters 4 through 6 are the algorithms above in full dress.
4. Alexei Kitaev, Alexander Shen, and Mikhail Vyalyi, Classical and Quantum Computation. The most mathematical treatment I know of, including the BQP-completeness material and Kitaev’s phase estimation from the source.
5. Scott Aaronson, Quantum Computing since Democritus, plus his free lecture notes. The complexity-theoretic soul of the subject, written by what I consider its funniest living expositor.
6. John Preskill, Ph219/CS219 lecture notes. The theorist’s course, and the best free treatment I know of fault tolerance and the threshold theorem.
7. John Watrous, The Theory of Quantum Information. Density operators, channels, and semidefinite programs at full rigor.
8. J. M. Landsberg, A Very Brief Introduction to Quantum Computing and Quantum Information Theory for Mathematicians. Aimed at geometers, with the representation theory foregrounded.
9. Stephen Jordan’s Quantum Algorithm Zoo. The catalog of what is known, with citations and speedup classifications. Treat it as the frontier map.

Alongside the reading, compute the algorithm by hand once. Take $$N = 15$$ and $$a = 2$$ and carry the period-finding circuit through to the measured fractions. The QFT on the counting register is small enough for paper. Every mathematician I know who did this stopped finding quantum computing mysterious, because by hand the calculation is plain bookkeeping.

When you are ready for the modern literature, read Gidney’s 2025 resource estimate as a capstone. It is long, and it is the cleanest example I know of what the field’s mathematics looks like when aimed at a machine that could actually exist.

What changed between 2000 and 2026

In that briefing room in 2000, I eventually put the physics away and wrote four axioms on a whiteboard. The questions stopped being about cats and started being about continued fractions, which is where they belonged. In 2026 the axioms still fit on one whiteboard. The algorithms are still the ones Deutsch, Simon, Shor, and Grover found in the first decade, plus a long tail of refinements. What changed is the machine. Error rates are below threshold now, logical qubits exist in the dozens, resource estimates shrink by an order of magnitude every few years, and the regulators stopped waiting for physicists to finish before setting dates.

You already own the mathematics, though: linear algebra with a strange norm, probability with complex weights, Fourier analysis on finite groups, coding theory, and complexity classes. The physicists are building the engine. What it can and cannot compute is a question written entirely in your notation.