3Some quantum algorithms
III Quantum Computation
3.4 Search problems and Grover’s algorithm
We are now going to turn our attention to search problems. These are very
important problems in computing, as we can formulate almost all problems as
some sort of search problems.
One important example is simultaneous constraint satisfaction. Here we have
a large configuration space of options, and we want to find some configuration
that satisfies some constraints. For example, when designing a lecture timetable
for Part III courses, we need to schedule the courses so that we don’t clash
two popular courses in the same area, and the courses need to have big enough
lecture halls, and we have to make sure a lecturer doesn’t have to simultaneously
lecture two courses at the same time. This is very complicated.
In general, search problems have some common features:
(i)
Given any instance of solution attempt, it is easy to check if it is good or
not.
(ii) There are exponentially many possible instances to try out.
One example is the boolean satisfiability problem, which we have already
seen before.
Example
(Boolean satisfiability problem)
.
The boolean satisfiability problem
(SAT ) is as follows — given a Boolean formula
f
:
B
n
→ B
, we want to know if
there is a “satisfying argument”, i.e. if there is an x with f(x) = 1.
This has complexity class
NP
, standing for non-deterministic polynomial
time. There are many ways to define
NP
, and here we will provide two. The
first definition of NP will involve the notion of a verifier:
Definition (Verifier). Suppose we have a language L ⊆ B
∗
, where
B
∗
=
[
n∈N
B
n
is the set of all bit strings.
A verifier for L is a computation V (w, c) with two inputs w, c such that
(i) V halts on all inputs.
(ii) If w ∈ L, then for some c, V (w, c) halts with “accept”.
(iii) If w 6∈ L, then for all c, V (w, c) halts with “reject”.
A polynomial time verifier is a
V
that runs in polynomial time in
|w|
(not
|w| + |c|!).
We can think of
c
as “certificate of membership”. So if you are a member,
you can exhibit a certificate of membership that you are in there, and we can
check if the certification is valid. However, if you are not a member, you cannot
“fake” a certificate.
Definition
(Non-deterministic polynomial time problem)
. NP
is the class of
languages that have polynomial time verifiers.
Example.
The SAT problem is in
NP
. Here
c
is the satisfying argument, and
V (f, c) just computes f(c) and checks whether it is 1.
Example.
Determining if a number is composite is in
NP
, where a certificate
is a factor of the number.
However, it is not immediately obvious that testing if a numb er is prime is
in
NP
. It is an old result that it indeed is, and recent progress shows that it is
in fact in P.
It is rather clear that
P ⊆ NP
. Indeed, if we can check membership in
polynomial time, then we can also construct a verifier in polynomial time that
just throws the certificate away and check directly.
There is another model of
NP
, via non-deterministic computation. Recall
that in probabilistic computation, in some steps, we had to pick a random
number, and picking a different number would lead to a different “branch”. In
the case of non-deterministic computation, we are allowed to take all paths at
the same time. If some of the paths end up being accepting, then we accept the
input. If all paths reject, then we reject the input. Then we can alternatively
say a problem is in
NP
if there is a p olynomial-time non-deterministic machine
that checks if the string is in the language.
It is not difficult to see that these definitions of
NP
are equivalent. Suppose
we have a non-deterministic machine that checks if a string is in the language.
Then we can construct a verifier whose certificate is a prescription of which
particular branch we should follow. Then the verifier just takes the prescription,
follows the path described and see if we end up being accepted.
Conversely, if we have a verifier, we can construct a non-deterministic machine
by testing a string on all possible certificates, and check if any of them accepts.
Unfortunately, we don’t know anything about how these different complexity
classes compare. We clearly have
P ⊆ BPP ⊆ BQP
and
P ⊆ NP
. However,
we do not know if these inclusions are strict, or how
NP
compares to the others.
Unstructured search problem and Grover’s algorithm
Usually, when we want to search something, the search space we have is structured
in some way, and this greatly helps our searching problem.
For example, if we have a phone book, then the names are ordered alpha-
betically. If we want to find someone’s phone number, we don’t have to look
through the whole b ook. We just open to the middle of the book, and see if the
person’s name is before or after the names on the page. By one lookup like this,
we have already eliminated half of the phone book we have to search through,
and we can usually very quickly locate the name.
However, if we know someone’s phone number and want to figure out their
name, it is pretty much hopeless! This is the problem with unstructured data!
So the problem is as follows: we are given an unstructured database with
N
= 2
n
items and a unique good item (or no good items). We can query any
item for good or bad-ness. The problem is to find the good item, or determine if
one exists.
Classically,
O
(
N
) queries are necessary and sufficient. Even if we are asking
for a right result with fixed probability
c
, if we pick items randomly to check,
then the probability of seeing the “good” one in
k
queries is given by
k/N
. So
we still need O(N ) queries for any fixed probability.
Quantumly, we have Grover’s algorithm. This needs
O
(
√
N
) queries, and
this is both necessary and sufficient.
The database of
N
= 2
n
items will be considered as an oracle
f
:
B
n
→ B
1
.
it is promised that there is a unique
x
0
∈ B
n
with
f
(
x
0
) = 1. The problem is to
find x
0
. Again, we have the quantum version
U
f
|xi|yi = |xi|y ⊗ f(x)i.
However, we’ll use instead I
x
0
on n qubits given by
I
x
0
|xi =
(
|xi x 6= x
0
−|xi x 6= x
0
.
This can be constructed from
U
f
as we’ve done before, and one use of
I
x
0
can
be done with one use of U
f
.
|si I
x
0
|si
|0i−|1i
2
|0i−|1i
2
U
f
We can write I
x
0
as
I
x
0
= I − 2 |x
0
ihx
0
|,
where I is the identity operator.
We are now going to state the Grover’s algorithm, and then later prove that
it works.
For convenience, we write
H
n
= H ⊗ ··· ⊗ H
| {z }
n times
We start with a uniform sup erposition
|ψ
0
i = H
n
|0 ···0i =
1
√
n
X
all x
|xi.
We consider the Grover iteration operator on n qubits given by
Q = −H
n
I
0
H
n
I
x
0
.
Here running
I
x
0
requires one query (whereas
I
0
is “free” because it is just
I − 2 |0ih0|).
Note that all these operators are all real. So we can pretend we are living
in the real world and have nice geometric pictures of what is going on. We let
P(x
0
) be the (real) plane spanned by |x
0
i and |ψ
0
i. We claim that
(i) In this plane P(x
0
), this operator Q is a rotation by 2α, where
sin α =
1
√
N
= hx
0
|ψ
0
i.
(ii) In the orthogonal complement P(x
0
)
⊥
, we have Q = −I.
We will prove these later on. But if we know this, then we can repeatedly apply
Q
to
|ψ
0
i
to rotate it near to
|x
0
i
, and then measure. Then we will obtain
|x
0
i
with very high probability:
P(x
0
)
|ψ
0
i
|x
0
i
β
α
The initial angle is
cos β = hx
0
|ψ
0
i =
1
√
N
.
So the number of iterations needed is
cos
−1
(1/
√
N)
2 sin
−1
(1/
√
N)
=
β
2α
.
In general, this is not an integer, but applying a good integer approximation to it
will bring us to very close to
|x
0
i
, and thus we measure
x
0
with high probability.
For large n, the number of iterations is approximately
π/2
2/
√
N
=
π
4
√
N.
Example. Let’s do a boring example with N = 4. The initial angle satisfies
cos β =
1
√
4
=
1
2
.
So we know
β =
π
3
.
Similarly, we have
2α = 2 sin
−1
1
2
=
π
3
.
So 1 iteration of
Q
will rotate
|ψ
0
i
exactly to
|x
0
i
, so we can find it with certainty
with 1 lookup.
Now we prove that this thing actually works. In general, for any unitary
U
and I
|ψi
= I − 2 |ψihψ|, we have
UI
|ψi
U
†
= U IU
†
− 2U |ψihψ|U
†
= I
U|ψi
.
In particular, since
H
n
is self-adjoint, i.e.
H
†
n
H
n
, and that by definition
H
n
|0i
=
|ψ
0
i, we know
Q = −H
n
I
0
H
n
I
x
0
= −I
|ψ
0
i
I
x
0
.
Next we note that for any |ψi and |ξi, we know by definition
I
|ψi
|ξi = |ξi−2 |ψihψ|ξi.
So this modifies |ξi by some multiple of |ψi. So we know our operator
Q|ψi = −I
|ψ
0
i
I
x
0
|ψi
modifies
|ψi
first by some multiple of
|x
0
i
, then by some multiple of
ψ
0
. So if
|ξi ∈ P(x
0
), then Q|ψi ∈ P(x
0
) too! So Q preserves P(x
0
).
We know that
Q
is a unitary, and it is “real”. So it must be a rotation or
a reflection, since these are the only things in O(2). We can explicitly figure
out what it is. In the plane
P
(
x
0
), we know
I
|x
0
i
is reflection in the mirror line
perpendicular to
|x
0
i
. Similarly,
I
|ψ
0
i
is reflection in the mirror line perpendicular
to |ψ
0
i.
We now use the following facts about 2D Euclidean geometry:
(i)
If
R
is a reflection in mirror
M
along
|Mi
, then
−R
is reflection in mirror
M
⊥
along
M
⊥
.
To see this, we know any vector can be written as a |Mi + b
M
⊥
. Then
R
sends this to
a |Mi − b
M
⊥
, while
−R
sends it to
−a |Mi
+
b
M
⊥
,
and this is reflection in
M
⊥
.
(ii) Suppose we have mirrors M
1
and M
2
making an angle of θ:
M
1
M
2
θ
Then reflection in
M
1
then reflection in
M
2
is the same as rotating coun-
terclockwise by 2θ.
So we know
Q = −I
|ψ
0
i
I
|x
0
i
is reflection in
x
⊥
0
then reflection in
ψ
⊥⊥
0
=
|ψ
0
i
. So this is a rotation by 2
α
,
where α is the angle between
x
⊥
0
and |ψ
0
i, i.e.
sin α = cos β = hx
0
|ψ
0
i.
To prove our second claim that
Q
acts as
−1
in
P
(
x
0
)
⊥
, we simply note that if
|ξi ∈ P(x
0
)
⊥
, then |ξi ⊥ |ψi
0
and ξ ⊥ |x
0
i. So both I
|x
0
i
and I
|ψ
0
i
fix |ξi.
In fact, Grover’s algorithm is the best algorithm we can achieve.
Theorem.
Let
A
be any quantum algorithm that solves the unique search
problem with probability 1
− ε
(for any constant
ε
), with
T
queries. Then
T
is
at least O(
√
N). In fact, we have
T ≥
π
4
(1 − ε)
√
N.
So Grover’s algorithm is not only optimal in the growth rate, but in the
constant as well, asymptotically.
Proof is omitted.
Further generalizations
Suppose we have multiple good items instead, say
r
of them. We then replace
I
x
0
with I
f
, where
I
f
|xi =
(
−|xi x good
|xi x bad
We run the same algorithm as before. We let
|ψ
good
i =
1
√
r
X
x good
|xi.
Then now
Q
is a rotation through 2
α
in the plane spanned by
|ψ
good
i
and
|ψ
0
i
with
sin α = hψ
good
|ψ
0
i =
r
r
N
.
So for large N, we need
π/2
2
p
r/N
=
π
4
r
N
r
,
i.e. we have a
√
r
reduction over the unique case. We will prove that these
numbers are right later when we prove a much more general result.
What if we don’t know what
r
is? The above algorithm would not work,
because we will not know when to stop the rotation. However, there are some
tricks we can do to fix it. This involves cleverly picking angles of rotation at
random, and we will not go into the details.