10.4 Deutsch’s algorithm

We start, once more, with the simplest quantum interference circuit

but let’s turn this into a black-box scenario, often known as the binary observable measurement problem:202

  • we are allowed to prepare the input in any state that we like;
  • we are allowed to read the output;
  • but all we know about the value of \varphi is that it is either 0 or \pi, and we are not allowed to “look inside” the phase gate to see which value it is!

With these rules, can we figure out which value \varphi has been set to?

Of course we can — we’re quantum information scientists!

One way of doing it is to prepare the input in the state |0\rangle and check the output: if \varphi=0 then the output is always |0\rangle, and if \varphi=\pi then it is always |1\rangle. In other words, a single run of the interference experiment is sufficient to determine the difference.

The very first quantum algorithm, proposed by David Deutsch in 1985, is very much related to this effect, but where the phase setting is determined by the Boolean function evaluation via the phase kick-back.

(Global properties of a one-bit function).

We are presented with an oracle that computes some unknown function f\colon\{0,1\}\to\{0,1\}. Note that there are only four possibilities for what f can be: it could be one of two constant functions (i.e. those where f(0)=f(1)), or one of two balanced functions (i.e. those where f(0)\neq f(1)).

f(0) f(1)
constant 0 0
constant 1 1
balanced 0 1
balanced 1 0

Our task is to determine, using the fewest queries possible, whether the function computed by the oracle is constant or balanced.

Note that we are not asked for the particular values f(0) and f(1), but only whether the two values are the same or different. Classical intuition tells us that we have to evaluate both f(0) and f(1) and compare them, which involves evaluating f twice. But, in the quantum setting, we can solve this problem with a single function evaluation, using the following circuit.203

(Deutsch’s algorithm).

First register: 1 qubit. Second register: 1 qubit.

During the function evaluation, the second register “kicks back” the phase factor (-1)^{f(x)} in front of |x\rangle, but the state of the second register remains unchanged; the first register is modified as follows: \begin{aligned} |0\rangle &\overset{H}{\longmapsto} |0\rangle+|1\rangle \\&\overset{U_f}{\longmapsto} (-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle \\&\quad= |0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle \\&\overset{H}{\longmapsto} |f(0)\oplus f(1)\rangle. \end{aligned}

The evolution of the first qubit is thus identical to that described by the circuit diagram

where the relative phase is \varphi = (-1)^{f(0)\oplus f(1)}. The first qubit ends in state |0\rangle if the function f is constant, and in state |1\rangle if the function is balanced, and the standard measurement distinguishes these two cases with certainty.204

But really this is just the binary observable measurement problem in disguise! Indeed, the fact that quantum Boolean function evaluation of a function f is given by |x\rangle|y\rangle \longmapsto |x\rangle|y\oplus f(x)\rangle means that the unitary U_f has eigenvalues \pm1 because it satisfies U_f^2=\mathbf{1}, since two consecutive evaluations gives \begin{aligned} |x\rangle|y\rangle \longmapsto& |x\rangle|y\oplus f(x)\rangle \\\longmapsto& |x\rangle|y\oplus f(x)\oplus f(x)\rangle \\=& |x\rangle|y\rangle. \end{aligned} So the fact that 1=e^{0} and -1=e^{i\pi} means that U_f acts as a phase gate with phase either 0 or \pi. We will come back to this link between Deutsch’s algorithm and binary observable measurement in Section 10.8.

Deutsch’s result laid the foundation for the new field of quantum computation, and was followed by several other quantum algorithms for various problems. They all seem to rest on the same generic sequence:

  • a Hadamard transform;
  • function evaluation;
  • another Hadamard (or Fourier) transform.205

As we shall see in a moment, in some cases (such as in Grover’s search algorithm) this sequence is repeated several times.

Let us now follow a tour through the three early quantum algorithms, where each one offers a higher-order speed-up when compared to their classical analogues than the last: firstly linear, then quadratic, and finally exponential. After this, we will look at generalising binary observable measurement, the corresponding algorithm analogous to Deutsch’s, and how this leads us to arguably the most famous quantum algorithm: Shor’s algorithm for prime factorisation.

  1. You might recognise this as Exercise 2.14.8, and we will return to this problem again in Section 10.8.↩︎

  2. The original version of Deutsch’s algorithm provides the correct answer with probability 50%. Here we present a modified/improved version. The more general problem, which deals with unknown functions f\colon\{0,1\}^n\to\{0,1\} for n\geqslant 1, is known as the Deutsch–Jozsa problem.↩︎

  3. This is also implemented in the Quantum Flytrap Virtual Lab.↩︎

  4. As explained in Section 10.9, the Hadamard transform is a special case of the Fourier transform over the group \mathbb{Z}_2^n.↩︎