10.4 Oracles and query complexity

The computational power of quantum interference was discovered by counting how many times certain Boolean functions have to be evaluated in order to find the answer to a given problem. Imagine a “black box” (also called an oracle) that computes some fixed Boolean function, but whose inner workings are unknown to us, and a scenario in which one wants to learn about a given property of the Boolean function but has to “pay” (in energy, or in money!) for each use (often referred to as a query) of the box. In such a setting, the objective is to minimise number of queries to the oracle while finding out as much information as possible about the function computed by the oracle. For this purpose, we ignore everything that happens inside the black box: the Boolean function evaluation counts as just one computational step.

10.4.1 Deutsch’s algorithm

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

Suppose you can prepare the input, you can read the output, you cannot see the phase shifter, but you are promised that the phase shifter is set to either \varphi=0 or \varphi=\pi. Can you tell which value \varphi has been set to?

Of course you can!

One way of doing it is to set your input to |0\rangle and check the output: for \varphi=0 the output is always |0\rangle, and for \varphi=\pi it is always |1\rangle. A single run of the interference experiment is sufficient to determine the difference. The 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.

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 \begin{matrix}0\\1\end{matrix} \begin{matrix}0\\1\end{matrix}
balanced \begin{matrix}0\\1\end{matrix} \begin{matrix}1\\0\end{matrix}

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.

(Deutsch’s).

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{f}{\longmapsto} (-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle \\&\quad\equiv |0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle \\&\overset{H}{\longmapsto} |f(0)\oplus f(1)\rangle. \end{aligned}

This evolution can be represented 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.129

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, followed by a function evaluation, followed by another Hadamard (or Fourier) transform.130 As we shall see in a moment, in some cases (such as in Grover’s search algorithm) this sequence is repeated several times. Let me now take you through the three early quantum algorithms, each one offering a higher-order speed-up when compared to their classical analogues than the last.

  1. The original Deutsch algorithm provides the correct answer with probability 50%. Here we have presented a modified/improved version.↩︎

  2. The Hadamard transform is a special case of the Fourier transform over the group \mathbb{Z}_2^n.↩︎