Quantum algorithms: what each one does and how it works

The most important quantum algorithms in plain language: Deutsch–Jozsa, Bernstein–Vazirani, Grover, the quantum Fourier transform, phase estimation, Shor, VQE and QAOA.

What is a quantum algorithm?

A quantum algorithm is a sequence of gates acting on qubits. Its power does not come from “trying every answer at once”; a measurement returns only one result. The real trick is interference: the algorithm arranges the amplitudes so that wrong answers cancel and the right one is reinforced.

That is why not every problem gets a quantum speed-up. Known speed-ups appear when the problem has structure that interference can capture: a period, a hidden pattern, the value of a phase.

Oracle algorithms: Deutsch–Jozsa and Bernstein–Vazirani

In these first algorithms the function is a black box (an oracle) and the goal is to query it as few times as possible. Deutsch–Jozsa decides with certainty, in a single query, whether a function is constant or balanced. Bernstein–Vazirani reads a bit string hidden inside a function in a single query.

Both rely on phase kickback: when the helper qubit is prepared in the right state, the oracle writes its result as a phase onto the inputs, and the final H gates turn this phase pattern into a readable result.

Search: Grover’s algorithm

Grover’s algorithm finds the marked answer among N options in about √N steps; classically you need N/2 tries on average. In each round the oracle flips the phase of the answer and the diffusion step amplifies it. Because the speed-up is quadratic, its effect on breaking ciphers is limited: keys such as AES-256 remain secure.

Periods and phases: QFT, phase estimation and Shor

The quantum Fourier transform (QFT) turns a periodic pattern of amplitudes into peaks that reveal the period. Phase estimation uses the inverse QFT to read, as a binary number, the phase a gate adds to one of its eigenstates.

Shor’s algorithm turns factoring a large number into finding the period of modular exponentiation and finds that period with phase estimation. This is the source of the exponential speed-up that threatens RSA; it is estimated to need an error-corrected computer with millions of physical qubits.

For today’s devices: VQE and QAOA

Long circuits do not work on today’s noisy (NISQ) devices, so hybrid methods combine short, tunable circuits with a classical optimisation loop. VQE searches for the lowest energy of a molecule, QAOA for good solutions to combinatorial optimisation problems. Neither has a proven advantage over classical methods yet; both are active research areas.

Try it yourself

Quantum Store’s intermediate course lets you run and modify Deutsch–Jozsa, Bernstein–Vazirani, Grover, quantum Fourier transform and phase estimation circuits in the browser with no installation (the lessons are currently in Turkish). To run them locally with Qiskit, see the first-algorithms and Shor packages.

Frequently asked questions

What are the best-known quantum algorithms?

Grover for search, Shor for factoring, the quantum Fourier transform and phase estimation as their building blocks, and VQE and QAOA for today’s devices.

Do quantum algorithms speed up every problem?

No. A speed-up only appears for problems with structure that interference can capture. For most ordinary tasks classical computers remain faster and cheaper.

What do I need to know to learn quantum algorithms?

The concepts of qubits, superposition, measurement, entanglement and interference are a sufficient start, along with some Python to run circuits with Qiskit.

Concepts in this guide

Deutsch–Jozsa algorithm · The Deutsch–Jozsa algorithm is one of the first quantum algorithms: it decides with certainty, in a single query, whether a function is constant or balanced.
Bernstein–Vazirani algorithm · The Bernstein–Vazirani algorithm finds the hidden bit string s inside a function f(x) = s·x in a single query, instead of the n queries needed classically.
Grover’s algorithm · Grover’s algorithm finds a marked item among N unsorted items in about √N steps, a quadratic speed-up over classical search.
Quantum Fourier transform (QFT) · The quantum Fourier transform (QFT) computes the discrete Fourier transform of the amplitudes with H and controlled-phase gates; it underlies period finding and phase estimation.
Quantum phase estimation (QPE) · Quantum phase estimation (QPE) reads the phase a gate adds to one of its eigenstates as a binary number in counting qubits, using phase kickback and the inverse Fourier transform.
Shor’s algorithm · Shor’s algorithm factors large numbers exponentially faster than known classical methods, which is why it threatens RSA encryption.
VQE (variational quantum eigensolver) · VQE is a hybrid quantum algorithm that approximates the ground-state energy of a molecule by tuning a parameterised quantum circuit in a classical optimisation loop.
QAOA (quantum approximate optimisation algorithm) · QAOA combines parameterised quantum circuits with classical optimisation to search for approximate solutions to combinatorial optimisation problems such as MaxCut.

Full quantum computing glossary →