A superconducting quantum computer, a dark cylindrical cryostat hanging inside a lit glass cube, in a dark hall in Ehningen, Germany
Unit 15 · Advanced + Quantum Information · 70 min

Quantum Algorithms

Deutsch, Grover, the quantum Fourier transform, and how Shor's algorithm factors a number
Image: IBM Research, Wikimedia Commons, CC BY 2.0

A quantum computer does not try every answer at once; it arranges the amplitudes of all answers so that the wrong ones cancel. This unit shows three ways of doing that: the Deutsch-Jozsa algorithm, which decides a property of a function with one evaluation, Grover's search, which finds one item among N in about the square root of N steps, and Shor's algorithm, which factors a number by finding a period with the quantum Fourier transform. The number 15 is factored by hand, the cost of breaking a 2,048-bit RSA key is compared with published estimates, and the unit ends with what has actually been factored and why the records are small.

Preview: the beginning of the unit

Unit 13 built the parts, qubits and gates, and Unit 14 used them to move and protect information. This unit asks what a circuit of gates can compute faster than any classical machine, and the answer is more surprising than the popular version. A quantum computer does not try every answer at once; it arranges the amplitudes of all possible answers so that the wrong ones cancel and the right one remains. Three algorithms show three ways of doing this: the Deutsch-Jozsa algorithm, which answers a question about a function with a single evaluation, Grover’s search, which finds one item among \(N\) in about \(\sqrt N\) steps, and Shor’s algorithm, which factors a number by finding a period with the quantum Fourier transform. The last is the reason governments and banks are replacing their encryption, and the unit ends with what has actually been factored and why the numbers are still small.

1 Computational paths and interference

A register of \(n\) qubits has \(2^n\) basis states, and Unit 13 labelled them by the \(n\)-bit strings, \(\ket{000}\), \(\ket{001}\), and so on. This unit also reads these strings as the integers \(0\) to \(2^n - 1\) written in binary, so that \(\ket{5}\) means \(\ket{101}\). The most important single state of this unit is the uniform superposition of all of them. One Hadamard gate turns \(\ket{0}\) into \((\ket{0} + \ket{1})/\sqrt2\), and a Hadamard gate on every qubit of \(\ket{0\ldots0}\) turns each factor into that sum, so that multiplying out the product gives every \(n\)-bit string once, each with the amplitude \((1/\sqrt2)^n\): \begin{equation} \mathrm{H}^{\otimes n}\ket{0\ldots0} = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n - 1}\ket{x} . \label{eq:uniform} \end{equation} Twenty qubits and twenty gates produce a state with a little over a million terms.

Now let \(f\) be any function that takes an \(n\)-bit string to a bit, computed by some classical circuit. Unit 13 explained that every classical computation can be made reversible, and the standard reversible form of \(f\) is the unitary operation \begin{equation} U_f\,\ket{x}\ket{y} = \ket{x}\ket{y \oplus f(x)} , \label{eq:oracle} \end{equation} which leaves the input register alone and adds \(f(x)\) to a one-qubit target register, where \(\oplus\) is addition modulo 2, so that \(0 \oplus 1 = 1\) and \(1 \oplus 1 = 0\). Applying \(U_f\) to the uniform superposition with the target in \(\ket{0}\) gives, because \(U_f\) is linear, \begin{equation} U_f\left(\frac{1}{\sqrt{2^n}}\sum_x \ket{x}\ket{0}\right) = \frac{1}{\sqrt{2^n}}\sum_x \ket{x}\ket{f(x)} . \label{eq:parallel} \end{equation} The state on the right contains the value of \(f\) at every one of the \(2^n\) inputs, computed with a single use of the circuit for \(f\). This is the fact behind the phrase “a quantum computer tries all answers at once”, and it is true as far as it goes. The problem is the next step. A measurement of both registers, by the Born rule of Unit 9, returns one basis state \(\ket{x}\ket{f(x)}\), with \(x\) chosen at random, and the rest of the superposition is gone. The experimenter has learned \(f\) at one random point, which a classical computer does by evaluating \(f\) once. Nothing has been gained.

What a quantum algorithm adds is interference. The amplitudes in Equation \eqref{eq:parallel} are complex numbers with phases, and later gates can add amplitudes that belong to different computational paths, as the two paths through a double slit add in Unit 3 and the two phasors add in Unit 1. An algorithm is a choice of gates for which the paths leading to wrong answers cancel and the paths leading to the right answer add up, so that the final measurement returns the right answer with high probability. The three algorithms of this unit are three different ways of arranging the cancellation, and in each the function \(f\) is used not to read its values but to write a pattern of signs onto the amplitudes.

Algorithms of this kind are compared by counting queries, the number of times the circuit for \(f\) is used. In this count \(f\) is treated as a sealed box that answers one question at a time and whose inner working is of no interest; such a box is called an oracle. Counting queries sets aside the cost of the other gates and of building \(U_f\), which is fair because quantum and classical algorithms must evaluate \(f\) in the same way; Section 5 returns to full gate counts where they matter.

The full unit is part of the program

Want to see a complete unit first? Unit 3, Matter Waves and the Double Slit, is free to read.