## 11.4 Oracles, and our first quantum algorithm

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” (sometimes also called an **oracle**) that computes some fixed Boolean function, but whose inner workings are unknown to us.
Then imagine that we are in a scenario where we want to learn about some given property of the Boolean function, but we have to “pay” (in energy, time, money, or anything!) 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 that it computes.
For this purpose, we ignore everything that happens inside the black box: in our rules of the game, the Boolean function evaluation counts as just *one* computational step.

### 11.4.1 Deutsch’s algorithm

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

but let’s turn this into a black-box scenario, as described above:

- 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 either0 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

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

One way of doing it is to prepare the input in the state *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.

We are presented with an oracle that computes some unknown function **constant** functions (i.e. those where **balanced** functions (i.e. those where

constant | ||

constant | ||

balanced | ||

balanced |

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 *only whether the two values are the same or different*.
Classical intuition tells us that we have to evaluate both *twice*.
But, in the quantum setting, we can solve this problem with a *single* function evaluation, using the following circuit.^{172}

(Deutsch’s).

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

During the function evaluation, the second register “kicks back” the phase factor

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

where the relative phase is ^{173}

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.
^{174}

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.

The original Deutsch 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\} forn\geqslant 1 , is known as the Deutsch–Jozsa problem.↩︎This is also implemented in the Quantum Flytrap Virtual Lab.↩︎

As explained in Section 11.2, the Hadamard transform is a special case of the Fourier transform over the group

\mathbb{Z}_2^n .↩︎