CSE 599d - Quantum Computing

Grover’s Algorithm

Dave Bacon
Department of Computer Science & Engineering, University of Washington

After Peter Shor demonstrated that quantum computers could efficiently factor, great interest arose in finding
other problems for which quantum algorithms could outperform the best known classical algorithms. One of the early
offshoots of this work was an algorithm invented by Lov Grover in 1996. Here we will describe Grover’s algorithm
and show that it is, in a query complexity manner, the optimal quantum algorithm.

I. GROVER’S ALGORITHM

Suppose that we have a function f (x) from {0, 1}n to {0, 1} which is zero on all inputs except for a single (marked)
item x0 : f (x) = δx,x0 . By querying this function you wish to find the marked item x0 . This is like finding a needle
in a haystack. Certainly if you have no information about the particular x0 , then finding this marked item is very
difficult. In the worst case it will take 2n − 1 queries to find x0 for a deterministic algorithm. Well what if we turn
this haystack into a quantum haystack? This is the question that Grover asked.
In the quantum version of Grover’s problem we have access to a function which computes f (x) in our standard
reversible manner:
X
Uf = |xihx| ⊗ |y ⊕ f (x)ihy|. (1)
x,y∈{0,1}n

Using our standard trick of phase kickback, we can feed |−i = √12 (|0i − |1i) into the y register of this unitary. If we
do this, then the effect on the first register is still unitary and is given by
X X
Vf = (−1)f (x) |xihx| = (−1)δx,x0 |xihx| (2)
x∈{0,1}n x∈{0,1}n

We will therefore assume that we have query access Pto Vf .

Consider the two vectors |x0 i and |ψi = √12n x∈{0,1}n |xi. These vectors are not orthogonal, hx0 |ψi = √12n ,
however they are linearly independent. Thus we can for a two dimensional basis for the subspace of vectors which are
linear superpositions of these two basis elements. One such choice of basis consists of |x0 i and
1 X
|ψ 0 i = √ n |xi (3)
2 − 1 x∈{0,1}n ,x6=x
0

We note that
r
2n − 1 0 1
|ψi = |ψ i + √ |x0 i. (4)
2n 2n
Now notice that Vf preserve the subspace |x0 i, |ψ 0 i:
Vf |x0 i = −|x0 i
Vf |ψ 0 i = |ψ 0 i. (5)
Now consider the unitary W = 2|ψihψ| − I. This is unitary? Yes because (2|ψihψ| − I)(2|ψihψ| − I)† = 4|ψihψ| −
2|ψihψ| − 2|ψihψ| + I = I. W also preserves the subspace spanned by |x0 i and |ψi:
p
2 (2n − 1) 0
 
2 2
W |x0 i = (2|ψihψ| − I)|x0 i = √ |ψi − |x0 i = |ψ i + − 1 |x0 i
2n 2n 2n
r √
2n − 1 2(2n − 1) 2 2n − 1
 
W |ψ 0 i = (2|ψihψ| − I)|ψ 0 i = 2 |ψi − |ψ 0
i = − 1 |ψ 0
i + |x0 i
2n 2n 2n
√
2 2n − 1
 
2 0
= − − 1 |ψ i + |x0 i (6)
2n 2n
 2

We can rewrite this as a rotation about an angle θ:

W |x0 i = − cos θ|x0 i + sin θ|ψ 0 i
W |ψ 0 i = sin θ|x0 i + cos θ|ψ 0 i (7)
where
√
2 2n − 1
sin θ = (8)
2n
If we combine W and Vf together, we can form what is called Grover’s iterate, G = W Vf . This acts as
G|x0 i = cos θ|x0 i − sin θ|ψ 0 i
G|ψ 0 i = sin θ|x0 i + cos θ|ψ 0 i (9)
Thus we see that the Grover’s iterate takes |ψ 0 and rotates it towards |x0 i.
Now we can describe Grover’s algorithm. We are trying to find |x0 i. We cannot prepare |ψ 0 i or |x0 i, but we can
prepare the superposition of them |ψi with no knowledge of |x0 i. This has most of its amplitude on |ψ 0 i. Now by
applying the Grover iterate, we can rotate this initial state towards the state with more amplitude on |x0 i. Notice
that each Grover iterate requires a query of the function. So is it possible to use Grover’s iterate to perform this
rotation with enough fidelity and few enough queries to beat out the classical case? Well let’s see!
The initial state is
r
2n − 1 0 1
|ψi = |ψ i + √ |x0 i. (10)
2n 2n
Apply G k times will achieve the rotation
Gk |x0 i = cos kθ|x0 i − sin kθ|ψ 0 i
Gk |ψ 0 i = sin kθ|x0 i + cos kθ|ψ 0 i (11)
For what k is this just the rotation which swaps |x0 i and |ψ 0 i (with a phase)? This is when sin θk = π2 . Now lets be
√ n √ n
physicists and use the small angle approximation for sin: sin θ = 2 22n −1 implies θ ≈ 2 22n −1 for large n. Thus we
need
√
2 2n − 1 π
k ≈ (12)
2n 2
or
π 2n π√ n
k≈ √ n ≈ 2 (13)
4 2 −1 4
√
Thus we see that if we perform 2n rotations, we can approximately flip |x0 i and |φ0 i. If we originally started with
|ψi, then with very high probability we will obtain |x0 i after this rotation. We haven’t dotted our probabilities or
crossed our bounds here, but with a little work this can be done. What is important to notice is that there is a
quadratic speedup in the number of queries needed to search compared to the classical situation.
What about the circuit costs for Grover’s algorithm? Well there is the query cost, which we’ve already computed.
And then there is W . How do we efficiently implement W = 2|ψihψ| − I? Well notice that this is W = H ⊗n (2|0ih0| −
I)H ⊗n where H is our friend the Hadamard gate. Thus we need to know how to implement (2|0ih0| − I efficiently.
This unitary maps all of states to themselves, with |0ih0| acquiring no phase and all of the other computational basis
states acquiring a −1 phase. It is useful to introduce a global phase which reverse this: −2|0ih0| + I. One way to
implement this gate is as follows. First note that you can construct a multiple controlled operation using Tofolli
gates, a single controlled gate, and some extra ancilla workspace qubits initialized to |0i (they will also end up being
|0i.) To do this, for the qubits you want to condition on, compute the AND of the first two qubits and put it into
an ancilla workspace qubit using a Tofolli, then compute the AND of this qubit and the third qubit into a second
workspace qubit using a Tofolli. Continuing in this way you see that in n qubits you can obtain the AND of all the
control bits calculated in some ancilla register. Conditional on this qubit perform the desired controlled gate on the
target qubit. Then run in reverse the Tofolli circuit you have perform, thus erasing the garbage in the aniclla qubits.
Now to implemen −2|0ih0| + I, notice that if you perform a n − 1 qubit controlled Z (Z is the Pauli phase operator),
then this gate is −2|1n ih1n | + I. Simply applying X ⊗n before and after this gate turns this into the desired gate (up
to the global phase.) Thus we see that we can implement W using O(2n) elementary gates. Note that this operation
W is sometimes called the “invert about the mean” operation. I leave it to you to determine why it has this name.
 3

II. OPTIMALITY OF GROVER’S ALGORITHM

So we have seen that Grover’s algorithm offers a speedup which is quadratic in finding the needle in the haystack.
A good question to ask is whether we could have done any better. There is a distinct way in which we could not have
done better and that is if we require ourselves to query f in the manner we have described then Grover’s algorithm
is optimal. Let’s prove this.
Suppose we start our attempt to determine f by starting in the state |ψi. Now we apply a sequence of oracle calls
followed by arbitrary (but independent of the oracles) unitaries. Suppose the oracle we use is the phase-kicked back
oracle

Vf = I − 2|x0 ihx0 | (14)

Then the algorithm will produce the state,

|φkx0 i = Uk Vf Uk−1 Vf · · · U2 Vf U1 Vf |ψi (15)

Notice that Vf depends on x0 . If we hadn’t called the oracle, we would be in the state

|φk i = Uk Uk−1 · · · U2 U1 |ψi. (16)

This setup is the most general setup for querying the oracle. We want to show that when we do this it is impossible
to make the |φkx0 i orthogonal enough such that a measurement can distinguish these different states (for different x0
values) unless we make k big enough (i.e the number of queries is high enough.) We do this by showing that we need
k large to make
X
rk = |||φkx0 i − |φk i||2 (17)
x0 ∈{0,1}n

is small unless k is large enough. Then we will show that this implies that when this quantity is small there is no way
to identify the x0 with high probability. Why do we choose |φk i? Well this is the state that would exist if no oracle
calls were made, so measuring our distance from this state is measuring how much effect the oracle is having.
So first we want to bound rk . To do this we show that rk ≤ 4k 2 . This is clearly true for k = 0. We proceed
inductively. First we use the fact that Uk+1 is unitary:

|||φk+1
x0 i − |φ
k+1 2
i|| = ||Uk+1 Vf |φkx0 i − Uk+1 |φk i||2 = ||Vf |φkx0 i − |φk i||2 (18)

The fact that this expression is equal is a consequence of the fact that the |φkx0 i and |φk i states cannot be made more
orthogonal by a unitary rotation. The only operator which can make them more orthogonal is Vf . Now we reexpress
this as

|||φk+1
x0 i − |φ
k+1 2
i|| = ||Vf (|φkx0 i − |φk i) + (Vf − I)|φk i||2 (19)

Next use the inequality |||ai + |bi||2 ≤ |||ai||2 + |||bi||2 + 2|||ai|| |||bi|| to obtain

|||φk+1
x0 i − |φ
k+1 2
i|| ≤ ||Vf (|φkx0 i − |φk i)||2 + ||(Vf − I)|φk i||2 + 2||Vf (|φkx0 i − |φk i)|| ||(Vf − I)|φk i|| (20)

Since Vf is unitary,

|||φk+1
x0 i − |φ
k+1 2
i|| ≤ ||(|φkx0 i − |φk i)||2 + ||(Vf − I)|φk i||2 + 2||(|φkx0 i − |φk i)|| ||(Vf − I)|φk i|| (21)

Now Vf − I = −2|x0 ihx0 |, so this becomes

|||φk+1
x0 i − |φ
k+1 2
i|| ≤ ||(|φkx0 i − |φk i)||2 + || − 2|x0 ihx0 ||φk i||2 + 2||(|φkx0 i − |φk i)|| || − 2|x0 ihx0 |φk i|| (22)

or

|||φk+1
x0 i − |φ
k+1 2
i|| ≤ ||(|φkx0 i − |φk i)||2 + 4||hx0 |φk i|x0 i||2 + 4||(|φkx0 i − |φk i)|| ||hx0 |φk i|x0 i|| (23)

Summing this over x0 we obtain

X
4||hx0 |φk i|x0 i||2 + 4||(|φkx0 i − |φk i)|| ||hx0 |φk i|x0 i||


rk+1 ≤ rk + (24)
x0 ∈{0,1}n
 4

4||hx0 |φk i|x0 i||2 = 1, this becomes

P
Now x0 ∈{0,1}n
X
rk+1 ≤ rk + 4 + 4||(|φkx0 i − |φk i)|| ||hx0 |φk i|x0 i|| (25)
x0 ∈{0,1}n

or
X
rk+1 ≤ rk + 4 + 4||(|φkx0 i − |φk i)|| |hx0 |φk i| (26)
x0 ∈{0,1}n

Now the Cauchy-Schwarz inequality for a real space is

n
!2 n n
X X X
xi yi ≤ x2i yj2 (27)
i=1 i=1 j=1

Applying this to our sum we obtain

  21   21
X X
rk+1 ≤ rk + 4 + 4  ||(|φkx0 i − |φk i)||2   |hx0 |φk i|2  (28)
x0 ∈{0,1}n x0 ∈{0,1}n

or
√
rk+1 ≤ rk + 4 + 4 rk (29)

Now from our inductive hypothesis rk ≤ 4k 2 , so rk+1 ≤ 4k 2 + 4 + 42k = 4(k 2 + 2k + 1) = 4(k + 1)2 . Thus we have
showed that rk ≤ 4k 2 for all k.
The next part of the proof is to show that if rk is small then we cannot distinguish the different vectors |φkx0 i with high
probability. Suppose that we wish to identify x0 with probability greater than one half. Then, without loss of generality
assume that the basis we use to make this distinction is the computational basis. In order for this to succeed we require
that |hx0 |φkx0 i|2 ≥ 12 . This in turn implies that |||φkx0 i − |x0 i||2 = (hφkx0 |−ix0 |)(|φkx0 i − |x0 i) = 2 − hφkx0 |x0 i − hx0 |φkx0 i.
We can always adjust the global phase of the computational basis states to make the last two terms sum to a real
number and our bound on probability then yields
√
|||φkx0 i − |x0 i||2 ≤ 2 − 2 (30)

Now we want to show that if this is true that rk must be large. So we do the obvious and stick in one of those |x0 i
states into our expression for rk :
X
rk = |||φkx0 i − |x0 i + |x0 i − |φk i||2 (31)
x0 ∈{0,1}n

which is bounded by
X  k
|||φx0 i − |x0 i||2 + |||φk i − |x0 i||2 − 2|||φkx0 i − |x0 i|| |||φk i − |x0 i||

rk ≥ (32)
x0 ∈{0,1}n

The Cauchy-Schwarz inequality implies

  21
X X X
|||φkx0 i − |x0 i|| |||φk i − |x0 i|| ≤  |||φkx0 i − |x0 i||2 |||φk i − |x0 i||2  (33)
x0 ∈{0,1}n x0 ∈{0,1}n x0 ∈{0,1}n

Thus
   21   12 2
X X
rk ≥ −  |||φkx0 i − |x0 i||2  +  |||φk i − |x0 i||2   (34)
 
x0 ∈{0,1}n x0 ∈{0,1}n
 5

Now let’s bound that last term

X X X
|||φk i − |x0 i||2 = hφk |φk i + hx0 |x0 i − hφk |x0 i − hx0 |φk i = 22n − hφk |x0 i + hx0 |φk i (35)
x0 ∈{0,1}n x0 ∈{0,1}n x0 ∈{0,1}n

Which we can bound as

X X
|||φk i − |x0 i||2 ≥ 22n − 2 |hφk |xi| (36)
x0 ∈{0,1}n x0 ∈{0,1}n

Cauchy-Schwarz yields
 2
X X X
 |hx|φk i| ≤ 1 |hx|φk i|2 = 2n (37)
x∈{0,1}n x∈{0,1}n x∈{0,1}n

Thus we find
X √
|||φk i − |x0 i||2 ≥ 2(2n − 2n ) (38)
x0 ∈{0,1}n

Back to our original equation we find

h √ 1 √ 1 2
i
rk ≥ ((2 − 2)2n ) 2 + (2(2n − 2n )) 2 ≥ c2n (39)
p √ √
where we work for sufficiently large n and c is a constant less than c = ( 2 − 2 − 2)2 ≈ 0.42.
Now putting things together, we know that in order to succeed with probability greater than one half for all inputs,
we require that rk ≥ c2n . But we know that rk ≤ 4k 2 . This implies that we need
r
c2n
k≥ (40)
4
queries in order
√ for the measurements to so succeed. Thus we see that we obtain a bound which is like Grover’s
algorithm: Ω( 2n ) queries are needed quantum mechanically.

III. GROVER’S ALGORITHM FOR MULTIPLE NEEDLES IN A HAYSTACK

So far I have worked with a function which maps {0, 1}n → {0, 1} and has only one marked item. But more
generally we can design our Grovers algorithm to work with a function {0, 1, . . . , N − 1} → {0, 1} which is 0 on N − M
on this domain and is 1 on the rest of the M points of this domain. The goal then will be to find a single one of the
inputs x such that f (x) = 1. For now we will assume that we know M . Let S be the set of x such that f (x) = 1.
Then we can define the states
1 X
|x0 i = √ |xi (41)
M x∈S

and
1 X
|φ0 = √ |xi (42)
N − M x∈S
/

and again produce a Grover’s iterate which rotates on this space. The argument is nearly identical, so I will not
repeat it. The important point, though, is that the state will rotate by an angle satisfying
p
2 M (N − M )
sin θ = (43)
N
 6

on this basis (with identical

q expressions q for the rotation matrix.) We can again start in the equal superposition state
1
PN −1 N −M 0 M
|ψi = √N x=0 |xi = N |φ i + N |x0 i. To maximize that we will measure a state from |x0 i we need to rotate
through the angle
r
−1 M
kθ = arccos (44)
N
N
where k is the number of such iterations and we will assume M ≤ 2 for the moment. The number of iterations
needed is
r
1 −1 M
k = arccos (45)
θ N
Normally we could calculate this number and run for this number of iterations. To obtain a bound on the number of
π
iterations, it is enough to note that the arccos is at most π2 , so k ≤ 2θ . Now sin2 θ2 = 12 (1 − cos θ) = M
N . So since
θ θ
2 ≥ sin 2 (θ is positive) this implies that
r
M
θ≥2 (46)
N
Putting this together we find that the number of iterations is bounded by
r
π N
k≤ (47)
4 M
Now what happens in the case where M is greater than N/2? Well one way to deal with this case (assuming we
know M ) is simply to double the size of where we are searching and then to use the M ≤ N/2 algorithm. This can
be done with a quantum circuit which uses just a single extra qubit: just use this extra qubit as a control for the
unitary you are querying.