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.