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.