What Quantum Computers Are For: A Mathematician’s Map of Quantum Advantage

In December 2015, Nature published a result that more mathematicians should have noticed. Toby Cubitt, David Perez-Garcia, and Michael Wolf proved the spectral gap problem undecidable, in Nature 528, with the full 143-page proof on arXiv. They constructed families of translationally invariant, nearest-neighbor Hamiltonians on a 2D lattice such that telling whether the system has an energy gap above its ground state is equivalent to the halting problem.

Even with the strongest possible promise, that the system is either gapped or gapless in the thermodynamic limit, no algorithm decides which.

Johannes Bausch and collaborators later pushed the same result down to one-dimensional chains. Deciding the spectral gap in those constructions is a finite-spin-lattice cousin of the Yang-Mills mass gap problem, the one with a Millennium Prize attached. It too is undecidable.

Whatever quantum mechanics is computationally, then, it is not classical mechanics with a faster clock. The problems that quantum devices handle natively and the problems classical computers choke on are related in a way one can state precisely, once the question is asked in the right language. Given a well-posed mathematical problem, what determines whether a quantum computer solves it faster?

What quantum computers are for is three shapes of problem. First, problems whose answer is itself a quantum state or a spectral quantity, which means simulating molecules and materials, the domain where the advantage is a tautology rather than a trick. Second, problems with a hidden global algebraic structure, such as a period, a subgroup, a class group, or a knot invariant, which a quantum computer can read out in one Fourier sample. Third, generic search, where the advantage is real, quadratic, and provably capped there.

Combinatorics, the field most people picture when they hear “hard problems,” falls almost entirely into the third category. The reasons come from three theorems, Simon’s classical lower bound, the BBBV optimality of Grover, and the Bravyi-Gosset-König unconditional separation, and I lay out each below.

In a companion piece, Quantum Computing for Mathematicians, I go slowly through the four axioms, the interference mechanism, and Shor’s algorithm with full derivations, since most of my own work is in cryptography. Here I assume none of it and move faster over the shared ground.

This article is a classification, written for the mathematician who has asked what quantum computers are for, what qubits add to classical bits, and whether the answer is combinatorics. It isn’t, for reasons I give in the second half.

Bits, probability vectors, and qubits

To see what a qubit adds, line up three computers and write down their state spaces. All three models compute with $$n$$ two-valued registers and evolve by local gates. The three models differ only in what a “state” is allowed to be.

A stochastic matrix preserves the $$L^1$$ geometry of the simplex, a unitary the $$L^2$$ geometry of the sphere. On the simplex all coordinates are non-negative, so computational paths can only accumulate. Probability there is a sum of non-negative terms, full stop.

On the sphere, coordinates are complex, and paths ending at the same point can cancel. Interference is the difference between $$L^1$$ and $$L^2$$ geometry, and it is unavailable to any classical probabilistic computer for exactly that geometric reason.

In the simplex, the pure states are the vertices, the deterministic configurations. A pure joint state there automatically has pure marginals. Correlated states lie in the interior, because the moment two classical bits are correlated their joint state is mixed, and no pure state represents the correlation itself.

In $$\mathbb{CP}^{,2^n-1}$$ the opposite happens. The Bell state $$\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$$ is a pure joint state whose one-qubit marginals are maximally mixed. Quantum mechanics admits undiluted correlation, a pure global state with impure parts, and no classical probability distribution has that property. That is entanglement, stated without any physics.

In all three models, the interesting dynamics is generated by local gates, maps touching one or two registers at a time, but the local generators differ in what they can create. Local stochastic maps starting from a vertex never produce anything but mixtures over configurations, while local unitaries starting from a basis state produce Bell states and everything beyond.

Every point of the simplex is a mixture of fully determined configurations, and local unitaries reach states whose correlations across different choices of local measurement no such mixture can reproduce. Made precise, that statement is Bell’s theorem, and I’ll leave it at the citation.

In the classical models, the state is the readout. A probability vector is already its own statistics, and inspecting it costs nothing. In the quantum model, the state is hidden behind the Born rule, which converts the $$L^2$$ description into an $$L^1$$ one, once, destructively. Alexander Holevo made the cost precise with his 1973 bound: from $$n$$ qubits, at most $$n$$ classical bits ever come out.

The quantum computer is an exponentially large workspace interrogated only through an $$n$$-bit keyhole, and I derive the consequences in the companion article. Every quantum algorithm is a method for compressing the answer to one classical question through that keyhole.

Classical bits aren’t weaker in principle. A classical probabilistic computer is Turing-universal and can simulate any quantum computation, expensively, so the quantum claim concerns the length of the path, never reachability. The simplex and the complex projective space both have exponential dimension, so size alone does not distinguish them.

The classical model has no way to make paths cancel, and no compact way to express entanglement either. Writing down the local behavior of an entangled state costs an exponential classical description.

We know from simulability results that the features are needed together. Richard Jozsa and Noah Linden showed that computations staying close to separable are classically trackable. Daniel Gottesman proved with his stabilizer theorem that circuits built from the Clifford group, which generate enormous entanglement, are simulable in polynomial time.

And Leslie Valiant, Emanuel Knill, and Barbara Terhal with David DiVincenzo showed that noninteracting fermionic circuits, the matchgates, are simulable as well. Remove the entanglement, or the non-Clifford resources, or the interactions, and a classical computer can simulate the quantum one efficiently. Superposition, entanglement, and interference are each insufficient on their own. The advantage requires all of them together.

A qubit is a coordinate on a sphere on which amplitudes can cancel, shared across registers in a way that produces pure correlation, manipulated by local unitaries that no classical local map can emulate at polynomial cost.

And input, output, and control stay classical, always. A quantum computation is a map with classical ends and a quantum middle, which is why the complexity class BQP is defined by classical inputs and outputs in the first place.

The first quantum algorithms, 1985–1996

David Deutsch defined the model in 1985, in the Proceedings of the Royal Society A, and the first algorithms followed quickly.

Deutsch and Jozsa showed in 1992 how to decide whether a promised function is constant or balanced in one query, again in the Proceedings. Bernstein and Vazirani recovered a hidden linear functional on $$(\mathbb{Z}/2)^n$$ in 1993, again in one query, in work later published in the SIAM Journal on Computing. Simon found a hidden period in $$(\mathbb{Z}/2)^n$$ in 1994, in $$O(n)$$ queries against a classical $$2^{n/2}$$, in the same journal. Shor, the same year, found periods over the integers, with factoring as the celebrity corollary. And Grover searched an unstructured set of size $$N$$ in $$O(\sqrt{N})$$ steps in 1996.

To a mathematician, every exponential win on that list is a promise problem with hidden algebraic structure, whether a period, a character, or a subgroup. The one algorithm that attacks raw, structureless search is Grover’s, and its gain is quadratic, exactly matching the lower bound that Bennett, Bernstein, Brassard, and Vazirani proved one year later.

The founders located the boundary of the model within three years. People tried, but none of the first algorithms solves a combinatorial optimization problem, because their shared mechanism, sketched next, needs a structure that a random combinatorial instance does not have.

I sketch the mechanism in one paragraph and leave the derivations to the companion article. The circuit prepares a uniform superposition over a group and uses the phase-kickback move to evaluate a function into a phase. It then applies the Fourier transform of the group and measures. If the function hides a period or a subgroup, the spectrum concentrates on a structured set, and one sample contains global information, which Simon’s algorithm cleans up with linear algebra over $$\mathbb{F}_2$$ and Shor’s with continued fractions.

Nearly every exponential quantum speedup known to date descends from this template or from phase estimation, Alexei Kitaev’s generalization of it, and the few that don’t, a knot invariant and a quantum walk among them, still depend on the same interference. Deciding where quantum computers win then means classifying mathematical problems by their structure. Which mathematical problems have that kind of structure? I sort the answers onto three shelves.

The first shelf is quantum simulation

Quantum simulation is the problem the field was invented for, and the only one where the advantage requires no interference trick. If the object under study is a quantum system, the output of the computation is a quantum state, or a spectral quantity extracted from one. The classical computer’s handicap is then definitional, since it must carry an exponentially long vector through every step of the simulation while the quantum device is the vector.

Seth Lloyd made this constructive in his 1996 paper in Science. For a local Hamiltonian $$H = \sum_j H_j$$ with each $$H_j$$ acting on a constant number of qubits, the Lie-Trotter expansion $$e^{-iHt} \approx \big(\prod_j e^{-iH_j t/m}\big)^m$$ decomposes the evolution into polynomially many local unitaries with controlled error.

Simulation is more than one good application, because time evolution under a local Hamiltonian is BQP-complete. Given any quantum circuit, the Feynman-Kitaev clock construction produces a local Hamiltonian whose evolution performs that circuit, so every problem a quantum computer solves efficiently becomes, after recompilation, a simulation problem. In that sense simulation is the universal quantum computation, and everything else is a special case of it. The reference is Kitaev, Shen, and Vyalyi’s Classical and Quantum Computation.

The ground-state problem is the static version of simulation, and its complexity class is QMA, the quantum analog of NP. Kitaev proved that deciding whether the ground energy of a $$k$$-local Hamiltonian is below or above a promised gap is QMA-complete for $$k = 5$$. Julia Kempe and Oded Regev lowered the locality to $$k = 3$$. Together with Kitaev they then proved the case $$k = 2$$. The canonical map of the territory is Dorit Aharonov and Tomer Naveh’s survey.

Ground energies of local Hamiltonians are to QMA what satisfiability is to NP – the field’s Cook-Levin. Molecules are local Hamiltonians, so the theorem applies to real chemistry.

That is the mathematical content of the claim that quantum computers will transform chemistry. Computing electronic structure means solving the ground-state problem of a 2-body Hamiltonian. James Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik wrote down the explicit compilation from molecular integrals to quantum circuits, via the Jordan-Wigner transform and phase estimation, in Molecular Physics in 2011. Markus Reiher and colleagues then priced a concrete target, the FeMo cofactor of nitrogenase, in fault-tolerant resources, an estimate I walk through in the companion piece.

The sharpest result on this shelf, in my view, comes from Yi-Kai Liu, Matthias Christandl, and Frank Verstraete, who proved that the N-representability problem, deciding whether a given 2-electron density matrix can come from any N-electron wavefunction at all, is QMA-complete. Quantum chemists have been asking that question since the 1950s.

As everywhere else in this field, the simulated state itself is never read. The algorithm prepares an approximation of an eigenstate and evolves it under the molecular Hamiltonian. It then uses phase estimation to extract the corresponding energy one binary digit at a time. Each additional digit requires doubling the coherent evolution time. Shor’s algorithm uses the same procedure, with modular exponentiation in place of molecular time evolution as the unitary.

The bottleneck is the preparation step, getting a state with enough overlap on the true ground state. In complexity-theoretic terms, that is exactly the QMA-complete local Hamiltonian problem above. Sometimes a Hartree-Fock guess has decent overlap and the estimation converges. When it doesn’t, the advantage narrows, and careful authors say so.

The undecidability result from the opening is about a different regime, the thermodynamic limit rather than any finite computation. In that limit the spectral gap question encodes the halting problem. I won’t pretend it has engineering consequences. For mathematicians, the computational status of quantum many-body theory is an active branch of computability and complexity theory. It currently contains undecidable questions as well as problems complete for QMA and for BQP, all with physical names.

The completeness theorems are worst-case statements. Real molecules are rarely adversarial instances, and the classical heuristics, density functional theory, coupled cluster, tensor networks, handle a wide range of systems well. The exponential wall appears for strongly correlated electrons, and the defensible claim is narrower than the marketing: for the systems where classical heuristics fail, quantum simulation is the only approach with a complexity-theoretic reason to exist.

I priced that narrower claim, resource estimates and all, in Quantum Chemistry’s Honest Ledger, and I rank industries by which will see useful results first in the Quantum Utility Ladder. The claim is still enormous. It’s just not a date, and anyone who sells you a date is selling something else.

The second shelf is hidden algebraic structure

The problems on this shelf share the structure of the Simon template. A global invariant is encoded redundantly across all inputs, so a single Fourier sample contains information about it. The famous occupants are factoring and discrete logarithms, hidden subgroup problems over abelian groups, and I have written separately about what Shor’s algorithm does to cryptography and about what a cryptographically relevant quantum computer would require.

The cryptographer’s version of the story, derivations included, is the companion article. Regulators, meanwhile, have already set the deadlines defenders work to, whichever year the hardware arrives. The shelf’s most interesting objects have nothing to do with secrecy.

Start with number theory, and with Pell’s equation, $$x^2 – d,y^2 = 1$$, one of the oldest Diophantine problems. Its fundamental solution can be so large, doubly exponential in the number of digits of $$d$$, that merely writing it down takes exponential time. The compact form of the answer is the regulator of the real quadratic field $$\mathbb{Q}(\sqrt{d})$$, and Sean Hallgren showed in 2002 that the regulator hides a real-valued period, so that Fourier sampling over the reals rather than over a finite group recovers it. In the paper, published in the Journal of the ACM, he gives polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem.

Kirsten Eisenträger, Hallgren, Kitaev, and Fang Song then computed unit groups of number fields of arbitrary degree in quantum polynomial time, presented at STOC 2014, and Kiran Kedlaya gave a quantum polynomial-time algorithm for counting points on curves over finite fields.

No problem on this list, whether class groups, unit groups, or point counting on curves, is classically polynomial in full generality. The best classical methods take subexponential time or worse. All of them can be solved efficiently with the same phase-estimation machinery, and none has any cryptographic motivation. Number theory is full of hidden periods, so RSA is only one of many number-theoretic problems with a quantum speedup.

The result I show any pure mathematician who doubts that the field concerns them is about knots. The Jones polynomial is a knot invariant with values in Laurent polynomials, and evaluating it exactly is #P-hard, a result of Jaeger, Vertigan, and Welsh from 1990.

In 2005, Dorit Aharonov, Vaughan Jones, and Zeph Landau gave an explicit polynomial-time quantum algorithm that additively approximates the Jones polynomial of the plat closure of a braid at any primitive root of unity $$e^{2\pi i/k}$$. With it they made effective a connection that Michael Freedman, Alexei Kitaev, Michael Larsen, and Zhenghan Wang had established through topological quantum field theory, with the universality theorem in Freedman, Larsen, and Wang. This approximation problem is BQP-complete.

The connection starts with Edward Witten’s 1989 interpretation of the Jones polynomial through topological quantum field theory, part of the circle of ideas behind the 1990 Fields Medals of both Jones and Witten. Freedman was the first to take it seriously as a computer architecture.

Translated out of complexity jargon, every quantum computation can be recompiled into the evaluation of a knot invariant. Approximating the Jones polynomial is exactly as powerful as a quantum computer. Topologists arrived at that problem independently of computer science. If you work in low-dimensional topology, one of your invariants is a complete problem for quantum computation.

Andrew Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel Spielman came closest to an exponential speedup for something that looks combinatorial. They constructed a graph-traversal problem, walking through a pair of glued binary trees, that a quantum walk solves exponentially faster than any classical algorithm, and presented it at STOC 2003. The caveat is built into the construction, because the graph arrives as an oracle with a promise, and the exponential separation is proved only in that relativized world.

The phenomenon is therefore possible for graph problems. Nobody has transplanted the glued-trees speedup to Boolean satisfiability, where no comparable structure is known.

Nobody has made the template work, so far, on the non-abelian hidden subgroup problems, the symmetric-group case that would settle graph isomorphism and the dihedral case tied to lattice problems. I cover that frontier, which remains open and subexponential at best, in the companion article.

The third shelf is generic search, with a quadratic ceiling

Mathematicians outside cryptography most often ask me, “Fine, but is the advantage ultimately combinatorial?” No, and the reasons form a stack, from the empirical down to the proved.

The proved bottom of the stack is BBBV. Any quantum algorithm for unstructured search needs $$\Omega(\sqrt{N})$$ black-box queries, and Grover’s algorithm achieves exactly that. Quadratic is therefore the ceiling for unstructured search, for any quantum hardware, forever. Applied to Boolean satisfiability, Grover over $$2^n$$ assignments costs $$O(2^{n/2})$$, an improvement on naive brute force and still exponential.

The only way past the ceiling is structure in the problem that a black box cannot see, and here the mechanism from the earlier sections becomes the obstruction. Amplitudes reinforce only where a signal repeats coherently across the whole instance, and a hidden period or subgroup is exactly such a signal. A generic combinatorial instance has no known global redundancy of this kind. Its phases encode no coherent message, so the cancellation averages out to something indistinguishable from random guessing. The best an algorithm can then do is rotate amplitude at Grover’s rate. BBBV proved that nothing better exists.

The empirical middle of the stack is thirty years of trying. The best quantum algorithms known for combinatorial-looking problems are polynomial improvements, and they appear precisely where a shadow of algebraic structure remains. Andris Ambainis’s quantum walk solves element distinctness, finding two equal items among $$N$$, in $$O(N^{2/3})$$ queries, matching the lower bound proved by Scott Aaronson and Yaoyun Shi, and the gain comes from the Johnson-graph structure of the collision problem, a polynomial factor.

Ashley Montanaro’s quantum backtracking gives a quadratic speedup for the depth-first search trees under exact exponential algorithms for constraint problems, with a similar quadratic result for branch-and-bound. His Monte Carlo speedup, quadratic and provably the right order, applies to estimation problems, and his 2016 survey is the balanced account of the whole field.

Every one of these gains is real, useful, and polynomial.

Researchers keep finding polynomial wins where structure exists. François Le Gall’s triangle finding, $$O(n^{5/4})$$ queries against the classical $$n^2$$, is again a quantum walk on structured subsets.

The conclusion would change only if someone found exploitable global structure, a periodicity, a hidden subspace, an algebraic spectral signal, inside an NP-complete problem. Then NP would fall into BQP and I would have to rewrite this section. The working assumption of the field is that no such structure exists, an assumption with the same standing as P $$\neq$$ NP: unproven, relied on everywhere, and so far confirmed by every failed attempt to disprove it.

The top of the stack is the heuristic layer, the quantum approximate optimization algorithm and its cousins, where I apply my claim-evidence test in full. After more than a decade there’s no proven advantage for QAOA on NP-hard optimization, and the experimental record consists of small instances against classical baselines that keep improving. With a quadratic speedup, $$2^n$$ steps become $$2^{n/2}$$, which is still exponential, a fact that has never once appeared in a press release.

Quantum vendors overpromise most on combinatorial optimization, precisely because that is where the provable structure is thinnest. I track the gap between claim and evidence under the heading Q-FUD and map where quantum value appears first in the Quantum Utility Map, with a separate accounting for the finance version of the overpromise.

How much of this is proved

The results form a ladder from proved to believed. Most people do not realize how strong the top rung is, and the reason is a 2018 result that I think everyone who knows Shor’s algorithm should also know.

The unconditional theorems are on the top rung. Sergey Bravyi, David Gosset, and Robert König proved that constant-depth quantum circuits are strictly more powerful than constant-depth classical ones, in Science in 2018. Their problem, the 2D Hidden Linear Function, is a non-oracular relative of Bernstein-Vazirani. An instance is a quadratic form on $$\mathbb{Z}_2^n$$, and the task is to recover a linear function describing its restriction to a hidden subset. A constant-depth quantum circuit of local gates on a 2D grid solves it exactly, while any classical probabilistic circuit of bounded fan-in needs depth growing logarithmically in $$n$$. The proof uses no oracle and no unproven conjecture.

The Bravyi-Gosset-König result was the first fully unconditional quantum-classical separation, and it is still the cleanest. For the standard polynomial-time classes, no unconditional separation has been proved. Bravyi, Gosset, König, and Marco Tomamichel later extended the separation to noisy shallow circuits, and François Le Gall proved an average-case version. By 2026 researchers had added an unconditional sampling separation for shallow circuits.

The caveat is scope, shallow circuits on a relation problem rather than polynomial-time machines on a decision problem. As a proof that the three geometries of the first section differ in power, though, it is exact.

The oracle separations are one rung down. Simon’s problem gives an exponential oracle separation between BQP and BPP, and the glued-trees construction does the same for a graph problem. Ran Raz and Avishay Tal gave an oracle relative to which BQP is not contained in the entire polynomial hierarchy, in ECCC TR18-107, presented at STOC 2019 and published in the Journal of the ACM in 2022.

Oracle results can be misleading. The classical literature is full of relativized results that do not hold in the unrelativized world. Still, in every one of these proofs, the source of the power is Fourier structure and the ability to correlate globally what a classical machine can only correlate locally.

The third rung is sampling with counting-complexity backing. In the boson sampling model of Scott Aaronson and Alex Arkhipov, the output distribution encodes permanents of random matrices, and Michael Bremner, Richard Jozsa, and Dan Shepherd showed that exact classical simulation of commuting quantum circuits would collapse the polynomial hierarchy to its third level.

The quantum supremacy experiments are based on these results. Approximate classical simulation of those experiments is ruled out only modulo plausible but unproven conjectures. I cover the experiment-versus-simulation saga in the companion article. The hardness behind those experiments is the right kind, #P-hardness, and that part is proved.

The completeness theorems from the shelves above make up the last rung. Simulating local Hamiltonian dynamics and approximating the Jones polynomial are both BQP-complete. Estimating ground energies is QMA-complete. A classical algorithm for any of these would make BQP equal BPP, against all the evidence on the rungs above. With completeness, “we believe” becomes “everything we know is consistent only if.”

Nobody has proved BPP $$\neq$$ BQP. Anyone who proves it will also have proved P $$\neq$$ PSPACE, so no proof is coming soon. The theory of quantum advantage is coherent, mutually reinforcing, and unproven at its foundation. As elsewhere in complexity theory, the foundation is one unresolved conjecture, BPP $$\neq$$ BQP, and above it is a large body of mutually consistent results that nobody has managed to contradict in four decades of trying.

Open problems for mathematicians

The open problems on the shelves above are mathematics problems with a new examiner.

The quantum PCP conjecture, whether ground energies can be verified to constant-factor precision, is, in my view, the field’s biggest open question. The guest column by Aharonov, Itai Arad, and Thomas Vidick is where to start. Graph isomorphism and certain lattice problems both reduce to non-abelian hidden subgroup problems. The second shelf’s algorithms for class and unit groups have barely been optimized.

Urmila Mahadev opened a verification theory that didn’t exist a decade ago with her protocol for classically verifying quantum computation. The dequantization boundary, where researchers match claimed quantum speedups with quantum-inspired classical algorithms, is an open research program of its own. I cover the machinery in the companion article.

I close the companion piece with a reading path into the field. Here I add only the two references best matched to this article’s audience: Aharonov and Naveh’s Quantum NP survey for the completeness theory, and Montanaro’s overview for the algorithm zoo with honest speedup labels. The invitation from the first article is still open, because the unsolved problems here are stated in your notation.

The cryptographer’s view and the mathematician’s view

I make one argument across the two articles, seen through two lenses. Through the cryptographer’s lens it is a threat, hidden periods breaking public-key cryptography.

Through the pure mathematician’s lens it is a classification. Quantum advantage is concentrated where problems are quantum-shaped, in the spectra of local Hamiltonians, the hidden periodicities of number theory, and the knot invariants of topology. It is almost absent from combinatorics, where the provable gain on generic search is quadratic, a ceiling that is exact in the black-box model.

Qubits have a geometry that classical bits lack. On a problem with no structure, the gain from that geometry is at most quadratic, and no hardware team can engineer its way past a theorem.