Quantum Algorithms
Quantum Computing Fundamentals · Frontiers track
7 min read
In this module
Why Algorithms Matter
Qubits and gates are necessary, but they're not enough. A quantum computer without good algorithms is a classical CPU without software — raw capability with nowhere to point it. The real breakthroughs in quantum computing have always been algorithmic: spotting problems where quantum interference can be harnessed to outpace anything classical.
This lesson runs through the three most important quantum algorithms and the messy idea of quantum advantage.
Deutsch-Jozsa: The First Quantum Speedup
The Deutsch-Jozsa algorithm (1992) was the first to prove a quantum computer could solve a specific problem exponentially faster than any deterministic classical one. The problem itself is artificial, almost a toy, but the techniques it introduced underpin every quantum algorithm that came after.
Here's the setup. You're handed a function f that takes an N-bit input and spits back either 0 or 1. You're also promised that f is either constant (same output for every input) or balanced (outputs 0 for exactly half the inputs and 1 for the other half). Your job: figure out which.
Classically, in the worst case, you might need to check 2^(N-1) + 1 inputs to be sure. Deutsch-Jozsa cracks it with a single query to f, no matter how big N gets.
The algorithm works by:
- Preparing N qubits in the |0⟩ state
- Applying Hadamard gates to create a superposition of all inputs
- Applying the function f in a reversible way (as a quantum oracle)
- Applying Hadamard gates again
- Measuring - if the result is all zeros, f is constant; otherwise f is balanced
The trick at the heart of it is quantum parallelism combined with interference. The function gets evaluated on every input simultaneously (via superposition), and the Hadamard transform turns global information about f into a pattern that a single measurement can read off.
Shor's Algorithm: Breaking Encryption
Shor's algorithm (1994) is probably the most famous quantum algorithm, and there's a reason: it factors large integers in polynomial time. That puts a hand directly around the throat of RSA encryption, one of the load-bearing pillars of internet security.
Why Factoring Matters
RSA encryption multiplies two large primes (say, 300 digits each) to produce a public key. Anyone can encrypt with that public key, but decryption requires knowing the two prime factors. Classical computers can't factor a 600-digit number in any time you'd be willing to wait. The best classical algorithms are sub-exponential, but still wholly impractical at those sizes.
How Shor's Algorithm Works
Shor's algorithm reduces factoring to the problem of finding the period of a function, then uses a quantum technique called the Quantum Fourier Transform (QFT) to find that period efficiently.
The high-level steps:
- Choose a random number a less than N (the number to factor)
- Use a quantum computer to find the period r of the function f(x) = a^x mod N
- Use the period r to compute the factors of N using classical arithmetic (via the GCD)
Step 2 is the quantum bit. Classically, finding the period of a modular exponentiation costs you exponential time. The QFT polishes it off in polynomial.
The Quantum Fourier Transform (QFT) is the quantum analogue of the classical discrete Fourier transform. It converts amplitude information from the "time domain" to the "frequency domain," revealing periodicities hidden in the quantum state. The QFT on n qubits uses only O(n²) quantum gates, compared to the O(n·2ⁿ) operations needed by the classical FFT on the equivalent 2ⁿ data points (where N=2ⁿ is the vector size). This exponential speedup is the engine that powers Shor's algorithm.
Practical Implications
A quantum computer with around 4,000 error-corrected logical qubits could factor a 2048-bit RSA key. Today's machines have far fewer qubits and far higher error rates, but the direction of travel has been enough to spark a worldwide rush to develop post-quantum cryptography (the subject of the next lesson).
Grover's Algorithm: Searching Faster
Grover's algorithm (1996) buys you a quadratic speedup on unstructured search. Hand a classical computer a database of N items with no particular ordering and it needs O(N) queries to find what you're after. Grover's algorithm finds it in O(√N).
The Algorithm
- Start with N qubits in the |0⟩ state
- Apply Hadamard gates to create equal superposition of all N states
- Repeat approximately √N times: a. Apply the oracle - a function that flips the sign of the amplitude of the target state b. Apply the diffusion operator - reflects all amplitudes about their mean
- Measure the qubits
Each pass of steps 3a and 3b nudges the target's amplitude up and the non-targets' amplitudes down. After roughly √N iterations, the target state hogs most of the probability mass and is overwhelmingly likely to be the thing you measure.
Amplitude Amplification
The technique at the heart of Grover's algorithm has a name: amplitude amplification. The oracle marks the target by flipping its phase, dragging its amplitude negative. The diffusion operator then "reflects" all amplitudes about their average. Since the target amplitude sits below the average (negative), the reflection lifts it above. The non-target amplitudes, which sit above (positive), get pushed down by the same reflection.
It's a kind of see-saw: each iteration lifts the target amplitude and lowers the rest. The process is also periodic, which is the trap — run too many iterations and the target amplitude starts dropping again. Sweet spot is roughly (π/4)√N iterations.
Practical Speedup
A quadratic speedup looks tame next to Shor's exponential one, until you notice how absurdly broad the class of problems it covers actually is. Anything that can be framed as "find the input that satisfies some condition" is potentially Grover-shaped:
- Database search
- Constraint satisfaction problems
- Cryptographic key search (effectively halving the key length)
- Optimisation problems (finding the minimum of a function)
Quantum Advantage and Quantum Supremacy
Quantum advantage (sometimes called quantum supremacy) is the moment where a quantum computer outpaces every classical machine on a given problem. In 2019, Google claimed it for their 53-qubit Sycamore processor, polishing off a specific sampling task in 200 seconds that they reckoned would take a classical supercomputer 10,000 years.
The claim didn't go unchallenged. IBM hit back with clever classical techniques that they argued could grind through the same problem in days rather than millennia. The squabble drives home a subtle point: quantum advantage is always measured against the best known classical algorithm, and those keep getting better.
Genuine practical quantum advantage — solving a real-world problem faster than anything classical can manage — hasn't landed yet. The tasks where quantum supremacy has been claimed are deliberately built to be hard classically and easy quantumly, with no direct application beyond the demo itself.
Quantum computers will not replace classical computers. They offer speedups for specific problem classes: factoring, simulation of quantum systems, certain optimisation problems, and unstructured search. For most everyday computing tasks, classical computers will remain faster, cheaper, and more practical. The goal is not to replace classical computing but to complement it for problems that are intractable classically.
Other Notable Quantum Algorithms
Beyond the "big three," a handful of other quantum algorithms deserve a name-check:
- Variational Quantum Eigensolver (VQE) — a hybrid quantum-classical algorithm for finding the ground state energy of molecules. One of the better candidates for near-term practical use.
- Quantum Approximate Optimisation Algorithm (QAOA) — chips at combinatorial optimisation problems using a similar hybrid trick.
- Quantum simulation — simulating quantum systems (molecules, materials) on quantum hardware is the most likely place where useful quantum advantage shows up first, on the simple grounds that quantum systems are themselves the most natural thing for a quantum computer to simulate.
- HHL algorithm — solves systems of linear equations exponentially faster than classical methods, though it comes wrapped in serious caveats about loading data in and pulling answers back out.
The next lesson digs into what quantum computing means for security and cryptography. The implications run deep.