3Some quantum algorithms

III Quantum Computation

3.5 Amplitude amplification

In fact, the techniques from Grover’s algorithm is completely general. Let

G

be

any subspace (“good” subspace) of the state space

H

, and

G

⊥

be its orthogonal

complement (“bad” subspace). Then

H = G ⊕ G

⊥

.

Given any normalized vector

|ψi ∈ H

, we have a unique decomposition with

real, non-negative coefficients

|ψi = sin θ |ψ

g

i + cos θ |ψ

b

i

such that

|ψ

g

i ∈ G, |ψ

b

i ∈ G

⊥

are normalized.

We define the reflections

I

|ψi

= I − 2 |ψihψ|, I

g

= I − 2P,

where P is the projection onto G given by

P =

X

b

|bihb|

for any orthonormal basis {|bi} of G. This P satisfies

P |ψi =

(

|ψi |ψi ∈ G

0 |ψi ∈ G

⊥

.

We now define the Grover operator

Q = −I

ψ

I

G

.

Theorem

(Amplitude amplification thoerem)

.

In the 2-dimensional subspace

spanned by |ψ

g

i and |ψi (or equivalently by |ψ

g

i and |ψ

b

i), where

|ψi = sin θ |ψ

g

i + cos θ |ψ

b

i,

we have that Q is rotation by 2θ.

Proof. We have

I

G

|ψ

g

i = −|ψ

g

i, I

G

|ψ

b

i = |ψ

b

i.

So

Q|ψ

g

i = I

ψ

|ψ

g

i, Q|ψ

b

i = −I

ψ

|ψ

b

i.

We know that

I

ψ

= I − 2 |ψihψ|.

So we have

Q|ψ

g

i = I

ψ

|ψ

g

i

= |ψ

g

i − 2(sin θ |ψ

g

i + cos θ |ψ

b

i)(sin θ)

= (1 − 2 sin

2

θ) |ψ

g

i − 2 sin θ cos θ |ψ

b

i

= cos 2θ |ψ

g

i − sin 2θ |ψ

b

i

Q|ψ

b

i = −I

ψ

|ψ

b

i

= −|ψ

b

i + 2(sin θ |ψ

g

i + cos θ |ψ

b

i)(cos θ)

= 2 sin θ cos θ |ψ

g

i + (2 cos

2

θ − 1) |ψ

b

i

= sin 2θ |ψ

g

i + cos 2θ |ψ

b

i.

So this is rotation by 2θ.

If we iterate this

n

times, then we have rotated by 2

nθ

, but we started at

θ

from the |ψ

b

i direction. So we have

Q

n

|ψi = sin(2n + 1)θ |ψ

g

i + cos(2n + 1)θ |ψ

b

i.

If we measure Q

n

|ψi for good versus bad, we know

P(good) = sin

2

(2n + 1)θ,

and this is a maximum, when (2n + 1)θ =

π

2

, i.e.

n =

π

4θ

−

1

2

.

For a general

θ

, we know that

n

is not a n integer. So we use

n

the nearest

integer to

π

4θ

−

1

2

, which is approximately

π

4θ

= O(θ

−1

) = O(1/ sin θ) = O

1

kgood projection of |ψik

.

Example.

Suppose we want to do a Grover search for

r

good items in

N

objects.

We start with

|ψi =

1

√

N

X

all x

|xi =

r

r

N

1

√

r

X

good x

|xi

+

r

N − r

N

1

√

N − r

X

bad x

|xi

!

.

Then G is the subspace spanned by the good x’s, and

sin θ =

r

r

N

,

So Q is a rotation by 2θ, where

θ = sin

−1

r

r

N

≈

r

r

N

for r N. So we will use O(

p

r/N) operations.

Example.

Let

A

be any quantum circuit on start state

|0 ···0i

. Then the final

state is

A |0 ···0i

. The good states are the desired computational outcomes. For

example, if

A

is Shor’s algorithm, then the desired outcomes might be the good

c-values. We can write

A |0 ···0i = a |ψ

g

i + b |ψ

b

i.

The probability of a success in one run is

|a|

2

. So we normally need

O

(1

/|a|

2

)

repetitions of A to succeed with a given constant probability 1 − ε.

Instead of just measuring the result and hoping for the best, we can use

amplitude amplification. We assume we can check if

x

is good or bad, so we can

implement I

G

. We consider

|ψi = A |0 ···0i.

Then we define

Q = −I

A|0···0i

I

G

= −AI

|0···0i

A

†

I

G

.

Here we can construct

A

†

just by reversing the gates in

A

. So all parts are

implementable.

By amplitude amplification, Q is rotation by 2θ, where sin θ = |a|. So after

n ≈

π

4θ

= O(|a|

−1

)

repetitions,

A |0 ···0i

will be rotated to very near to

|ψ

g

i

, and this will succeed

with high probability. This gives us a square root speedup over the naive method.