Where quantum speedups actually come from
A quantum algorithm is not a classical algorithm run on faster hardware. It is a sequence of operations designed so that the amplitudes of wrong answers interfere destructively and cancel, leaving the right answer with a high probability of being measured. Every genuine speedup in this field traces back to finding a structure in the problem that interference can exploit. Where no such structure exists, quantum computers give you nothing.
The algorithms that matter, and what they actually do
- Shor's algorithm — factors large integers in polynomial time, which breaks RSA and elliptic-curve cryptography. The speedup is exponential, and it is the single result that made governments start funding this field. It needs a large, error-corrected machine that does not yet exist.
- Grover's algorithm — searches an unstructured list of N items in roughly √N steps instead of N. Note what that means: it is a quadratic speedup, not an exponential one. Doubling your security key size defeats it. Grover is important, but it is not the apocalypse.
- Quantum phase estimation — the workhorse underneath Shor and underneath most chemistry simulation. It extracts the eigenvalue of an operator, which in chemistry means a molecule's energy.
- VQE and QAOA — variational algorithms that split the work between a small quantum circuit and a classical optimiser. They are designed to run on today's noisy machines. Whether they beat good classical methods on real problems is genuinely unsettled, and claims in both directions should be read carefully.
- HHL — solves linear systems exponentially faster, with a long list of caveats about how the data goes in and what comes out that often erase the advantage in practice.
- Quantum walks and amplitude amplification — the general machinery that Grover is a special case of, and the basis of several newer algorithms.
The question to ask of any claimed speedup
Three things decide whether a quantum algorithm is useful: how the classical data gets loaded into the machine, how many logical qubits and gates the algorithm needs, and what the best classical algorithm can already do. Many published quantum speedups quietly assume free data loading, or are compared against a weak classical baseline. Several famous "exponential speedups" have been dequantised — a classical algorithm was found that matched them. That is not a scandal; it is the field working properly.
Reading these articles
Start with Grover and Shor to get the two shapes of speedup in your head, then phase estimation, then the variational algorithms. Resource estimates — how many qubits, for how long — are where theory meets hardware reality, and they are usually the most informative number in any paper.
