Grover search algorithm

Eva Borbely

Technological University Budapest, Hungary

PhD student

Introduction

A quantum algorithm is a set of instructions for a quantum computer, however, unlike

algorithms in classical computer science their results cannot be guaranteed. A quantum
system can undergo two types of operation, measurement and quantum state transformation,
operations themselves must be unitary (reversible). Most quantum algorithms involve a series
of quantum state transformations followed by a measurement. Currently very few quantum
algorithms are known and no general design methodology exists for their construction.

Almost all quantum algorithms can be expressed in a in a query (oracle) model where the
input is given by a black box which answers queries of a certain form.
In the query model, the input x1,K, x n is contained in a black box and can be accessed by

queries to the black box. In each query we give i to the black box, and the black box outputs
xi . The goal is to solve the problem with the minimum number of queries.

There are two ways to define the query box in the quantum model.
In the first case it has two inputs i and j, where i consisting of log 2 N bits and j consisting of

1 bit. If the input to the query box is a basis state i j , the output is i j ⊕ xi where

⊕ denotes addition modulo 2. If the input is a superposition : ∑ ai , j i j , the output is

i, j

∑a
i, j
i, j i j ⊕ xi .

In the second form of quantum query the black box has just one input i. If the input is a state

∑a
i
i i , the output is ∑ a (−1)
i
i
xi
i .

(This query model for example serves as a basis of Grover’s search algorithm. )
A large class of problems can be specified as search problems of the form: “find some x such
that statement f(x) is true.”
Such problems range from database search to sorting. A sorting problem can be viewed as a
search for a permutation for which the statement “the permutation x takes the initial state to
the desired sorted state” is true.

1
An unstructured search problem is one where nothing is known (or no assumption are used)
about the structure of the solution space and the statement f. For example, determining f ( x 0 )

provides no information about the possible value of f ( x1 ) for x 0 ≠ x1 .

A structured search problem is one where information about the search and statement f can be
exploited. For instance, searching an alphabetical list is a structured search problem and the
structure can be exploited to construct efficient algorithms.
Consider the problem of searching for a phone number in an unsorted directory with N
names.. This is an example of unstructured search problem. In order to find someone’s phone
number with a probability of ½, any classical algorithm will need to look at minimum of N/2
names. In the general case of an unstructured problem, randomly testing the truth of some
statement f ( xi ) one by one is the best that can be done classically.
For a search space of size N, the general unstructured search problem requires O(N)
evaluation of f.
On a quantum computer, however, Grover showed that the unstructured search problem can
be solved with bounded probability within O ( N ) evaluation of f.
The problem is to search trough a search space of N elements (for convenience we assume
N = 2 n ) and the search problem has exactly M solutions with 1 ≤ M ≤ N.
In our case the search problem can be represented by a function f, wich takes as input register
x, x =0,1,…, N-1. By definition f ( x ) = 1 if x is a solution to the search problem, and
f ( x ) = 0 if x is not a solution to the search problem.
Classically we need N queries to solve this problem. If we are using probabilistic classical
N
computer, we can reduce it to expected steps.
2
Grover showed that there is a quantum algorithm that solves this problem with
O ( N ) queries.
The simplest case is if M=1, namely there exist exactly one x such that f ( x ) = 1 . In this case
we consider the following problem:
• Label the records of the database with the integers 0, 1, 2, . . . , N -1 ,
• denote the unknown marked record by ω
• let f an n bit binary function f : {0,1} → {0,1}
n

⎧1, x = ω
f ( x) = ⎨
⎩0, otherwise

2
Search Problem for an Unstructured Database. Find the record ω with the minimum amount
of computational work, i.e., with the minimum number of queries.
To solve the Grover’s search problem suppose we are supplied with a quantum oracle with
the ability to recognize solution to the search problem.
The oracle is a unitary operator U, defined by its action on the computational basis:
U : x q → x q ⊕ f ( x)

where x is the input register, q is the oracle qubit, and ⊕ denotes addition modulo 2.

The oracle qubit q is a single qubit which is flipped if f ( x ) = 1 , and is unchanged

otherwise. We can check whether x is a solution to our search problem by preparing x 0 ,

applying the oracle and checking to see if the oracle qubit has been flipped to 1 .

1
It is useful to choose the state of the single – qubit register to be: ( 0 − 1 ) . We achieve
2
this state simply applying the Hadamard transform to the 1 quantum state:

⎧ 1
0 ⎫⎪ H ⎪⎪ (0 +1)
1 ⎡1 1 ⎤ 2
H≡ ⎢ ⎥, ⎬ ⎯⎯→ ⎨
2 ⎣1 − 1⎦ 1
1 ⎪⎭ ⎪
⎪⎩
(0 −1)
2
Now we apply the oracle to the new state:
⎛ 0 −1 ⎞ ⎛ 0 −1 ⎞
U x ⎜⎜ ⎟ → (− 1) f ( x ) x ⎜ ⎟.
2 ⎟ ⎜ 2 ⎟
⎝ ⎠ ⎝ ⎠
For instance, if x is a solution to the search problem then the final state will be:
⎛ 0 −1 ⎞
− x ⎜⎜ ⎟.
⎟
⎝ 2 ⎠
It is obvious, that the state of the oracle qubit is not changed, so we may ignore it, and obtain:
x ⎯⎯→
U
(− 1) f (x )
x .

It is easy to see, that the oracle transformation U is equivalent with the following
transformation: U = I − 2 ω ω , where ω is the only solution of the search problem, and I

is the identity matrix.

If x = ω , then: U ω = I ω − 2 ω ω ω = I ω − 2 ω = − ω .

3
If x ≠ ω then we have: U x = I x − 2 ω ω x = I x = I x since ω and x are

orthogonal to each other if ω ≠ x .

Thus the oracle U flips the sign of x if x = ω but operates trivially on all x ≠ ω .

More precisely, when U operates on some vector x in Hilbert space H 2 ( N = 2 n ) , reflects

n

it about the hyperplane orthogonal to ω . We know that the reflection is performed for some

basis state ω , but nothing is known about the string ω itself. Our task is to determine ω. To

achieve our aim, we are using the so – called Grover iteration:

2 n −1
1
1. Create a perfect random state Ψ = ∑x i by application of the Hadamard
2n i =0

⊗n
transformation on the state 0 .

1
We know about ω that it is a base state, which means that Ψ ω = . Measuring
2n
the state Ψ by projection onto its base {x } would return the state ω only with

1
probability .
N
2. Combine the unknown reflection U with some known reflection V = 2 Ψ Ψ − I . It

flips the sign of x if it is orthogonal to Ψ and preserves the sign of x , if

x = Ψ :

— V x = 2 Ψ Ψ x − I x = − x because Ψ x = 0

— V Ψ = 2 Ψ Ψ Ψ − I Ψ = Ψ , since Ψ Ψ = I .

Acting on some arbitrary vector, V preserves the component along Ψ but flips all

components in the hyperplane orthogonal to Ψ .

3. Apply the operator G=V*U to some vector x with the following effect:

— the vector Ψ and ω span a plane in H ⊗ N with a vector ω ⊥ that is orthogonal

to ω in that plane;

— any vectors x in that plane is by U flipped about ω ⊥ and by V flipped about

Ψ .

4
To understand what this means, consider the geometry in a two-dimensional Hilbert space:

ω⊥

x
x'

θ =ϕ +δ Ψ

ϕ ϕ
δ x"
δ

— the angle between Ψ and ω is given as:

1 1 ⎛π ⎞
Ψ ω = = = cos⎜ − θ ⎟ = sin θ
N 2 ⎝2
n
⎠

— a vector x is by U flipped about ω⊥ and thereby changed its angle by 2ϕ

— the vector U x = x ' is by V flipped about Ψ , thus changing its angle by 2δ

— the total change of angle effected by G=V*U is thus 2ϕ + 2δ = 2θ, which is the
effect of one Grover iteration.
Remark:
He Grover iteration may be seen to be a consequence of the following elementary theorem of
2-dimensional real Euclidian geometry.
Theorem: Let L and M be two mirror lines in the Euclidian plan R2 intersecting at a point O
and let α be the angle in the plane from L to M. Then the operation of reflection in L followed
by reflection in M is just a rotation by angle 2α about the point O.

O α

4. Repeat the Grover iteration until the possibility the input item in the data base
approaches the value 1.

5
We assume that we need some k iteration to bring Ψ close to ω ( or to turn it away from

π
ω ⊥ by an angle of .
2
π
After k iteration we thus get a rotation by θ + 2kθ = .
2
1
Since sin θ ≅ θ = for large N, we iterate until:
N

(2k + 1)θ ≅ π ⎛ π 1⎞
, ⇒ k = round ⎜ − ⎟
2 ⎝ 4θ 2 ⎠
π
or k ≅ N.
4
π
Only N iteration are required to find ω with high probability.
4
For example assuming that the data base contains just 4 items. A classical sequential search
would requires 2 steps to find a particular item. A quantum-mechanical search for an item
1 1 1
x would set out x ω = = = sin θ which means that θ = sin −1 = 30 o . A rotation
4 2 2

by 2θ = 60 o brings x into a 90 o angle with ω ⊥ , or in line with ω .

Multiple solutions

Suppose that the search problem has exactly M solutions, with 1 ≤ M ≤ N , N = 2 n and M is
known. In this case the oracle introduces a reflection in the hyperplane orthogonal to the
1 M
1
vector β =
M
∑ω i , or in other manner β =
M
∑x , the equal weighted
i =1 x = f −1 (1)

superposition of the marked computational basis states.

N −1
1
The original state Ψ =
N
∑x i =1
can be rewritten as :

N − M ⎛⎜ 1 ⎞ M ⎛⎜ 1 ⎞
Ψ =
N ⎜⎝ N − M
∑ x ⎟⎟ + N ⎜⎝ M
∑ x ⎟⎟ ,
x = f −1 (0 ) ⎠ x = f −1 (1) ⎠
or

N −M M
Ψ = α + β ,
N N
1 1
where α ≡
N −M
∑x, β ≡
M
∑x .
x = f −1 ( 0 ) x = f −1 (1)

6
Using the simplest notation, Ψ = cosθ α + sin θ β .

Geometrical representation:
β

G Ψ

2θ Ψ
θ β⊥
θ
U Ψ

The effect of G = V*U is the following:

— the oracle U performs a reflection about the vector α which is orthogonal to β :

U (cosθ α + sin θ β ) = cosθ α − sin θ β

— the vector cosθ α − sin θ β is by V = 2 Ψ Ψ − I flipped about Ψ

— the product of two reflection is a rotation and after k iteration the state:
G k Ψ = cos(2k + 1)θ α + sin (2k + 1)θ β

M
For large N, when M << N we have θ ≈ sin θ ≈ and:
N
(2k + 1)θ = π ,
2

M π ⎛π N 1⎞
(2k + 1) = ⇒ k = round ⎜⎜ − ⎟.
N 2 ⎝4 M 2 ⎟⎠

π N
So the state is close to β after a number of iteration k ≈ with probability:
4 M

prob = sin 2 (2k + 1)θ .

Reverting to the previous example; the probability to find one marked item from 4 is
prob = sin 2 (2k + 1)θ = sin 2 3 ⋅ θ = sin 2 3 ⋅ 30 o = 1 .

7
 (
Quantum search algorithm in detail: M = 1, N = 2 n )
Input:
x1 = {0,1}, x 2 = {0,1}, L , x N = {0,1} , f : {0,1} → {0,1} ; f ( x ) = 0 for all 0 ≤ x ≤ N
N
—

except ω = xi , for which f ( xi ) = 1

⎡ 0 − 1 ⎤
— n qubits in the state 0 and 1 qubit, the oracle qubit in state: ⎢ ⎥ .
⎣ 2 ⎦
Procedure:

⊗n ⎡0 −1⎤
1. Initial sate: 0 ⎢ ⎥
⎣ 2 ⎦

1 N −1 ⎡ 0 − 1 ⎤
2. Apply the H ⊗n
to the first n qubits: ⇒
N
∑ x ⎢
2 ⎦
⎥
x=0 ⎣
π
3. Apply the Grover iteration k ≈ N times
4
N −1 ⎡0 −1⎤ ⎡0 −1⎤
⇒ [(2 Ψ Ψ − I )(I − 2 ω ω )]
k 1
∑x⎢ ⎥≈ ω ⎢ ⎥
N x =0 ⎣ 2 ⎦ ⎣ 2 ⎦

4. Measure the first n qubits ⇒ ω .

8
Inversion about the average

There is an alternative way to visualize the Grover iteration that is sometimes useful, as an
“inversion about the average”.
N N
The unitary transformation Dn : ∑ ai xi → ∑ (2 A − ai ) xi , where A is the average of
i =0 i =0

{a i 0 < i < N } can be performed by the matrix:

⎡2 2 2 ⎤
⎢ N −1 N
L
N ⎥
⎢ 2 2 2 ⎥
D=⎢ N −1 L ⎥,
⎢ N N ⎥
⎢ M M M M ⎥
⎢ 2 2 2
L − 1⎥
⎣⎢ N N N ⎦⎥
⎧2
⎪⎪ N , if i ≠ j
or simply: Di , j =⎨
⎪ 2 − 1, if i = j
⎩⎪ N
D has two properties:
1. it is unitary
2. it can be seen as “inversion about average”.
Proof:
1. For N = 2 n , operator D can be decomposed and rewritten as:

⎡1 0 L 0 ⎤ ⎡ ⎡2 0 L 0⎤ ⎤
⎢0 − 1 L 0 ⎥ ⎢⎢ ⎥
⊗n ⎢ ⎥ ⊗n ⊗ n ⎢ ⎢0 0 L 0⎥⎥ ⎥ ⊗n
D=H H =H −I H =
⎢M M M M⎥ ⎢⎢ M M M M⎥ ⎥
⎢ ⎥ ⎢⎢ ⎥ ⎥
⎣0 0 L − 1⎦ ⎣⎢ ⎣0 0 L 0⎦ ⎦⎥

⎡ 2 2 2 ⎤
⎡2 0 L 0⎤
⎢ L
⎢0 N ⎥⎥
0 L 0⎥⎥ ⊗n ⎢ N N
= H ⊗n ⎢ H − I = H ⊗n ⎢ 0 0 L 0 ⎥−I =
⎢M M M M⎥ ⎢
⎢ ⎥ M M M M ⎥
⎣0 0 L 0⎦ ⎢ ⎥
⎣ 0 0 L 0 ⎦

9
 ⎡ 2 2 2 ⎤ ⎡ 2 2 2 ⎤
⎢ N N
L
N ⎥⎥ ⎢ N −1 N
L
N ⎥⎥
⎢ ⎢
⎢ 2 2 2 ⎥ ⎢ 2 2 2 ⎥
L −1 L
=⎢ N N N⎥ − I = ⎢ N N N ⎥
⎢ M M M M ⎥ ⎢ M M M M ⎥
⎢ 2 2 2 ⎥ ⎢ 2 2 2 ⎥
⎢ L ⎥ ⎢ L − 1⎥
⎣ N N N⎦ ⎣ N N N ⎦
Observe that D can be expressed as the product of three unitary matrices: two Hadamard
matrices separated by a conditional phase shift matrix. Therefore D is also unitary.
N −1
2. Let Ψ = ∑ ai i be the state before D. Then, the state after D is:
i =0

N −1
⎛2 ⎞ 2
Ψ ' = ∑ a i i , where ai' = ⎜ − 1⎟ai + ∑i ≠ j a j . We can rewrite this as
'

i =0 ⎝N ⎠ N
N −1 N −1 N −1
2 2 1
ai' = −ai + ∑ a j and ai' + ai = ∑ a j . Let A = ∑ a j be the average of
j =0 N j =0 N j =0 N

'
amplitudes ai . Then, we have a i' + a i = 2 A and, if ai = A + ∆ , then ai = A − ∆ . Thus,

the effect of the D operator is that every amplitude ai is replaced by its reflection

against the average of all ai .

Geometrical representation:

Amplitudes after the first

Amplitudes in initial state oracle trnsformation: U
(fig.1.) (fig.2.)

Amplitudes after D
(fig.3.)
10
As we can see in fig. 2., after the first oracle transformation U = 2 ω ω − I , the amplitude

1 1
of ω = xi = 1 is − , and all the other amplitudes are . The average is:
N N
1 1 2
(N − 1) ⋅ −
N
−
N N N N 1 2 1
= = − ≈ for large N. Therefore, after
N N N N N N
3
applying D, the amplitude of i with xi = 1 becomes almost and the amplitudes of all
N
1
other basis states j slightly less than (fig.3.).
N
The next query (oracle transformation) makes the amplitude of i with xi = 1 approximately

1 3
(N − 1) ⋅ −
3 N N = 1 − 4 ≈ 1 , which
− . The average of all amplitudes is:
N N N N N N
1
is slightly less than , and reflecting against it make the amplitude i with xi = 1 almost
N
5
.
N
π
A precise calculation made by Grover shows that after N steps the amplitude of i with
4
xi = 1 is 1- o(1). Therefore, the measurement gives the correct answer with probability 1 –
o(1).

Example for N = 4 (matrix representation)

In this case we need n=2 qubits and another one with 1 qubit, the oracle qubit. We need just at
⎛π ⎞ ⎛π ⎞
k = round ⎜ N ⎟ = round ⎜ ⎟ = 1 oracle query to resolve the search problem.
⎝4 ⎠ ⎝2⎠
The initial state is Ψ0 = 00 , and after applying the Hadamard gates we get:

⎛1⎞
⊗2 ⊗2 ⎜ ⎟
⎡ 1 ⎛1 1 ⎞⎛ 1 ⎞⎤ ⎡ 1 ⎛1⎞⎤ 1 ⎛1⎞ ⎛1⎞ 1 ⎜1⎟
Ψ = H ⊗ 2 00 = (H 0 )⊗2
=⎢ ⎜⎜ ⎟⎟⎜⎜ ⎟⎟⎥ =⎢ ⎜⎜ ⎟⎟⎥ = ⎜⎜ ⎟⎟ ⊗ ⎜⎜ ⎟⎟ = ⎜ ⎟
⎣ 2 ⎝1 − 1⎠⎝ 0 ⎠⎦ ⎣ 2 ⎝1⎠⎦ 2 ⎝1⎠ ⎝1⎠ 2 1
⎜ ⎟
⎜1⎟
⎝ ⎠

11
 ⎛1⎞
⎜ ⎟
1 ⎜1⎟
Ψ = ⎜ ⎟
2 1
⎜ ⎟
⎜1⎟
⎝ ⎠
Suppose that f (3) = 1 and f (i ) = 0 for i ≠ 3 .
Than the oracle transformation is the identity matrix with the 3th element of the diagonal equal
to –1.
⎛1 0 0 0⎞
⎜ ⎟
⎜0 1 0 0⎟
U =⎜
0 0 1 0⎟
⎜ ⎟
⎜0 0 0 − 1⎟⎠
⎝
⎛1⎞
⎜ ⎟
1 ⎜1⎟
In the next step we apply the oracle transformation U to the state Ψ = ⎜ ⎟ :
2 1
⎜ ⎟
⎜1⎟
⎝ ⎠
⎛1 0 0 0 ⎞ ⎛1⎞ ⎛1⎞
⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎜0 1 0 0 ⎟ 1 ⎜1⎟ 1 ⎜ 1 ⎟
Ψ1 = U Ψ = ⎜ = .
0 0 1 0 ⎟ 2 ⎜1⎟ 2 ⎜ 1 ⎟
⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎜0 0 0 − 1⎟⎠ ⎜⎝1⎟⎠ ⎜ − 1⎟
⎝ ⎝ ⎠
We have seen that the V = 2 Ψ Ψ − I operator is equivalent with the so-called “diffusion

⎡ 1 1 1 1 ⎤
⎢− 2 2 2 2 ⎥
⎧2 ⎢ 1 1 1 1 ⎥
⎪⎪ N − 1 if i = j ⎢ − ⎥
operator” D = ⎨ or in this case: D = ⎢ 2 2 2 2 ⎥
⎪2 ⎢ 1 1
−
1 1 ⎥
if i ≠ j ⎢ 2
⎪⎩ N 2 2 2 ⎥
⎢ 1 1 1 1⎥
⎢ − ⎥
⎣ 2 2 2 2⎦

⎡ 1 1 1 1 ⎤
⎢− 2 2 2 2 ⎥ 1
⎢ 1 1 1 1 ⎥ ⎡ ⎤ ⎡ 0 ⎤ ⎡0 ⎤
⎢ − ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥
Ψ 2 = D Ψ1 = ⎢ 2 2 2 2 ⎥ ⋅ ⎢ 1 ⎥ = 1 ⎢ 0 ⎥ = ⎢0 ⎥ .
⎢ 1 1
−
1 1 ⎥ ⎢ 1 ⎥ 2 ⎢ 0 ⎥ ⎢0 ⎥
⎢ 2 2 2 2 ⎥ ⎢− 1⎥ ⎢ ⎥ ⎢ ⎥
⎢ 1 1 1 1 ⎥ ⎣ ⎦ ⎣ 2 ⎦ ⎣1 ⎦
⎢ − ⎥
⎣ 2 2 2 2⎦
According to the Grover iteration, the amplitude of the marked state increased by ½, while
the amplitude of other states decreased to zero.

12
Now if we measure the final state Ψ2 , then we obtain the correct answer with unit

probability.

Example for N = 8

If N = 2 3 ⇒ there are 3 qubits in the first register and 1 qubit in the second register, which is
the oracle qubit. For N = 8, the operator G will be applied k = 2 times as follows from
⎛π ⎞
k = round ⎜ N ⎟ = round (2,2214 ) .
⎝4 ⎠
The initial state is Ψ0 = 000 .
7
1
After applying Hadamard gates, we get: Ψ = H ⊗3 000 = (H 0 ) ∑i
⊗3
= .
8 i =0

Suppose that we are searching for the element with index 5. Since 5 = 101 , after the U

oracle transformation we obtain: U 101 = − 101 , and U i = i , if i ≠ 5 .

7
1 1
Define s = ∑i = ( 000 + 001 + 010 + 011 + 100 + 110 + 111 ) .
7i =0 7
i ≠5

7 1 7 1
Then Ψ = s + 101 = 101 .s +
8 8 2 2 2 2
7
The value of θ is: θ = 2. arccos ≅ 41,4 o .
8
1
The next step is: Ψ1 = U Ψ = ( 000 + 001 + 010 + 011 + 100 − 101 + 110 + 111 )
8
1
or using the state s we can write Ψ1 as: Ψ1 = Ψ − 101 .
2
In the next step we have to apply the 2 Ψ Ψ − I operator:

⎛ 1 ⎞
Ψ2 = (2 Ψ Ψ − I ) Ψ1 = (2 Ψ Ψ − I )⎜ Ψ − 101 ⎟ =
⎝ 2 ⎠
2 1 2 1 1
=2Ψ − Ψ Ψ 101 − Ψ + 101 = 2 Ψ − ⋅ Ψ − Ψ + 101 =
2 2 2 2 2 2
1 1
= Ψ + 101
2 2

7 1
or using Ψ = s + 101 ,
2 2 2 2

13
 1⎛ 7 1 ⎞ 1 7 5
Ψ2 = ⎜ s + 101 ⎟⎟ + 101 = s + 101 .
⎜
2⎝2 2 2 2 2 4 2 4 2
⎠

Let us confirm that the angle between Ψ and Ψ 2 is θ :

1 1 1 1 1 3
cosθ = Ψ Ψ2 = Ψ Ψ + Ψ 101 = + ⋅ =
2 2 2 2 2 2 4
3
θ = cos −1 ≅ 41,4 o
4
which correspond with the previous result.
The second and last application of Grover iteration is similar:
7 5 7 1
Ψ3 is given by: Ψ3 = s − 101 or using the Ψ = s + 101
4 2 4 2 8 8
1 3
expression Ψ3 = Ψ − 101 because.
2 2 2

1 3 7 ⎛ 1 3 ⎞ 7 5
Ψ − 101 = s +⎜ − ⎟ 101 = s − 101 = Ψ3 .
2 2 2 4 2 ⎝4 2 2 2⎠ 4 2 4 2
The last step is:
⎛1 3 ⎞
Ψ4 = (2 Ψ Ψ − I ) Ψ3 = (2 Ψ Ψ − I )⎜ Ψ − 101 ⎟ =
⎝2 2 2 ⎠
1 3 1 3
= 2⋅ Ψ Ψ Ψ − 2⋅ Ψ Ψ 101 − Ψ + 101 =
2 2 2 2 2 2
3 1 1 3 1 3
= Ψ − Ψ ⋅ − Ψ + 101 = − Ψ + 101
2 2 2 2 2 2 2 4 2 2

7 1
Using the Ψ = s + 101 expression:
2 2 2 2

7 1 3 7 11
Ψ4 = Ψ = − s − 101 + 101 = − s + 101 .
8 2 8 2 2 2 8 2 8 2
A measurement of the state Ψ4 in the computational basis will project it into state 101
2
11 121
with probability: p = ≅ ≅ 0,9453 .
8 2 128
The basic idea of Grover iteration became obvious through this example: it increases the
amplitude of the state that carry the desired information and decreases the amplitude of an
other state i .

14
In what follows we will show how important is to know the number of repetition of Grover
iteration.
Let us suppose that, we don’t know the value of k, and continue to perform further Grover
iterations:
7 11 7 1
Ψ5 = − s − 101 or using Ψ = s + 101 :
8 2 8 2 2 2 2 2
1 5
Ψ5 = − Ψ − 101 .
4 4 2
⎛ 1 5 ⎞
Ψ6 = (2 Ψ Ψ − I ) Ψ5 = (2 Ψ Ψ − I )⎜ − Ψ − 101 ⎟ =
⎝ 4 4 2 ⎠
7 5 7⎛ 7 1 ⎞ 5
=− Ψ + 101 = − ⎜⎜ s + 101 ⎟⎟ + 101 ⇒
8 4 2 8⎝2 2 2 2 ⎠ 4 2
7 7 13
⇒ Ψ6 = − s + 101
16 2 16 2

If we measure now the state Ψ6 , we et the result 101 with probability:

2
13 169
p= = ≅ 0,33 , and some other state with probability:
16 2 512
2
7 7 343
p = −
'
= ≅ 0,67 .
16 2 512

⎛π ⎞
So, if we continue the Grover iteration, after k = round ⎜ N ⎟ steps the probability of
⎝4 ⎠
finding the marked state begins to decline while the possibility of error increases better and
better.

Implementation

In the following we can reed the Grover’s opinion about the implementation possibility of his
algorithm:
“This algorithm is likely to be simpler to implement as compared to other quantum
mechanical algorithms for the following reasons:
(i) The only operations required are, first, the Walsh-Hadamard transform, and second,
the conditional phase shift operation both of which are relatively easy as compared to
operations required for other quantum mechanical algorithms

15
 (ii) Quantum mechanical algorithms based on the Walsh-Hadamard transform are likely
to be much simpler to implement than those based on the “large scale Fourier transform”.
(iii) The conditional phase shift would be much easier to implement if the algorithm was
used in the mode where the function at each point was computed rather than retrieved form
memory. This would eliminate the storage requirements in quantum memory.
(iv) In case the elements had to be retrieved from a table (instead of being computed as
discussed in (iii)), in principle it should be possible to store the data in classical memory and
only the sampling system need be quantum mechanical. This is because only the system under
consideration needs to undergo quantum mechanical interference, not the bits in the memory.”

Experimental realization using optical quantum computation technology

We restrict our attention to the case where the number of elements in the search space is
N = 4.

0 H Z H H X „a”

Oracle
0 H „b”

1 H H „1”

Fig. 1.

Fig. 1. is a circuit diagram for the four-element Grover algorithm. The top two qubits are the
data qubits, initialised in state | 0 0 , while the bottom qubit is the oracle qubit, initialised in

state 1 .The boxes labelled H and Z represent the one-qubit Hadamard and Pauli Z gates,

respectively. The CNOT is denoted by the usual symbol, while the grey half-circles represent
one-qubit measurements in the computational basis, whose output appears on the classical
output wires (double lines). The final X gate represents the classical NOT required to put the
output into the correct form. The measurement always gives “1” on the oracle qubit, while the
data qubits give “a” and “b”. It is straightforward to show that, in principle, ab is the state
marked by the oracle.
It can be verified directly that this circuit, using only one oracle call, gives the correct answer
with probability 1, compared to the average of 2.25 oracle calls that must be made with a

16
classical circuit. For example, if the solution is 11, then the output of the circuit is a = 1and b
= 1.

Implementing the oracle

An oracle is a quantum circuit that recognizes solutions to a given problem. For example,
suppose we wish to solve a version of the travelling salesman problem, where the goal is to
find a route visiting a given collection of cities that is shorter than some specified length L
.Although it is in general hard to find such a route, it is easy to recognize whether a proposed
route solves the problem: simply add up the total distance the salesman would travel on the
proposed route, and compare it to L .Specifically, an oracle is a circuit that, given an input
consisting of a potential solution to a problem, flips the sign of an ancilla qubit if and only if
the input is a solution to the problem. Since the only action of the oracle is to recognize
solutions, its internal structure is unimportant in a test of the algorithm itself. Thus, for our
purposes, the choice of oracle is arbitrary, and may be chosen to be as simple as possible.
Although the internal workings of the oracle are unimportant for the purposes of testing the
algorithm, the complexity of implementing some oracle must be included to characterize the
difficulty of performing the experiment. A simple implementation of an oracle marking one of
four states is a Toffoli gate, with the control qubits negated where necessary to specify any of
the states 00, 01, 10, or 11 (see the Fig. 2a. for the example where the marked state is 11).
If the marked state is 11, the action of the oracle on the three qubits is to take the state
( 00 + 01 + 10 + 11 )( 0 − 1 ) to ( 00 + 01 + 10 )( 0 − 1 ) + 11 ( 1 − 0 ) (omitting the

normalization). Thus the oracle simply has the effect of flipping the sign of the marked state.
The ancilla is not used again, so it can be discarded at this point.
Toffoli gates are difficult to implement in LOQC because there is no known way to
implement one without using several CNOT gate. However, for our purposes, a full Toffoli
gate is not required because the ancilla qubit plays such a limited role.

0 H

0
H

1 H H

Fig. 2a.

17
 H
0
X x1 ⊕1
0
H Z
X x 2 ⊕1

Fig. 2b.

FIG. 2a: The circuit shows the beginning of the Grover circuit with an example oracle (inside
the dashed box) marking the item 11. We have implemented the oracle using a variant of the
Toffoli gate, where the state of the third qubit is flipped when the first two qubits are in the
state 11 , as indicated by the closed circles on the control qubits. We have moved the

measurement on the third qubit forward since it plays no further role in the algorithm.
However, this circuit is in fact equivalent to the simplification in the Fig 2b., where the
Toffoli has been replaced by a controlled-Z operation followed by the X gates
A simplified circuit to implement the four-element Grover algorithm is given in Fig. 3.

H
0
X x1 ⊕1 Z H H X „a”

H Z
0
X x 2 ⊕1 „b”

Fig. 3.
FIG. 3: Inserting the simplified oracle of Fig. 2b. into the circuit of Fig. 1 gives this circuit.
Note that the marked state is specified inside the oracle (the dashed box) by the values of
x1 and x2 used to determine whether or not the X gates are applied Under ideal circumstances,
the output of the circuit is a = x1 and b = x2 .
We are verifying directly that the circuit in fig 3. gives the correct answer to the search
problem using only one oracle call.
In our example, if the solution is 11, then the output of the circuit is a = 1 and b = 1 .
1
— Initial state is: (H 0 ) ( 00 + 01 + 10 + 11 ) ; which is the oracle input
⊗2
=
2
— In this special case the oracle makes just one transformation- the Controlled –Z -,in
order to invert the sign of the marked state because x1 = x2 = 1 , and

X x1 ⊕1 = X x 2 ⊕1 = I , where I is the identity:

18
 1
( 00 + 01 + 10 + 11 ) ⎯ ⎯⎯ →
C −Z 1
( 00 + 01 + 10 − 11 )
2 2
— The following two transformations: Z and H, are performed just on the first qubit
( x1 ):
1
( 00 + 01 + 10 − 11 ) ⎯Z⎯→⎯x1 → 1 ( 00 + 01 − 10 + 11 ) ⎯⎯ H → x1
⎯→
2 2
1
(( 0 + 1 )( 0 + 1 ) + ( 0 − 1 )( 1 − 0 )) = 1 ( 01 + 10 )
2 2 2
— In the next step the C-NOT gate operates on both qubit as follows: it changes the
second bit if the first bit is 1 and leaves this bit unchanged otherwise:
1 1
( 01 + 10 ) ⎯⎯⎯C − NOT
⎯→ ( 01 + 11 )
2 2
— Repeat the H transformation on the first qubit:
1 1 ⎛⎛ 1 ⎞ ⎛ 1 ⎞ ⎞
( 01 + 11 ) ⎯⎯⎯→
H → x1
⎜⎜ ⎜ 0 + 1 ⎟1 +⎜ 0 − 1 ⎟1 ⎟⎟ =
2 2 ⎝⎝ 2 ⎠ ⎝ 2 ⎠ ⎠
1
= ( 01 + 11 + 01 − 11 ) = 01
2
— We measure the qubits in the computational basis separately, and perform an X
(classical NOT) transformation on the first bit:
⎧0 ⎯⎯→
X
1 =" a"
01 ⎯⎯⎯⎯
⎯→⎨
Measurement
, the output is: ab=11
⎩1 → 1 =" b"
Notations
1 ⎡1 1 ⎤
— H is the Hadamard gate defined as: H = ⎢ ⎥,
2 ⎣1 − 1⎦
1
H: 0 → (0 + 1 )
2
more precisely :
1
1 → (0 − 1 )
2
— X is the classical NOT gate, or Pauli X transformation defined as:

⎛ 0 1⎞ X: 0 → 0
X = ⎜⎜ ⎟⎟ , more precisely:
⎝ 1 0⎠ 1 → 1

— Z is the phase shift gate, or Pauli Z transformation defined as:

⎛1 0 ⎞ Z: 0 → 0
Z = ⎜⎜ ⎟⎟ or more precisely:
⎝ 0 − 1⎠ 1 → −1

19
 — CNOT is the controlled NOT gate, which applies a NOT on the second bit, called
the target bit if the first control bit is 1:

⎛1 0 0 0⎞ CNOT : 00 → 00
⎜ ⎟
⎜0 1 0 0⎟ 01 → 01
CNOT = ⎜ or:
0 0 0 1⎟ 10 → 11
⎜ ⎟
⎜0 0 1 0 ⎟⎠
⎝ 11 → 10

— C-Z is the controlled Z gate, which applies the Z transformation on the second bit, t
if the first control bit is 1:

⎛1 0 0 0⎞ C−Z : 00 → 00
⎜ ⎟
⎜0 1 0 0⎟ 01 → 01
Matrix representation: C − Z = ⎜ , or:
0 0 1 0⎟ 10 → 10
⎜ ⎟
⎜0 0 0 − 1⎟⎠
⎝ 11 → − 11

— Toffoli gate or controlled–controlled–NOT, which negates the last bit of three if and
⎛ I 4x4 M 0 ⎞
⎜ ⎟
only if the first two are both 1. matrix representation: ⎜ L L L ⎟
⎜ 0 M CNOT ⎟⎠
⎝

References

1. M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Informa-
tion, Cambridge University Press, Cambridge (2000).
2. J. Preskill, Quantum Information and Computation, Lecture Notes, California
Institute of Technology (1998).
3. G. Brassard, P. Høyer, and A. Tapp, Quantum Counting, quant-ph/9805082.
4. .Grover, Lov K., A framework for fast quantum mechanical algorithms, quant-
ph/9711043.
5. Grover, L., Quantum mechanics helps in searching for a needle in a haystack (quant-
ph/9605043)
6. Grover, L., Phys. Rev. Lett. 78, (1997), pp 325 - 328.
7. Gruska, Jozef, “Quantum Computing,” McGraw-Hill, (1999)
8. Jozsa, Richard, Searching in Grover’s Algorithm, quant-ph/9901021.
9. Andris Ambainis. Quantum query algorithms and lower bounds
10. P. G. Kwiat, J. R. Mitchell, P. D. D. Schwindt, and A. G. White, Grover’s search
algorithm: An optical approach, quant- ph/ 9905086
11. Christof Zalka, Could Grover’s quantum algorithm help in

20
 searching an actual database? quant- ph/ 9901068
12. Ofer Biham, Daniel Shapira and Yishai Shimoni, Analysis of Grover’s quantum
search algorithm as a dynamical system, quant- ph/ 0307141
13. Jennifer L. Dodd, Timothy C. Ralph and G. J. Milburn, Grover’s algorithm in optical
quantum computation
14. J´er´emie Roland and Nicolas J. Cerf, Quantum circuit implementation of the
Hamiltonian versions of Grover’s algorithm, quant- ph/ 0302138
15. Manoj K. Samal and Partha Ghose, Grover’s search algorithm and the quantum
measurement problem, quant- ph/ 0202176
16. Daniel Braun, Quantum Chaos and Quantum Algorithms, quant- ph/ 0110037
17. Goong Chen and Shunhua Sun , Generalization of Grover’s Algorithm to Multiobject
Search in Quantum Computing, General Unitary Transformati

21