# Chapter 10 Quantum algorithms

About quantum interference in disguise:

Hadamard, function evaluation, Hadamard. Also about the early quantum algorithms and how they deal with querying oracles, searching for a needle in a haystack, and estimating periodicity of certain functions.

Classical computers essentially evaluate functions: given

## 10.1 Quantum Boolean function evaluation

*In quantum computation, all elementary operations are reversible* (unitary), so we compute Boolean functions in a reversible fashion as

The corresponding circuit diagram (for

Here we use two registers: the first one (counting from the top to the bottom of the circuit diagram) stores the arguments

Quantum Boolean function evaluation is a special case of the generalised ^{116}

### 10.1.1 Example

Consider the Boolean function

## 10.2 Hadamard and quantum Fourier transforms

**!!!TODO!!!**

## 10.3 More phase kick-back

What makes the quantum evaluation of Boolean functions really interesting is its action on a superposition of different inputs *all* *single* run (note that we have dropped the normalisation factor).
It is more instructive to see the effect of the function evaluation when the qubit in the second register is prepared in the state

The reason for defining the state

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

Of course you can!

One way of doing it is to set your input to

We are presented with an oracle that computes some unknown function

constant | ||

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.

(Deutsch’s).

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

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

This evolution can be represented by the circuit diagram

where the relative phase is ^{117}

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

## 10.5 Three more quantum algorithms

Along with Deutsch’s algorithm, there are three more fundamental quantum algorithms that we will study here. Each one was designed to solve a different specific problem, but they all share some similarity: this omnipresent sequence of Hadamard, function evaluation, Hadamard.

### 10.5.1 The Bernstein-Vazirani algorithm

We are presented with an oracle that computes some unknown function

Our task is to determine, using the fewest queries possible, the value of the

It’s quite easy to see how to do this classically: if we input the value

In contrast, by running the circuit below, it is possible to determine the value of *single* (!) call to the oracle.

(Bernstein-Vazirani).

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

N.B. The “

or even simply

Now, stepping through the execution of the circuit (and ignoring the second register, which remains in state

This lets us write^{119}
*unless* *unless y=a*.
Thus the standard bit-by-bit measurement of the first register gives the value of

Note that the algorithm follows the same pattern as Deutsch’s algorithm: Hadamard, function evaluation, Hadamard, i.e. a generic quantum interference pattern.

### 10.5.2 Grover’s search algorithm

The next algorithm we will study aims to solve the problem of searching for a specific item in an *unsorted* database.
Think about an old-fashioned phone book: the entries are typically sorted alphabetically, by the name of the person that you want to find.
However, what if you were in the opposite situation: you had a phone number and wanted to find the corresponding person’s name?
The phone book is not sorted in that way, and to find the number (and hence name) with, say, 50% probability, you would need to search through, on average, 50% of the entries.
In a large phone book, this would take a long time.

While this might seem like a rather contrived problem (a computer database should always maintain an index on any searchable field), many problems in computer science can be cast in this form, i.e. that of an **unstructured search**.

We are presented with an oracle that computes some unknown function

Our task is to find, using the fewest queries possible, an input

Suppose that we know that, amongst the

In contrast, there is a quantum search algorithm, implemented by the circuit below, that was proposed in 1996 by Lov Grover, and which requires only roughly

(Grover’s search).

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

where

We can recognise the typical Hadamard, function evaluation, Hadamard sequence, and we can see that the second register (the bottom qubit, in state

Here, the basic step is the **Grover iteration operator G**, which is the boxed part of the circuit that we repeat over and over.
After

*with “high” probability*,

*see*how this algorithm works, and to justify our claim that it gives what we are searching for “with high probability”, we can take a more geometric approach.

First, we define two orthonormal vectors in the Hilbert space of the first register:^{120}

This subspace contains the equally-weighted superposition ^{121}

The state

To see this, note that the oracle induces the unitary transformation

Now recall the purely geometric fact that (working in

The angle between

So the quantum algorithm searches an unsorted list of *quadratic* speed-up when compared to classical search, which can be of immense practical importance.
For example, cracking some of the popular ciphers, such as AES (Advanced Encryption Standard), essentially requires a search among *many* binary strings (called **keys**).
If these can be checked at a rate of, say, one million keys per second, then a classical computer would need over a thousand years to find the correct key, while a quantum computer using Grover’s algorithm would find it in less than four minutes.

### 10.5.3 Simon’s problem

Here we will see the simplest quantum algorithm that shows an exponential speed-up compared to the best classical algorithm.

We are presented with an oracle that computes some unknown function **period** of ^{122}
So that the problem is non-trivial (i.e. so that *not* the string of

Our task is to determine, using the fewest queries possible, the value of the

Classically, this problem is exponentially hard.
We will not go through a detailed proof of this fact, but the intuition is reasonably simple: since there is no structure in the function

The quantum case, on the other hand, gives a result with high probability within a *linear* number of steps.
The circuit that solves this problem, shown below, has a familiar Hadamard–function–Hadamard structure, but the second register has been expanded to

(Simon’s problem).

*First register: n qubits. Second register: n qubits.*

Let’s follow the evolution of the two registers in this circuit.
We start off by preparing the equally-weighted superposition of all

Now, if we measure the second register *before* applying the second Hadamard transform to the first, we obtain one of the ^{123}

Suppose that the outcome of the measurement is

The subsequent Hadamard transform on the first register then gives us the final state^{124}

In fact, we do not have to measure the second register at all: it was a mathematical shortcut, simply taken for pedagogical purposes.
Instead of collapsing the state to just one term in a superposition, we can express Equation (6.4.3.1) as^{125}

The output of the algorithm is then

We are not quite done yet: we cannot infer *single* output ^{126} strings *two* elements, since then we know that we can just take the non-zero one.)

So we run this algorithm repeatedly, each time obtaining another value of

Indeed, suppose that we have *outside* the subspace spanned by the ^{127}
the probability of obtaining a linearly independent set

We conclude that we can determine

## 10.6 Remarks and exercises

### 10.6.1 Shor’s algorithm

**!!!TODO!!!**

### 10.6.2 RSA

**!!!TODO!!!**

### 10.6.3 More complexity classes

**!!!TODO!!!**

### 10.6.4

**!!!TODO!!! implementing reflections**

### 10.6.5

**!!!TODO!!! optimality of Grover**

Do not confuse the capital

X , which is the Pauli flip operator\sigma_x , with the smallx , which is a binary string stored in the first register and the argument of our Boolean functionf .↩︎The original Deutsch algorithm provides the correct answer with probability 50%. Here we have presented a modified/improved version.↩︎

The Hadamard transform is a special case of the Fourier transform over the group

\mathbb{Z}_2^n .↩︎Even if you don’t immediately see how this sum works for

z\neq a (writing|z\rangle to mean the output), you can first calculate the probability that the output isz=a . In this case it is easy to see that the sum is2^n , and that in the final state\sum_z\alpha_z|z\rangle the termz=a has amplitude1 . Thus, by normalisation, all the other terms must be equal to0 .↩︎In fact, we shall completely ignore the second register from now on.↩︎

We often omit from our notation the fact that the sum is over all

x\in\{0,1\}^n , leaving it (hopefully) implicitly understood from the context.↩︎This is equivalent to saying that

f is**two-to-one**: for anyy\in\{0,1\}^n such that there exists somex\in\{0,1\}^n withf(x)=y , there exists exactly one otherx'\neq x such thatf(x')=y as well.↩︎As we shall see in a moment, the actual measurement on the second register is not actually necessary.↩︎

We write

s^\perp to mean the set of ally\in\{0,1\}^n such thaty\cdot s=0 .↩︎Recall that the image of

f is the set of allz\in\{0,1\}^n such that there exists somex\in\{0,1\}^n satisfyingf(x)=z .↩︎Here,

**linearly independent**means that no string in the set\{y_1,\ldots,y_n\} can be expressed as the bitwise sum of some other strings in this set.↩︎Use the inequality

\begin{aligned}(1-x)(1-y)&= 1 - x - y - xy\\&\geqslant 1 - (x+y)\end{aligned} which holds for any0<x,y<1 .↩︎