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.