Mathematical Field Notes

Quantum computers: Grover’s algorithm

leave a comment »

I’ve been meaning to get my head around the idea of a quantum computer for a while now and, since my mathematical energy is currently reduced to clearing out my ETH office, I thought I’d do some reading and find out more. I leafed through my dusty copy of Wikipedia [Wik], picked up Kitaev et al [KSV] from the library and turned to chapter two…

I think the easiest way to illustrate how a quantum computer differs (functionally) from a classical computer is by explaining an algorithm which only makes sense for quantum computers and which really outperforms a classical algorithm for the same task (that is the point of quantum computers, after all). The first algorithm they explain in [KSV] is called Grover’s algorithm and it performs the task of searching a database. Wikipedia [Wik] has a really nice exposition too, but I was initially confused by what they both call a “quantum oracle” (sounds like something from Star Trek TNG). I tried to explicitly avoid that in what I said below.

TLDR: Classically you have to look through all N elements of a database until you find the right one (so runtime increases linearly in N); Grover’s algorithm has a surprising runtime of order \sqrt{N} to do the same thing, using clever ideas from quantum mechanics.

The problem

You have a collection of N objects you want to store on a database. The objects can be either black or white. Each object has an identification number between 1 and N and a colour. For simplicity assume that there’s only one white object in the database and you want to find out its identification number m. A classical computer would work through the objects in the database one by one and check each one to see if it were white. Assume that the probability that the kth object is white is 1/N, then the expected runtime for this classical algorithm would be

\sum_{k=1}^Nk/N=(N+1)/2

which is asymptotically linear in N (i.e. if you have lots and lots of objects then quadrupling the number of objects quadruples the runtime).

Grover [Gro] showed that a quantum computer could do better, with a runtime which goes asymptotically like \sqrt{N} (quadrupling the number of objects only doubles the runtime).

So what is a quantum computer?

Of course I don’t know how to build a physical quantum computer. If I did I’d probably have your bank account details by now. But let me explain how to mathematically model quantum computers: how they manipulate and store data. Classically, you store data as strings of 0s and 1s. On a quantum computer you store data as vectors. A “bit” of a string (i.e. a place where a 0 or 1 could go) is now replaced by a “qubit” – a two dimensional complex vector space with a basis |0\rangle,|1\rangle. Obviously you could represent 0s and 1s by pointing in those directions, but you can now point in a whole host of other directions, linear combinations of the vectors |0\rangle and |1\rangle. Note that the funny notation |v\rangle is standard in quantum mechanics, was introduced by Dirac and makes it easy to talk about vectors in the dual space \langle w| and the number you get by evaluating \langle w| on |v\rangle is \langle w|v\rangle.

A string of bits is replaced by the tensor product of qubits (i.e. of vector spaces). In Dirac’s notation we have a nifty trick for writing tensor products:

|v_1v_2\rangle\equiv|v_1\rangle\otimes |v_2\rangle

Let’s write T for the tensor product of all our qubits (this is now a 2n-dimensional complex vector space) and call it our state space. So a string 0011101 can be transformed into a vector |0011101\rangle, but vectors can be added in all sorts of ways and we end up with points in our state space which don’t correspond to classical data strings.

Ideally, T would be realised as the Hilbert space of some explicit quantum mechanical system, but remember we’re only interested in how to model it mathematically (which is much easier).

Quantum algorithms and measurements

Instead of getting a Turing machine to work along a classical data string manipulating the 0s and 1s according to some program, at each timestep our quantum computer will apply a unitary transformation to the state space T.

After some sequence of unitary transformations have been applied (which we think of as a “quantum algorithm”), we measure the system. Now measurement is a tricky thing in quantum mechanics and I want to avoid that discussion right now. But at least we have to specify what we are measuring. Well suppose we just had one qubit and we applied a load of unitary transformations to it (just unitary 2-by-2 matrices). If we started off with some vector, say |0\rangle, and ended up with another one, say |\xi\rangle, we really want to get back to basics and know if we’ve got a 0 or a 1. But that doesn’t make sense any more! It’s quite possibly a superposition of the two. “Measuring” the 0- or 1-ness of the qubit in a state |\xi\rangle means:

  • we consider the operator which projects the qubit onto the subspace spanned by |1\rangle,
  • this has eigenvalues 0 and 1 with eigenspaces spanned by |0\rangle and |1\rangle respectively,
  • when we measure the system we cause it to collapse into one or the other eigenspace and the number we measure is 0 (with probability |\langle\xi|0\rangle|^2) or 1 (with probability |\langle\xi|1\rangle|^2),
  • in order to ensure that all probabilities sum up to 1 (which they surely should!) we need to normalise our states to have norm 1, i.e. |\langle \xi|\xi\rangle|^2=1.

As I said, I don’t want to justify this – we can treat it as axiomatic or we can go and read Bohm. Either way, we end up getting a probabilistic algorithm (i.e. we have to run the algorithm many times and only afterwards can we guess what |\xi\rangle was by looking at the probabilities).

Grover’s algorithm

State space for the database

First we encode our database into a vector space. Remember our data consists of strings of length n (identification numbers for the N=2n objects) and colours (black or white) for each object (yes I know they’re not colours, it’s a figure of speech).

Introduce basis vectors |x_1x_2\cdots x_n\rangle for each identification number and |B\rangle, |W\rangle for the colours. Form the tensor product T (state space) so that a general basis element is something like

|100101001010\cdots 10010011B\rangle

Unitary transformations for the algorithm

Let U be the unitary operator

U|xB\rangle\equiv|xB\rangle,\qquad U|xW\rangle\equiv-|xW\rangle

(writing x for an arbitrary identification number) and let

|\xi\rangle\equiv\frac{1}{\sqrt{N}}\sum_x|xC(x)\rangle

where C(x) denotes the colour of object x and the coefficient is for normalisation (we want all states to have norm one). Finally we define

V\equiv 2|\xi\rangle\langle\xi|-1.

The funny notation need another word of explanation: |\xi\rangle\langle\xi| means the operator sending a vector |w\rangle to |\xi\rangle\langle\xi|w\rangle (which is just a rescaling of |\xi\rangle by the number \langle\xi|w\rangle).

These (U and V) are the unitary transformations we’ll use in Grover’s algorithm.

Notice that they’re both reflections: U reflects in the hyperplane orthogonal to all white vectors and V acts as -1 on the hyperplane |\xi\rangle^{\perp} orthogonal to |\xi\rangle and preserves the vector |\xi\rangle.

The algorithm

We apply the composite transformation VU to T and specifically look at what happens to the vector |\xi\rangle which we defined above as \frac{1}{\sqrt{N}}\sum_x|xC(x)\rangle.

Diagram showing how the composite map VU is a rotation. What is the operation VU? It’s a composition of two reflections and hence it’s a rotation. To understand exactly what’s rotating where, let’s write |\xi'\rangle for the projection of |\xi\rangle to the subspace spanned by black vectors (normalising |\xi'\rangle to have norm 1) and restrict attention to the 2-dimensional subspace spanned by |\xi'\rangle and the vector |mW\rangle, corresponding to the unique white vector in our dataset (remember I told you a long time ago that m is the identification number of the unique white object!).

Now |\xi\rangle is a linear combination of |\xi'\rangle and |mW\rangle by construction, say

|\xi\rangle=\cos\phi|\xi'\rangle+\sin\phi|mW\rangle

Moreover, we know that the coefficient of |mW\rangle in |\xi\rangle is 1/\sqrt{N}, so

\sin(\phi)=1/\sqrt{N}.

The two reflections U and V preserve the 2-dimensional subspace spanned by |\xi'\rangle and the vector |mW\rangle. Indeed, reflecting using U gives

U|\xi\rangle=\cos\phi|\xi'\rangle-\sin\phi|mW\rangle

and the using V (exercise, very clear when you draw the picture!) gives

VU|\xi\rangle=\cos(\phi+2\phi)|\xi'\rangle+\sin(\phi+2\phi)|mW\rangle

In other words, VU is a rotation by 2\phi towards |mW\rangle. If we rotate R times then the |mW\rangle-component of (VU)^R|\xi\rangle is

\sin((2R+1)\phi)

and (remembering our discussion about measurement) the square of this quantity

\sin^2((2R+1)\phi)

has an interpretation as the probability that we get the right identification number for the white object when we measure the identification number in this state (i.e. after rotation). When N is large \phi is very small and we can pick R to make \sin^2((2R+1)\phi) very close to 1. Indeed, when N is enormous, so that \phi\approx\sin\phi=1/\sqrt{N} it’s clear that we need 2R/\sqrt{N}\approx \pi, i.e.

R\approx \pi\sqrt{N}/2\mbox{ iterations}.

Note: we don’t want to do any more than this, or else we start rotating away from |mW\rangle!

Conclusion

We only had to do Grover’s algorithm about \pi\sqrt{N}/2 times to the right answer with high probability, which is a big saving – if we quadruple the number of objects in the database then classically we quadruple computing time, but with Grover’s algorithm we only double it!

Of course, we need to repeat the experiment many times to get a probability distribution and pick the identification number which seems to occur with a frequency

\sin^2((2R+1)\phi)

but we can do this a fixed number of times (independently of N) because the probability that we get the right answer is improving with N. All in all, we quadratically save computational effort and it’s all thanks to the tricksy use of (purely formal) quantum mechanics.

Of course, it’s not clear to me how you would really implement this algorithm (How would you start the quantum computer in the state |\xi\rangle? How would you actually do the unitary transformations?) so we should really treat it as a mathematical abstraction until further notice. However, it’s a simple and surprising illustration of the power of quantum mechanics.

This post was brought to you by the numbers 0 and 1 and the letter Q.

References

[Gro] L. Grover, “A fast quantum mechanical algorithm for database search”, Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC), May 1996, pages 212-219, arXiv: quant-ph/9605043

[KSV] A. Y. Kitaev, A. H. Shen, M. N. Vyalyi, “Classical and Quantum Computation”, Grad. Stud. in Math. Vol. 47 (2002) AMS, Providence

[Wik] Wikipedia (13.08.2012) http://en.wikipedia.org/wiki/Grover’s_algorithm

Advertisements

Written by Jonny Evans

August 13, 2012 at 10:13 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: