## 10.6 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.
Needless to say, 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**.

*(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 **tagged**, i.e. strings on which

In contrast, there is a quantum search algorithm, implemented by the circuit below, which requires only roughly ^{208}

*(Grover’s search).*

First register:

where

Yet again, we can recognise the typical Hadamard, function evaluation, Hadamard sequence, and yet again 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^{209} *with “high” probability*, *see* how this algorithm works, and to justify our use of the phrase “with high probability”, we can take a more geometric approach.

First, we define two orthonormal vectors in the Hilbert space describing the first register:^{210}
**preimage** of

Using the fact that **partition**^{211} of the space

The state

To see this, note that the unitary transformation induced by the oracle
^{212}

Some further algebraic manipulation shows that

Now recall the purely geometric fact that if we have two intersecting lines

The angle between

So the quantum algorithm searches an unsorted list of ^{213} *quadratic* speed-up when compared to classical search, which can be of immense practical importance.
For example, cracking some of the more popular modern ciphers, such as AES, 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.

This algorithm is named for Lov Grover, who proposed it in 1996.↩︎

Recall the big-

\mathcal{O} notation introduced in Exercise 1.11.7.↩︎Once again, we shall completely ignore the second register from now on, since all the interesting stuff happens in the first.↩︎

A

**partition**of a setX is a collection of disjoint subsetsX_1,\ldots,X_m\subseteq X whose union is all ofX , i.e.X_i\cap X_j=\varnothing for alli\neq j , andX_1\cup\ldots\cup X_m=X .↩︎To prove this, it suffices to check that these two transformations agree on the standard basis; since

f^{-1}(0) andf^{-1}(1) form a partition, we know that any element (and, in particular, any basis element) is either in the preimage of0 or of1 ; if it is in the former, thenI_a acts as the identity; if the latter, thenI_a acts as-\mathbf{1} .↩︎Recall that

M\ll N , so\sqrt{\frac{N}{M}}\approx\sqrt{N} .↩︎