3Some quantum algorithms
III Quantum Computation
3.2 Quantum Fourier transform and periodicities
We’ve just seen some nice examples of benefits of quantum algorithms. However,
oracles are rather unnatural problems — it is rare to just have a black-box access
to a function without knowing anything else about the function.
How about more “normal” problems? The issue with trying to compare
quantum and classical algorithms for “normal” problems is that we don’t actually
have any method to find the lower bound for the computation complexity. For
example, while we have not managed to find polynomial prime factorization
algorithms, we cannot prove for sure that there isn’t any classical algorithm that
is polynomial time. However, for the prime factorization problem, we do have a
quantum algorithm that does much better than all known classical algorithms.
This is Shor’s algorithm, which relies on the toolkit of the quantum Fourier
transform.
We start by defining the quantum Fourier transform.
Definition
(Quantum Fourier transform mod
N
)
.
Suppose we have an
N
-
dimensional state space with basis
|0i, |1i, ··· , |N − 1i
labelled by
Z/NZ
. The
quantum Fourier transform mod N is defined by
QFT : |ai 7→
1
√
N
N−1
X
b=0
e
2πiab/N
|bi.
The matrix entries are
[QFT]
ab
=
1
√
N
ω
ab
, ω = e
2πi/N
,
where
a, b
= 0
,
1
, ··· , N −
1. We write
QFT
n
for the quantum Fourier transform
mod n.
Note that we are civilized and start counting at 0, not 1.
We observe that the matrix
√
NQFT is
(i) Symmetric
(ii) The first (i.e. 0th) row and column are all 1’s.
(iii)
Each row and column is a geometric progression 1
, r, r
2
, ··· , r
n−1
, where
r = ω
k
for the kth row or column.
Example.
If we look at
QFT
2
, then we get our good old H. However,
QFT
4
is
not H ⊗ H.
Proposition. QFT is unitary.
Proof. We use the fact that
1 + r + ··· + r
N−1
=
(
1−r
N
1−r
r 6= 1
N r = 1
.
So if r = ω
k
, then we get
1 + r + ··· + r
N−1
=
(
0 k 6≡ 0 mod N
N k ≡ 0 mod N
.
Then we have
(QFT
†
QFT)
ij
=
1
√
N
2
X
k
ω
−ik
ω
jk
=
1
N
X
k
ω
(j−i)k
=
(
1 i = j
0 i 6= j
.
We now use the quantum Fourier Transform to solve the periodicity problem.
Example.
Suppose we are given
f
:
Z/NZ → Y
(for some set
Y
). We are
promised that f is periodic with some period r | N, so that
f(x + r) = f(x)
for all x. We also assume that f is injective in each period, so that
0 ≤ x
1
6= x
2
≤ r −1 implies f(x
1
) 6= f(x
2
).
The problem is to find
r
, with any constant level of error 1
− ε
independent of
N. Since this is not a decision problem, we can allow ε >
1
2
.
In the classical setting, if
f
is viewed as an oracle, then
O
(
√
N
) queries are
necessary and sufficient. We are going to show that quantumly,
O
(
log log N
)
queries with
O
(
poly
(
log N
)) pro ce ssing steps suffice. In later applications, we
will see that the relevant input size is
log N
, not
N
. So the classical algorithm is
exponential time, while the quantum algorithm is polynomial time.
Why would we care about such a problem? It turns out that later we will
see that we can reduce prime factorization into a periodicity problem. While
we will actually have a very explicit formula for
f
, there isn’t much we can do
with it, and treating it as a black box and using a slight modification of what
we have here will be much more efficient than any known classical algorithm.
The quantum algorithm is given as follows:
(i)
Make
1
√
N
P
N−1
x=0
|xi
. For example, if
N
= 2
n
, then we can make this using
H
⊗ ··· ⊗
H. If
N
is not a power of 2, it is not immediately obvious how
we can make this state, but we will discuss this problem later.
(ii) We make one query to get
|fi =
1
√
N
X
|xi|f(x)i.
(iii)
We now recall that
r | N
, Write
N
=
Ar
, so that
A
is the number of
periods. We measure the second register, and we will see some
y
=
f
(
x
).
We let
x
0
be the least
x
with
f
(
x
) =
y
, i.e. it is in the first period. Note
that we don’t know what x
0
is. We just know what y is.
By periodicity, we know there are exactly
A
values of
x
such that
f
(
x
) =
y
,
namely
x
0
, x
0
+ r, x
0
+ 2r, ··· , x
0
+ (A − 1)r.
By the Born rule, the first register is collapsed to
|peri =
1
√
A
A−1
X
j=0
|x
0
+ jri
|f(x
0
)i.
We throw the second register away. Note that
x
0
is chosen randomly from
the first period 0, 1, ··· , r − 1 with equal probability.
What do we do next? If we measure
|peri
, we obtain a random
j
-value, so
what we actually get is a random element (
x
0
th) of a random period (
j
th),
namely a uniformly chosen random number in 0
,
1
, ··· , N
. This is not too
useful.
(iv)
The solution is the use the quantum Fourier transform, which is not sur-
prising, since Fourier transforms are classically used to extract periodicity
information.
Apply QFT
N
to |peri now gives
QFT
N
|peri =
1
√
NA
n−1
X
j=0
N−1
X
y=0
ω
(x
0
+jr)y
|yi
=
1
√
NA
N−1
X
y=0
ω
x
0
y
n−1
X
j=0
ω
jry
|yi
We now see the inner sum is a geometric series. If
ω
ry
= 1, then this sum
is just A. Otherwise, we have
A−1
X
j=0
ω
jry
=
1 − ω
rA
1 − ω
ry
=
1 − 1
1 − ω
ry
= 0.
So we are left with
QFT
n
|peri =
r
A
N
r−1
X
k=0
ω
x
0
kN/r
k
N
r
.
Note that before the Fourier transform, the random shift of
x
0
lied in the
label
|x
0
+ jri
. After the Fourier transform, it is now encoded in the phase
instead.
(v)
Now we can measure the label, and we will get some
C
which is a multiple
k
0
N
r
, where 0
≤ k
0
≤ r −
1 is chosen uniformly at random. We rewrite
this equation as
k
0
r
=
C
N
.
We know
C
, because we just measured it, and
N
is a given in the question.
Also,
k
0
is randomly chosen, and
r
is what we want. So how do we extract
that out?
If by good chance, we have
k
0
coprime to
r
, then we can cancel
C/N
to
lowest terms and read off
r
as the resulting denominator
˜r
. Note that
cancelling
C/N
to lowest terms can be done quickly by Euclidean algorithm.
But how likely are we to be so lucky? We can just find some number theory
book, and figure out that the number of natural numbers
< r
that are
coprime to
r
grows as
O
(
r/ log log r
). More precisely, it is
∼ e
−γ
r/ log log r
,
where γ is the other Euler’s constant. We note that
O
r
log log r
> O
1
log log N
.
So if
k
0
is chosen uniformly and randomly, the probability that
k
0
is
coprime to r is at least O(1/ log log N).
Note that if
k
0
is not coprime with
r
, then we have
˜r | r
, and in particular
˜r < r
. So we can check if
˜r
is a true period — we compute
f
(0) and
f
(
˜r
),
and see if they are the same. If
˜r
is wrong, then they cannot be equal as
f
is injective in the period.
While the probability of getting a right answer decreases as
N → ∞
, we just
have to do the experiment many times. From elementary probability, if an
event has some (small) success probability
p
, then given any 0
<
1
−ε <
1,
for
M
=
−
log ε
p
trials, the probability that there is at least one success is
>
1
− ε
. So if we repeat the quantum algorithm
O
(
log log N
) times, and
check
˜r
each time, then we can get a true
r
with any constant level of
probability.
(vi)
We can further improve this process — if we have obtained two attempts
˜r, ˜r
0
, then we know
r
is at least their least common multiple. So we can
in fact achieve this in constant time, if we do a bit more number theory.
However, the other parts of the algorithm (e.g. cancelling
C/N
down to
lowest terms) still use time polynomial in
log N
. So we have a polynomial
time algorithm.
There is one thing we swept under the carpet. We need to find an efficient
way of computing the quantum Fourier transform, or else we just hid all our
complexity in the quantum Fourier transform.
In general, we would expect that a general unitary operations on
n
qubits
needs
exp
(
n
) elementary circuits. However, the quantum Fourier transform is
special.
Fact. QFT
2
n
can be implemented by a quantum circuit of size O(n
2
).
The idea of the construction is to mimic the classical fast Fourier transform.
An important ingredient of it is:
Fact. The state
QFT
2
n
|xi =
1
2
n/2
2
n
−1
X
y=0
ω
xy
|yi
is in fact a product state.
We will not go into the details of implementation.
We can generalize the periodicity problem to arbitrary groups, known as the
hidden subgroup problem. We are given some oracle for
f
:
G → Y
, and we are
promised that there is a subgroup
H < G
such that
f
is constant and distinct on
cosets of
H
in
G
. We want to find
H
(we can make “find” more precise in two
ways — we can either ask for a set of generators, or provide a way of sampling
uniformly from H).
In our case, we had G = (Z/NZ, +), and our subgroup was
H = {0, r, 2r, ··· , (A − 1)r}.
Unfortunately, we do not know how to do this efficiently for a group in general.