3Some quantum algorithms

III Quantum Computation

3.1 Balanced vs constant problem

We are going to come to our first quantum algorithm.

Here our computational task is a bit special. Instead of an input

i

1

, ··· , i

n

∈

B

n

, we are given a black box/oracle that computes some

f

:

B

m

→ B

n

. We may

have some a priori promise on

f

, and we want to determine some property of

the function f. The only access to f is querying the oracle with its inputs.

The use of

f

(classical) or

U

f

(quantum) counts as one step of computation.

The query complexity of this task is the least number of times the oracle needs

to be queried. Usually, we do not care much about how many times the other

gates are used.

Obviously, if we just query all the values of the function, then we can

determine anything about the function, since we have complete information. So

the goal is to see if we can do it with fewer queries.

The problem we are going to look at is the balanced vs constant problem.

The input black box is a function

f

:

B

n

→ B

1

. The promise is that

f

is either

(i) a constant function, i.e. f (x) = 0 for all x, or f (x) = 1 for all x; or

(ii) a balanced function, i.e. exactly half of the values in B

n

are sent to 1.

We want to determine if f is (i) or (ii) with certainty.

Classically, if we want to find the answer with certainty, in the worst case

scenario, we will have to perform 2

n−1

+ 1 queries — if you are really unlucky,

you might query a balanced function 2

n−1

times and get 0 all the time, and you

can’t distinguish it from a constant 0 function.

Quantumly, we have the Deutsch-Jozsa algorithm, that answers the question

in 1 query!

A trick we are going to use is something known as “phase kickback ”. Instead

of encoding the result as a single bit, we encode them as

±

signs, i.e. as phases

of the quantum bits. The “kickback” part is about using the fact that we have

|ai(e

iθ

|bi) = (e

iθ

|ai) |bi,

So we might do something to

|bi

to give it a phase, and then we “kick back” the

phase on |ai, and hopefully obtain something when we measure |ai.

Recall that we have

U

f

|xi|yi = |xi|y ⊕ f(x)i.

Here |xi has n qubits, and |yi has 1 qubit.

The non-obvious thing to do is to set the output register to

|αi =

|0i − |1i

2

= H |1i = HX |0i.

We then note that U

f

acts by

|xi

|0i − |1i

2

7→ |xi

|f(x)i − |1 ⊕ f(x)i

√

2

=

(

|xi

|0i−|1i

√

2

if f(x) = 0

|xi

|1i−|0i

√

2

if f(x) = 1

= (−1)

f(x)

|xi|αi.

Now we do this to the superposition over all possible x:

1

√

2

n

X

|xi|αi 7→

1

√

2

n

X

(−1)

f(x)

|xi

|αi.

So one query gives us

|ξ

f

i =

1

√

2

n

X

(−1)

f(x)

|xi.

The key observation now is simply that if

f

is constant, then all the signs are

the same. If

x

is balanced, then exactly half of the signs are + and

−

. The

crucial thing is that

|ξ

f

const

i

is orthogonal to

|ξ

f

balanced

i

. This is a go od thing,

since orthogonality is something we can perfectly distinguish with a quantum

measurement.

There is a slight technical problem here. We allow only measurements in the

standard

|0i

,

|1i

basis. So we need want to “rotate” our states to the standard

basis. Fortunately, recall that

|0i···|0i

1

√

2

n

P

|xi

H⊗···⊗H

,

Now recall that H is self-inverse, so

H

2

=

I

. Thus, if we apply H

⊗ ··· ⊗

H to

1

√

2

n

P

|xi, then we obtain |0i···|0i.

We write

|η

f

i = H ⊗ ··· ⊗ H |ξ

f

i.

Since H is unitary, we still have

|η

f

const

i ⊥ |η

f

balanced

i.

Now we note that if f is constant, then

η

f

const

= ±|0i···|0i.

If we look at what

|η

f

balanced

i

is, it will be a huge mess, but it doesn’t really

matter — all that matters is that it is perpendicular to |0i···|0i.

Now when we measure

η

f

, if

f

is a constant function, then we obtain 0

···

0

with probability 1. If it is balanced, then we obtain something that is not 0 with

probability 1. So we can determine the result with probability 1.

|0i

.

.

.

|0i

|0i

H

H

H

X H

U

f

H

H

H

input

output

measure

discard

This uses exactly one query, with 1 + (

n

+ 1) +

n

+

n

=

O

(

n

) elementary gates

and measurements.

What if we tolerate error in the balanced vs constant problem? In other

words, we only require that the answer is correct with probability 1

− ε

with

0 < ε <

1

2

.

In the quantum case, nothing much changes, since we are probably not going

to do better than 1 query. However, we no longer have a huge benefit over

classical algorithms. There is a classical randomized algorithm with

O

(

log

(1

/ε

))

queries, and in particular does not depend on n.

Indeed, we do it the obvious way — we choose some

K x

-values uniformly at

random from

B

n

, say

x

1

, ··· , x

n

(where

K

is fixed and determined later). We

then evaluate f(x

1

), ··· , f(x

n

).

If all the outputs are the same, then we say

f

is constant. If they are not

the same, then we say f is balanced.

If

f

actually is constant, then the answer is correct with probability 1. If

f

is balanced, then each

f

(

x

i

) is 0 or 1 with equal probability. So the probability

of getting the same values for all x

i

is

2

2

K

= 2

1−K

.

This is our failure probability. So if we pick

K > log

2

(ε

−1

) + 1,

then we have a failure probability of less than ε.

Can we decide every yes/no question about

f

:

B

n

→ B

1

’s by quantum

algorithms with “a few” queries? The answer is no. One prominent example is

the SAT problem (satisfiability problem) — given an arbitrary

f

, we want to

determine if there an

x

such that

f

(

x

) = 1? It can be shown that any quantum

algorithm (even if we allow for bounded errors) needs at least

O

(

√

2

n

) queries,

which is achieved by Grover’s algorithm. Classically, we need

O

(2

n

) queries. So

we have achieved a square root speedup, which is good, but not as good as the

Deutsch-Jozsa algorithm.

In any case, the Deutsch-Jozsa algorithm demonstrates how we can achieve

an exponential benefit with quantum algorithms, but it happens only when

we have no error tolerance. In real life scenario, external factors will lead to

potential errors anyway, and requiring that we are always correct is not a sensible

requirement.

There are other problems where quantum algorithms are better:

Example

(Simon’s algorithm)

.

The Simon’s problem is a promise problem about

f

:

B

n

→ B

n

with provably exponential separation between classical (

O

(2

n/4

))

and quantum (

O

(

n

)) query complexity even with bounded error. The details

are on the first example sheet.