## 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^{131}
*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:^{132}

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

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 ^{134}
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 ^{135}

Suppose that the outcome of the measurement is

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

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^{137}

The output of the algorithm is then

We are not quite done yet: we cannot infer *single* output ^{138} 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 ^{139}
the probability of obtaining a linearly independent set

We conclude that we can determine

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 .↩︎