Quantum Computing (CST Part II)

Lecture 8: Quantum Search

Quantum computation is... a distinctively new way of harnessing

nature... It will be the first technology that allows useful tasks to be
performed in collaboration between parallel universes.
David Deutsch

1 / 20
What can we do with quantum parallelism?

Last time we saw how the Deutsch-Jozsa algorithm uses the fact that
when using a quantum computer an oracle can be queried by a
superposition of computational basis states (rather than by a single
state), thus using this quantum parallelism to reduce the complexity of
some query problems.

This prompts the question of what else we can use this quantum
parallelism for: and the simplest thing we may think of is to use a
quantum computer to search through a database looking for a single
significant entry.

2 / 20
Quantum search

In 1996 Indian-American computer

scientist Lov Grover published a quantum
search algorithm, which to this day
remains one of the most important
quantum algorithms.
The algorithm concerns searching an
unstructured database with N entries.
If we are searching for a unique marked
entry, then classically this would take a
maximum of N queries, and N/2 queries https://www.dotquantum.io
on average.
Lov Grover
Grover’s algorithm enables
√ the task to be
completed with only O( N ) queries.

3 / 20
Oracles revisited
Recall that a core component of the Deutsch-Jozsa algorithm is the
“oracle”, which can be thought of as something that can recognise a
correct answer when it sees one. Specifically, we think of an oracle as a
black box “marking” some input binary strings as 0 (i.e., f (x) = 0) and
some as 1 (i.e., f (x) = 1), of the form:

𝑥 𝑥
V
𝑎 𝑎⊕𝑓(𝑥)

In Grover’s algorithm, we consider a search oracle, V , which marks a

single element as 1, and all the others as 0.
The goal is to find the element marked 1, and we assume that there
is no algorithmic short-cut to find it, so classically we would have to
perform a brute-force search.

4 / 20
An example of an oracle

Say that 0010 is the unique “marked” binary string, then an appropriate
oracle would be:

X X
X X
V =
X X

Which is in the form of a general control gate.

5 / 20
The action of a search oracle on |−i

Consider an input binary string x and let the final qubit input be set
as |−i, (i.e., the input is |xi |−i)
The oracle transforms this to (−1)f (x) |xi |−i,
That is, if f (x) = 0 then nothing happens, whereas if f (x) = 1 then
the last qubit is changed from |−i = √12 (|0i − |1i) to
√1 (|1i − |0i) = − √1 (|0i − |1i) because of the modulo-2 addition.
2 2

𝑥 (−1)𝑓(𝑥) 𝑥
V
− −

6 / 20
Decomposing the uniform superposition

Initially we apply H ⊗n to the search register, that is we put the input in

the uniform superposition over all bitstrings of length n = log2 N (for
convenience we let the number of elements in the search space, N , be a
power of 2) to get:
1 X
|ψi = √ |xi
N x∈{0,1}n

Which we can write:

 
 
1 √ 1 X 
|ψi = √  N −1√ |xi + |zi
 
N  N − 1 x s.t. f (x)=0 
 
| {z }
|yi

where |zi is the single basis state |xi such that f (x) = 1.

7 / 20
Visualising the action of a search oracle on |−i
Now we consider the effect of the search oracle on this input, as can be
visualised in a two-dimensional space where (from previous slide):
|yi = √N1−1 x s.t.f (x)=0 |xi, i.e., a unit vector in the direction of
P

the uniform superposition of all unmarked strings.

|zi = |xi where f (x) = 1, i.e., the marked element.

𝜓
𝜃 𝑦
𝜃
V𝜓
√1
P
Where |ψi = N x |xi is the uniform superposition.

Applying the search oracle to |ψi does nothing to the component in the
|yi direction, but multiplies the component in the |zi direction by −1. So
the action of the search oracle can be seen as a reflection in the |yi axis.

8 / 20
The second step: reflecting about the original
superposition
As we have seen, the search oracle leads to a reflection in the |yi
axis.
But we need to rotate the superposition towards the |zi axis to
increase the probability of measuring the marked state (i.e., x s.t.
f (x) = 1) as is required.
So we follow up the oracle step with another reflection, about the
line of the original uniform superposition, which is given by
⊗n
W = (2 |ψi hψ| − I) where |ψi = |+i .

𝑧
W(V 𝜓 )
2𝜃
𝜓
𝜃 𝑦
𝜃
V𝜓

9 / 20
The operation of W
To see that the unitary W does indeed perform the reflection as claimed,
consider an arbitrary (real) vector |φi, decomposed into a component in
the direction of the uniform superposition (denoted |ψi as previously
defined), and a component perpendicular to the uniform superposition,
which we denote |ψ ⊥ i:

|φi = a |ψi + b |ψ ⊥ i

So it follows:

W |φi =(2 |ψi hψ| − I) |φi

=(2 |ψi hψ| − I)(a |ψi + b |ψ ⊥ i)
=2a |ψi hψ|ψi −2b |ψi hψ|ψ ⊥ i −a |ψi − b |ψ ⊥ i
| {z } | {z }
=1 =0
=2a |ψi − a |ψi − b |ψ ⊥ i
=a |ψi − b |ψ ⊥ i

That is, the desired reflection about the uniform superposition.

10 / 20
Implementing W with gates from a universal set
We still have to show that W can be implemented with gates from our
universal set. We start by decomposing W = 2 |ψi hψ| − I (where
⊗n
|ψi = |+i ):

H ⊗n W H ⊗n =2 |0n i h0n | − H ⊗n IH ⊗n
=2 |0n i h0n | − I
⊗n
because H is self-inverse, and H |+i = |0i (note |0n i = |0i ). We can
also use the fact that X |0i = |1i:

X ⊗n (H ⊗n W H ⊗n )X ⊗n =X ⊗n (2 |0n i h0n | − I)X ⊗n

=2 |1n i h1n | − I

which is the matrix:

     
0 0 ··· 0 1 0 ··· 0 1 0 ··· 0
0 0  0 1  0 1 
2 .  −  ..  = −  ..
     
 .. .. .. .. 
.  . .  . . 
0 1 0 1 0 −1

11 / 20
Implementing W with gates from a universal set (cont.)
We have that (−2 |1n i h1n | + I) is a n-qubit generalisation of the CZ
gate, which we denote Cn−1 Z:

=
Z H X H

As Z = HXH, we have that Cn−1 Z = (I ⊗ H)Cn−1 X(I ⊗ H), which

can be efficiently implemented using Toffoli gates with some extra
workspace qubits.
Putting this altogether we have:

W = −H ⊗n X ⊗n (I ⊗ H)Cn−1 X(I ⊗ H)X ⊗n H ⊗n

12 / 20
Iterating these two reflections
Say we have rotated to an angle kθ:

𝑧
𝜓′
𝑘𝜃 𝜓
𝜃 𝑦

Then the action of the matrices V and then W will be:

𝑧 𝑧 W(V 𝜓′ )
𝜓′
(𝑘 + 2)𝜃
𝑘𝜃 𝜓 𝜓
𝜃 𝜃 𝑦
𝑦
𝑘𝜃 𝑘𝜃
𝑘𝜃
V 𝜓′ V 𝜓′

Each occurrence of the Grover iterate, (W ⊗ I)V , leads to a 2θ rotation.

13 / 20
Grover’s algorithm

It follows that Grover’s algorithm consists of an iteration over V and W ,

which rotates the uniform superposition |ψi towards a superposition
consisting of only (or dominated by) the marked element, |zi:

0 H
𝑛 0 H
H
V W V W V W
0
−

14 / 20
How many iterations?
By simple trigonometry we can express θ:
𝑧
unit length
𝜓 1
length=
𝜃 𝑁
𝑦
 
So sin θ = √1N /1. If we are searching a large database then θ ≈ sin θ.
Each iteration rotates the superposition 2θ, and we need to rotate
( π2 − θ) in total, thus we require nit iterations, where:
π
− θ =nit × 2θ
2
π 1
=⇒ nit = −
4θ√ 2
π N
≈
4
√
so we require only O( N ) iterations of WV in Grover’s algorithm, as
opposed to checking all N elements in a classical brute-force search.
15 / 20
Other things to note
𝑧

≤𝜃

In general N may be such that the superposition never quite aligns

with |zi, however we can always rotate to within θ of |zi. Therefore
we will measure the marked answer with probability at least:
 2
2 2 1 N −1
(cos θ) = 1 − (sin θ) = 1 − √ =
N N

Rotating too far reduces the probability of getting the right answer.
Grover’s algorithm also works when there is more than one marked
answer (where the aim is to find any marked answer).
√
It has been shown that Θ N is a lower bound for search of an
unstructured database.
16 / 20
Oracles and complexity
Recall that an oracle can be thought of as something that can recognise
an answer.
In general an oracle can be any function that outputs a 0 or 1.
If we now think about NP-complete problems, by definition the
solution can be verified by a function which can be computed in
polynomial time... thus we can encode such a function as an oracle.

So it follows that, if we want to solve a NP-complete problem by a brute

force search through all possible solutions, then we can use the
polynomial verifying function as an oracle, and thus Grover’s algorithm
can yield a quadratic speed-up (note there is a subtlety here regarding
the fact that in general a NP-complete problem may have an unknown
number of solutions, so we may not know how many iterations of
Grover’s algorithm to perform to get the correct rotation, but this can be
taken care of using other techniques).
If we know that there are M solutions (M marked elements), then the
same analysis can be applied to the case in which |zi on Slide 8 is not a
single marked element,p but the equal superposition of all marked
elements, and yields π4 N/M iterations needed to find some solution.
17 / 20
There is more to quantum computing than superposition

So we can see that we cannot use quantum computing to obtain an

exponential speed-up in unstructured search problems. This is one
manifestation of the fact that quantum computing is more nuanced that
simply preparing a superposition state and thus evaluating each
possibility simultaneously.

In particular, we can only get an exponential quantum speed-up for

problems that have a specific structure where we must interfere the
superposed terms to get the answer.
This is the function of the final layer of Hadamard gates in
Deutsch-Jozsa, and we will see that the same feature is present in
many other quantum algorithms.

18 / 20
But the quadratic advantage is not to be sniffed at
Even though Grover search “only” yields a quadratic speed-up, this may
still be very useful in practise. We can understand why we can get a
quadratic advantage in the unstructured search problem in the following
way.

Each element in the database has a 1/N probability of being the

marked element. It follows that if we classically search through the
elements, each new element that we inspect increases the probability
of us having found the marked element by 1/N . Thus taking
1/(1/N ) = N iterations to find the marked state with certainty.
Quantumly, we put all elements in superposition and then “move the
superposition around”. Crucially, the (modulus of the) co-efficient of
a term in the superposition is the square rootpof its probability, and
so the co-efficient of the marked element is 1/N . As we move the
superposition such that the co-efficient of the marked element
increases
p in constant√increments we only take
O(1/( 1/N ) = O( N ) iterations to find the marked state.

19 / 20
Summary

Grover’s search algorithm enables a “marked” element of an

unstructured
√ database to be found with high probability with
O( N ) queries to the database, as opposed to O(N ) classically.
Grover’s algorithm is of the form of repeated oracle calls V and
reflections W .
The oracle V simply recognises the marked entry.
The reflection W can be efficiently implemented using gates from a
standard universal gate-set.

20 / 20