What Is a Quantum Algorithm?

A quantum algorithm is a step-by-step procedure, written as a quantum circuit, that runs on quantum hardware and uses superposition, entanglement and interference to solve a specific problem faster than the best known classical method. The catch is in the word "specific": the list of problems with a proven quantum speedup is short.

This article explains what makes an algorithm quantum, walks through the ones that matter, and is direct about what quantum algorithms do not do. It is one of the most overstated areas in quantum coverage, so precision helps.

What makes an algorithm quantum

A quantum algorithm is a circuit: a sequence of gates applied to qubits, followed by measurement. Because the result is probabilistic, the circuit is run many times. Real programs are hybrid, with a classical computer preparing the circuit, reading the results and often deciding what to run next. The quantum part is a subroutine, not the whole program. What makes it worth using is interference, arranged so that wrong answers cancel.

The algorithms that matter

• Shor's algorithm (1994). Factors large integers in polynomial time, while the best known classical method, the general number field sieve, is sub-exponential. That gap is why quantum computing is taken seriously as a future threat to RSA encryption, which relies on factoring being hard.
• Grover's algorithm (1996). Finds a marked item in an unsorted list of N entries in about the square root of N steps instead of about N. That is a quadratic speedup, and it is provably the best possible for unstructured search. It is meaningful but far more modest than Shor's, and it does not break most encryption. Doubling a symmetric key's length is enough to offset it.
• Quantum simulation. Richard Feynman proposed the idea in 1981, and Seth Lloyd showed in 1996 that a quantum computer can efficiently simulate the dynamics of quantum systems. It lets you model how molecules and materials behave at the quantum level, which classical computers scale badly at.
• Variational algorithms. Methods such as VQE and QAOA pair a small quantum circuit with a classical optimizer and are designed for today's noisy hardware. They are promising heuristics, but they do not come with a proven speedup.

What quantum algorithms do not do

There is no known general-purpose quantum algorithm that speeds up arbitrary computation. The problems with real speedups are specific and mathematically identified, and they do not generalize to "computing gets faster now". Even a genuine speedup can be smaller than it looks. Researchers have argued that once you count the large overhead of error correction, a quadratic speedup such as Grover's only pays off for very large problems on early fault-tolerant machines.

Why the list is so short

Designing the interference pattern for a specific problem is hard, and only a few problems have the right structure. Some claimed speedups also disappear under scrutiny. In 2018 Ewin Tang found a classical algorithm that matched a celebrated quantum recommendation-system algorithm up to a polynomial factor, removing its claimed exponential advantage. That episode is a useful reminder that a quantum speedup is a claim to check against the best classical method, not a headline to accept.

A great deal of current research is about finding new problems where a genuine quantum advantage exists. That is an open, active area, not a solved one. If you want to see the practical side, what quantum computers are used for covers where these algorithms stand outside the lab.