2003 - Quantum Computation Lecture 6 - Grover's Search Algorithm

Duration: 00:41:05

Transcript

David Deutsch

00:01:00 - 00:03:06

Today, I’m going to describe a remarkable quantum algorithm which was invented by Lov Grover in 1996. It’s a search algorithm suitable for a very broad category of computational task known as algorithmic searching. Algorithmic searching is just exhaustive searching for a number with a given mathematical property. It’s a programmer’s last resort in addressing computational tasks where there’s a quick way of verifying that a given number is the answer once you have it, but no easy way of constructing the answer. In other words, the task is we’re given a criterion for whether a number is the answer or not. We’re given it in the form of an algorithm $F$ that delivers an output $+1$ or $-1$ where minus one means that the input meets the criterion and plus one that it doesn’t. And we have to find a value $t$ , the target value, such that $F(t)=-1$ . Suppose there are $N$ possible values that have to be searched. And suppose for simplicity that $N=2^L$ for some integer $L$ so that we can encode each possible value uniquely in a register of $L$ qubits. By the way, note that the conventional representation for binary numbers stored in qubits is that the eigenvalue $+1$ state represents the binary digit zero and the $-1$ state represents the digit one. Anyway, suppose that there’s exactly one value that meets the criterion in the range that we want to search.

00:03:06 - 00:05:12

That’s the target value $t$ with $F(t)=-1$ . For all other values $x\ne t$ , $F(x)=+1$ . And we’re given a classical reversible algorithm for evaluating $F$ on an arbitrary $L$ -bit input. Like last time, we’re given this in the form of an oracle. It’s some sort of computer operating coherently on a certain number of qubits that we can give it as input and then get out again after a fixed period. But we’re not allowed to look inside it. Now that models the fact that we’re only doing this search in the first place because we’ve exhausted all ways of simplifying the problem analytically. And we’re looking for an exhaustive search algorithm, one that doesn’t depend on our knowing anything about the structure of the function $F$ . So the oracle computes $F$ on an $L$ -bit input and gives us a one-bit output, whether it meets the criterion or not. But again, because of reversibility, it must actually have the same number of outputs as inputs. So it must operate something like this. For inputs $x$ and $y$ , where $x$ can take one of $2^L$ values and $y$ can take one of two values, $+1$ or $-1$ , it gives an output $(x,yF(x))$ . So the oracle as a whole operates on $L+1$ qubits. And it may also contain an unknown number of internal qubits that we never see. How many evaluations of $F$ , how many invocations of the oracle, are we going to need to find the unique value of $t$ such that $F(t)=-1$ ?

00:05:12 - 00:07:31

Well, by a similar argument to last time, it’s clear that we may need to invoke the oracle as many as $N-1$ times. It’s $N-1$ rather than $N$ , because if the conditions of the task say that there’s exactly one value meeting the criterion and we’ve checked all but one of the possible values, then we know that the answer is the remaining value. But that’s the only break we get. We could check the values randomly and then on average we’d probably need about $N/2$ oracle invocations, probably. Using quantum computation in which the oracle receives different inputs in different universes, we can do a great deal better than that and that’s what Grover’s algorithm does. Grover’s algorithm uses three simple subroutines, so I’ll describe those separately first and then put them together. The first subroutine involves the Hadamard gate that I introduced last time. It consists of applying a Hadamard gate to each of $L$ qubits. In our case, it’s the $L$ qubits in our $L$ -qubit register, like this. I’ll call this operation $\mathbf{H}$ to distinguish it from a single qubit Hadamard gate. The algorithm begins, as I advocated last time, with all $L$ of these qubits in their blank initial state where they all have sharp values plus one and I’ll call that state $|0\rangle$ . It’s a state of $L$ qubits all in state plus one. The effect of H on the blank state is $\mathbf{H}|0\rangle=2^{-L/2}(|+\rangle+|-\rangle)^{\otimes L}$ .

00:07:31 - 00:11:04

$L$ factors in the tensor product. This state of the $L$ qubits plays an important role in the analysis of this algorithm, so let me give it a name, $\mu$ . So $\mathbf{H}|0\rangle=|\mu\rangle$ and since the Hadamard gate is its own inverse, it must also be true that $\mathbf{H}|\mu\rangle=|0\rangle$ . If we multiply out mu, we see that it consists of a superposition of states with all $N=2^L$ possible sequences of plus and minus values representing the $2^L$ possible values of $x$ . Hence, if $|x\rangle$ is any computation basis state, the scalar product is $\langle x|\mu\rangle=1/\sqrt{N}$ . Okay, the next subroutine involves the oracle with its $L$ qubits to hold the argument of $F$ and its one auxiliary qubit. I’ll call this the marking subroutine, $M$ . You’ll see why in a moment. It starts with the auxiliary bit being put through a NOT gate and then a Hadamard gate. That’s just to prepare it in the state $\frac{1}{\sqrt{2}}(|+\rangle-|-\rangle)$ . With that as the input for the auxiliary qubit, the effect of the oracle on a sharp state of the first $L$ qubits with the value $x$ is, well as always, $x$ passes through unchanged and the value of $F(x)$ is exclusive-ORed into the auxiliary qubit, which in this case just multiplies the overall state by $F(x)$ . That means that the auxiliary qubit is left unchanged. $M$ could run repeatedly just recycling the same qubit which never changes. So it never receives any information, which means in turn that the first $L$ qubits never receive any information from it. So these first $L$ qubits by themselves evolve autonomously, which means as I said in lecture four, that they undergo coherent evolution during the process $M$ . And the effect of $M$ is that of a unitary matrix acting on the state of those $L$ qubits alone. So we don’t have to mention the auxiliary qubit explicitly when we analyse algorithms involving $M$ , just as we don’t explicitly mention the unseen qubits in the oracle when it computes $F$ .

00:11:11 - 00:13:50

The net effect of $M$ on the $L$ qubits holding $x$ can be summarised as $M|x\rangle=F(x)|x\rangle$ . Explicitly the unitary matrix that is $M$ is $I-2|t\rangle\langle t|$ . That’s because the computation basis states are orthonormal. So $M|t\rangle=-|t\rangle$ and $M$ operating on any other computation basis state leaves the state unchanged. Hence also the effect of $M$ on the state $\mu$ is $M|\mu\rangle=\frac{1}{\sqrt N}M\sum_x|x\rangle=\frac{1}{\sqrt N}\sum_x F(x)|x\rangle$ . Now for all but one value of $x$ , $F(x)$ is $+1$ , only $F(t)$ is $-1$ . Now you can see why I called this the marking operation. It marks the target term in the superposition by changing its sign. And we can write the effect of $M$ in terms of states I’ve already named like this. The third subroutine, which I’ll call $B$ , is just marking the blank state. Or for convenience actually, we’re going to mark everything but the blank state. So this operation is like $M$ , except that instead of the oracle, it uses a network that performs the NAND operation on all $L$ inputs and exclusive-ORs the result into the auxiliary qubit. That means that for computation basis state inputs, the auxiliary qubit is flipped unless the first $L$ inputs are all plus one. And we’ll use the same trick of using a Hadamard gate to prepare the auxiliary qubit in a state $\frac{1}{\sqrt{2}}(|+\rangle-|-\rangle)$ , giving us an $L$ -qubit operation $B$ .

00:13:51 - 00:16:38

The effect of $B$ is that $B|0\rangle=|0\rangle$ , and $B$ on any other computation basis state is minus that state. So $B=2|0\rangle\langle0|-I$ . Those are the ingredients of Grover’s algorithm. All of them are operations on $L$ qubits. There’s the operation $\mathbf{H}$ , which transforms the blank state to the grand superposition $\mu$ and vice versa. $M$ , which marks the target state, and $B$ , which marks all computation basis states except the blank state. Grover’s algorithm consists of starting with a blank initial state, perform $\mathbf{H}$ , which makes the state $\mu$ , and then perform a certain number of iterations of the sequence $M$ , then $\mathbf{H}$ , then $B$ , then $\mathbf{H}$ again. So the net effect of such an iteration called the Grover iteration on an arbitrary state is given by the unitary matrix $\mathbf{H}B\mathbf{H}M$ . They’re in reverse order to the order they’re performed in because it’s the rightmost factor that hits the ket first. We’ll see in a moment how many of these Grover iterations you have to do. That’s it. Now what does all that do and why does it work? There’s a beautiful geometric interpretation of what it’s doing. Let’s take a look at a two-dimensional plane through the $2^L$ -dimensional Hilbert space of these $L$ qubits. The plane is defined as the one containing both the target state $|t\rangle$ and the superposition $|\mu\rangle$ .

00:16:39 - 00:19:03

Now $|t\rangle$ and $|\mu\rangle$ are very nearly orthogonal for large $N$ . But never quite orthogonal. Their scalar product is $1/\sqrt{N}$ . Let’s define a state that is orthogonal to $|t\rangle$ here. Call it $\phi$ . And now consider a family of states all lying in this plane. $\cos\theta|\phi\rangle+\sin\theta|t\rangle$ , where $\theta$ is a real parameter. The state that we want to end up in, namely $|t\rangle$ , is in this parameterized family with $\theta=\pi/2$ . And at the moment after our initial Hadamard operation, just before we start the iterations, we’re in the state $|\mu\rangle$ , which is also of this form, but with $\theta=\arcsin(1/\sqrt{N})$ . For a general state of this form, what’s the effect of one Grover iteration? Well, the Grover iteration begins with an $M$ operation, and we know what the effect of $M$ is. It changes the sign of the coefficient of the target $|t\rangle$ , and it leaves all other computation basis states unchanged. Hence, the effect of $M$ on a general state in this plane is to reflect it in the horizontal axis. After $M$ , we do $\mathbf{H}B\mathbf{H}$ , and we can simplify that if we just substitute what $\mathbf{H}$ and $B$ are as unitary matrices. Substituting the unitary matrices gives the reflection formula.

00:19:03 - 00:21:14

We get $\mathbf{H}B\mathbf{H}=2|\mu\rangle\langle\mu|-I$ , which has no effect on the state $|\mu\rangle$ , but changes the sign of any state perpendicular to $\mu$ . In other words, the effect of $\mathbf{H}B\mathbf{H}$ on an arbitrary state in this plane is to reflect it in the line $\mu$ . The product of these two reflections, namely the Grover iteration as a whole, is a rotation. You can easily prove that it’s a rotation through an angle $2\arcsin(1/\sqrt{N})$ . Exactly twice this angle, and in the anti-clockwise direction. In other words, towards $|t\rangle$ . So, each Grover iteration rotates the state a little closer to our target. Until we go past it and then get further away from it again. So, it’s vital to choose the right number of iterations. And the right number will be $\pi/2$ divided by the angle that the rotation rotates the state by. Except that because we start the rotation at half that angle away from the horizontal, that means that the state will be closest to the target $|t\rangle$ after the integer part of that number of operations. Namely, $\left\lfloor\frac{\pi}{4\arcsin(1/\sqrt N)}\right\rfloor$ .

00:21:14 - 00:23:19

Roughly speaking, that’s a constant times $\sqrt{N}$ . So, Grover’s algorithm completes its search using about the square root of the number of oracle calls required using classical computation. That’s a tremendous saving. You can search a million possibilities in only about a thousand iterations. A trillion possibilities in only a million iterations. Now, just a small detail. The state at the end won’t have exactly hit the target state. Except when $N=4$ , by the way. You might like to check that interesting special case where a single oracle call is actually enough to do the whole search. But for all other values, the output of Grover’s algorithm is not a computation basis state at all. It’s a state of the $L$ qubits that’s close to but not equal to the target state. Does that matter? It doesn’t because, well, suppose Grover’s algorithm delivers a state $\cos\epsilon|t\rangle+\sin\epsilon|\phi\rangle$ . Well, from the argument I’ve just given, we can expect $\epsilon$ to be less than about $1/\sqrt{N}$ , which is very small. Well, suppose we then measure the output value of the $L$ qubits and check whether it’s correct, whether it’s the value such that $F(t)=-1$ . We can do that very easily by using the oracle one more time, this time with the auxiliary qubit initially blank, with the sharp value $+1$ , like this. And then running the oracle will flip the sign of the component that goes with $|t\rangle$ and leave the other one alone.

00:23:19 - 00:25:38

What is then the expectation value of the $Z$ component of that auxiliary qubit? If the output had been sharply at the target value, then $Z$ for the auxiliary qubit would also be sharp with value minus 1. If its expectation value is anything above that, that means that the answer was wrong in some universes, and we can work out how many. The expectation value of $Z$ is $\operatorname{tr}(\rho Z)$ . And $\rho$ for this pure state gives the expectation value of $Z$ . So we get the expectation value $-\cos^2\epsilon+\sin^2\epsilon$ , which is $-1+O(\epsilon^2)$ . So the probability of seeing a wrong answer, that is, the proportion of universes in which the answer will be wrong, is of order $O(1/N)$ . Very small. In practice, many other small errors will be introduced by physical factors such as noise, or the fact that the computer doesn’t perfectly match its ideal design. But it’s in the nature of algorithmic searching that we can’t be led astray by such errors. We check the result, and in the rare cases when it’s wrong, we just run the algorithm again. You’ll see in the worked examples that Grover’s algorithm can also be used in cases where more than one value satisfies the target criterion, and that it speeds up such searches by the same factor.

00:25:41 - 00:27:33

It has been proved that the algorithm is optimal. That is, no algorithm, quantum or classical, can ever do an exhaustive algorithmic search faster than Grover’s. Though bear in mind that the proof of this applies only to the oracle version of the searching task, which is an idealization. In real life algorithmic searches, we often do know something about the structure of the function we’re investigating, and this knowledge can be used to speed up searching. The possibility is still open that in some cases it speeds up quantum searching by more than classical searching. In other cases though, it offsets the benefit of quantum searching altogether. I once mentioned in a popular article about quantum computers that one day, Grover’s algorithm will be used to make super powerful chess-playing machines. My thought was that since the best classical chess-playing algorithms work by exhaustively searching all possible continuations of the game from a given position, Grover’s algorithm would allow one to search the square of the number of possibilities in a given number of steps, a huge improvement. But no, as was pointed out by Richard Cleve, the nature of that kind of search, which has a tree-like structure, is that most of the work of computing any of the final positions is shared with many other final positions. And under those circumstances, the advantage of Grover’s algorithm over conventional tree searching disappears. And the same seems to be true of game playing in general.

00:27:33 - 00:29:37

Though I should add that that doesn’t rule out the possibility that there may be other quantum algorithms for playing certain games. Grover’s paper in which he first published his algorithm was called A Fast Quantum Mechanical Algorithm for Database Search. That’s a slightly misleading name because the algorithm is probably at its least useful in searching databases. First of all, if your database is a custom-built physical object like an oracle containing essentially a read-only memory of $N$ bits or $N$ qubits, then it would surely be easier just to store the single value $t$ and it could just tell you that value on request and you wouldn’t have to do any searching. On the other hand, if the database is not known in advance or if the query you’re going to make is not known in advance, suppose the data was some recently gathered data from the search for extraterrestrial intelligence and you want to search it for a given pattern, well then the act of reading the data into a quantum computer memory or imprinting it permanently on an oracle is itself a task that takes of the order of $N$ operations. So Grover’s algorithm would only speed up database searching by perhaps a constant factor and even that factor might be swamped by the extra technological difficulty of doing coherent quantum computations as opposed to incoherent classical ones. Or it might not, but in any case, once there are quantum computers, Grover’s algorithm will be unrivaled when it comes to algorithmic searching which includes a wide variety of very important tasks.

00:29:37 - 00:31:38

There’s a large number of tasks, some of which currently take up a lot of computer time where there’s at present no known alternative but the hard slog of try $F(1)$ , try $F(2)$ , try $F(3)$ and so on and where having tried any number of such guesses gives you little or no useful information about where the target may be among the remaining possibilities. Perhaps the archetypal case of this is cryptanalysis, the science of reading encrypted messages. One of the basic computational tasks of cryptanalysis comes up when we know the cryptographic system that was used by the writer of an encrypted message but we don’t know the key that they used for that session. We know the decoding algorithm, but not the key that would make it decode the ciphertext correctly. Say we have an encrypted message, ciphertext C and we know that the original plain text was written in English, say. To solve that problem by algorithmic search means to try one value of k after another until we find one for which the decoding algorithm yields a message that seems to be an English text. More generally, the problems for which algorithmic search is useful are in the complexity class called NP, basically problems where it’s easy to recognise a solution once you have it. And they especially include the important subset of NP called NP-complete which includes problems such as the travelling salesman problem.

00:31:38 - 00:33:43

Grover’s algorithm will speed up the solution of such problems by a factor of $\sqrt{N}$ . That doesn’t make such problems tractable on a quantum computer in the language of complexity theorists because the technical definition of a tractable task is one which for very large $N$ requires only some power of $\log N$ steps. But if you’re a programmer contemplating an algorithmic search of a trillion possibilities to solve some vital design problem or whatever, it’ll be a great help to have a way of doing that that uses only a million function calls instead of a trillion. With cryptanalysis, the numbers are much larger still and in general, the harder the task is, the greater the advantage Grover’s algorithm will confer. Let me try to give a feel for the numbers involved. Imagine some future quantum computer that’s performing Grover’s algorithm. Say it has a quantum processor capable of performing a hundred million calls of criterion $F$ per second. And suppose it’s engaged in a particularly arduous search through a space of $10^{30}$ possible solutions looking for the one with $F(t)=-1$ . How long will that take? Well, it’ll require about $10^{15}$ calls of $F$ which at 100 million calls per second will take about $10^7$ seconds or about 4 months. A classical computer with the same processor speed would require about $5\times10^{29}$ calls of $F$ which would take it $5\times10^{21}$ seconds or very nearly the age of the universe.

00:33:43 - 00:35:39

That’s the size of the practical benefit of the quantum search algorithm over the classical. But the theoretical implication is even more mind-boggling because we know how Grover’s algorithm works. It isn’t just doing $10^{15}$ evaluations of $F$ in parallel which you could mimic classically by, say, making all the computers on earth work on nothing but this problem. The quantum processor is doing $10^{30}$ possible computations of $F$ in parallel every time it’s invoked. If all the silicon in the whole of our planet were made into microchips of 1 cubic millimetre each and they were all set performing different computations there’d still be fewer distinct computations going on in that giant parallel computer than there would be in a single quantum processor performing Grover’s algorithm. That’s a measure of the complexity of structure and process that exists in ordinary matter just beyond our perception because quantum processes are of course going on all the time everywhere. In a quantum computer, some small part of that complexity is put to good use. Thank you.

Markdown