quantum mechanics

Quantum Fourier Transform

The Fourier transform is an important operation used in a large class of mathe- matical problems. Many real-world physical and computational problems, that usually deal with a discretized set of data, are e?ciently analyzed and solved employing the discrete Fourier transform, which amounts to transforming one set of complex numbers x0, x1,..., xN ?1 to another set y0, y1,..., yN ?1, ac- cording to

1 N ?1

. 2?ijn .

yn = .
j=0

exp

xj . (9.20)
N

The set {xj } can conveniently be thought of as representing a vector in an

N dimensional complex vector space, and the set {yj } is then a rotated vec- tor, since transformation (9.20) is norm-preserving, . |yj |2 = . |xj |2. For
computational convenience, the dimension of the vector is usually taken such that N = 2k . To accomplish the discrete Fourier transform, a straightforward application of (9.20) requires about N × N = 22k steps of computation. There exists, however, a more economical classical algorithm, called fast Fourier transform—FFT—that performs the transformation in N log(N )= k2k com- putational steps. We describe now a quantum Fourier transform (QFT) algo- rithm, invented by Shor, that o?ers an impressive exponential speed-up over the best known classical FFT algorithm.
Let us use integers j and n, such that 0 ? j, n ? 2k ? 1, to represent the basis states |j) and |n) of a k-qubit quantum register. Recall from Sect. 7.1 that j and n have the binary representation j ? j1j2 ... jk and n ? n1n2 ... nk . The quantum Fourier transform operation UQFT is de?ned via



QFT

1 N ?1

. 2?ijn .

|j) ??

? . exp

|n) . (9.21)

N n=0 N

Then, if the input state of the register is prepared as |?in) = .N ?1 xj |j),
k j=0
and the UQFT transforms every |j) according to (9.21), for the output state
we have

N ?1

. 1 N ?1

. 2?ijn . .

|?out

in . .

k ) = UQFT |?k ) =

xj
j=0

?
n=0

exp
N

|n)

N ?1 ? 1

N ?1

. 2?ijn . ?

N ?1

= . ? ? . exp

xj ? |n) = . yn |n) , (9.22)


n=0

N j=0 N


n=0


j H T T


... T T ?

1 2 3 k?1 k

j2

j3


H T2


...


Tk?2


Tk?1

H




...




Tk?3




Tk?2

k

?k ?1

?k ?2






jk ?1

jk

...

...


H T2 ?2

H ?1

Fig. 9.9. Circuit implementing the quantum Fourier transform.

where the amplitudes yn are given by (9.20).
The circuit realizing the quantum Fourier transform is shown in Fig. 9.9, where the Tl operation is de?ned as



Tl =

. 1 0 .
2?i ,
0 e 2l


while H denotes the usual Hadamard gate. This circuit is based on the fol- lowing product representation for the Fourier transformed register,
|j) ? |j1 ... jk )
k


QFT

1 2 ?1

2?ijn

. exp . . n

?? 2k/2
1


n=0 1

2k | )
1 .


k n .

= 2k/2

. ... . exp

2?ij . l
2l

|n1 ... nk )

n1 =0
1 1

nk =0
1 k

l=1
.

= 2k/2

. ... . - exp . 2?ijnl
2l

|nl)

n1 =0

nk =0 l=1

1
= 2k/2

k
-

l=1

. exp . 2?ijnl .
2l
nl =0

.
|nl)

k 2?ij k

- |0) +e 2l |1)
?

= - |?l)

l=1 2

l=1

|0) + e2?i 0.jk |1)
? ?2

|0) + e2?i 0.jk?1 jk |1)
?2 ···

|0) + e2?i 0.j1 j2 ...jk |1)
?2 ,
(9.23)


where in the last step we have used the decomposition j = j12k?1 + ... + jk 20, binary fraction representation (7.2), and the fact that e2?ir = 1, r being any integer (see Prob. 9.3).


To see that the circuit of Fig. 9.9 indeed realizes transformation (9.23), observe that the action of the Hadamard gate on a qubit in state |jm) (jm ?
{0, 1}) can be cast as
H 0) + e2?i0.jm 1)

|jm) ?? |

? | ,
2


while an application of the controlled-Tl operation b etween the control qubit in state |jc) and target qubit in state ( |0) + |1))/?2, gives



0) + |1)



T jc


2?i
|0) + e c 2l |1)

l?1
|0) + e2?i 0.¸0x..s.0¸jc 1

|jc) | ?

?? |jc) ?2

= |jc)

? | ) .
2

Let us follow through the circuit the evolution of the state of the ?rst qubit,

H 0) + e2?i 0.j1 1)


T j2

0) + e2?i0.j1 j2 1)


T j3

|j1) ?? |

| 2 |
?2 ??

| 3
? ?? ···

jk k
··· ??

|0) + e2?i 0.j1 j2 ...jk |1)
?
2

= |?k ) . (9.24)

Similarly, for the second qubit we have

H 0) + e2?i 0.j2 1)


T j3

0) + e2?i0.j2 j3 1)


T j4

|j2) ?? |

?2
T jk

| 2 |
?? ?

2?i 0.j2 j3 ...jk

| 3
?? ···

k?1 |0) +e

|1)

··· ??

?2 = |?k?1) , (9.25)

and so on for all the qubits through the last one
H 0) + e2?i 0.jk 1)

|jk ) ?? |

? | = |?1) . (9.26)



We then use the swap operations (not shown in Fig. 9.9) between the ?rst and the last qubits, the second and one before the last qubits, etc., to reverse the order of qubits, obtaining ?nally (9.23). In doing this, we apply k logic gates to the ?rst qubit, k ? 1 gates to the second one, etc., all together k(k + 1)/2 gates. At the end, we use k/2 swap gates, if k is even, or (k ? 1)/2 swap gates, if k is odd. So all in all, we need k(k + 2)/2 gates, or O(k2) steps of computation, which is exponentially better than the classical FFT algorithm.
Given such an impressive speed-up, one is then tempted to assume that the quantum Fourier transform can be used to e?ciently solve a great variety of classical problems. This is, however, not entirely true, and to-date only a limited number of problems have been shown to be amenable to the QFT algo- rithm. All of them are examples of a general problem known as the (Abelian) hidden subgroup problem. It includes the order-?nding and prime factoriza- tion which employ the phase estimation procedure of Prob. 9.5, as well as

9.3 Quantum Computer Simulating Quantum Mechanics 265
period-?nding and discrete logarithm determination. Other possible applica- tions of the QFT algorithm include e?cient simulations of certain quantum systems, such as particles con?ned in potentials of speci?c shapes, whose clas- sical counterparts exhibit chaos. One of the main complications associated with the use of the quantum Fourier transform for a broader range of ap- plications is that it is usually very di?cult to prepare the input state of a
quantum register as |?in) = .2 ?1 xj |j), which is typically an entangled
k j=0
in
state of k qubits. Also, even if state |?k ) is successfully prepared and the
transformation (9.22) is accomplished, measuring reliably the amplitudes yn of the output state in a single (or few) runs is usually not possible, unless the input represents a periodic function, in which case at the output only one or just a few states |n) have appreciable probabilities |yn|2.


9.3 Quantum Computer Simulating Quantum Mechanics

Finally, let us brie?y discuss simulations of quantum systems by quantum computers. One of the most important applications of modern (classical) com- puters involves analysis, design and simulation of complex physical systems, such as constructions and buildings, cars and aircraft, and even weapons, to name just a few. However, classical computers are ine?cient in simu- lating quantum systems. As reviewed in Chap. 1, a typical quantum me- chanical problem can be formulated as follows. Given a compound system S composed of subsystems A,B,C,.. ., each having a ?nite number of states NA, NB, NC,.. ., respectively, then the number of states NS spanning the com- plete system S (the dimension of its Hilbert space) is given by the product NS = NA × NB × NC ... At an initial time t0, the state of the system |? S(t0)) is known and, provided the subsystems are unentangled, it is given by the
tensor product |? S(t0)) = |? A)? |? B)? |? C) ... of the initial states |? j )
0 0 0 0
of subsystems j = A,B,C,... The time-evolution of the system is governed by
the Schro¨dinger equation

ik ? |? S) = HS |? S) , (9.27)

where the Hamiltonian of the systems HS = . Hj + V is composed of the
sum of free Hamiltonians of each subsystem Hj plus the term V describing the interactions between them. At time t> t0, the state vector evolves into
|? S(t)) = US(t) |? S(t0)) . (9.28)

where US(t) ? exp[? i HS(t ? t0)] is the evolution operator. Except for a few special cases, analytic expressions for the evolution operator US(t) are usually not attainable, because exponentiating operators is very di?cult. Thus to solve the problem of determining the state of the system |? S(t)), in most cases one would have to use computers.


On a classical computer, solving the Schr¨odinger equation amounts to integrating NS di?erential equations

? i
?t cn = ? k

. Hnmcm , Hnm ? (n S
m

|m) , (9.29)

for NS complex amplitudes cn representing the state vector |? S) = .NS

cn |n).

Each amplitude requires at least 64, or better 128 bits of memory to store its
value. Adding one more subsystem of dimension M increases the dimension NS of system’s Hilbert space M times! Assuming that the subsystems have a comparable number of states Nj ? N , we see that the dimension of the Hilbert space of the total system grows exponentially with the number of subsystems ns, NS ? N ns . As remarked by Caves, “Hilbert space is a big place.” Even for a modest system composed of only a few (ns ” 10) interacting subsys- tems, each having say N ? 10 ? 100 relevant eigenstates, we have to store and process a huge number (NS ? 1010) of complex probability amplitudes. If the size of the system is somewhat larger, even the best classical computers today and in the foreseeable future will not be able to cope with such amounts of data, not to mention the amount of energy required to process it.
If we realize a scalable quantum computer, however, these problems would become tractable. To be able to store and process all the data associated with a quantum system of size NS we need to have a register containing k qubits so that 2k ” NS . That is, the size of the Hilbert space of the computer’s register should be comparable or only slightly larger than that of the system. The computation would then proceeds in four steps outlined in Sect. 9.1: First, we initialize the register to a known initial state |00 ... 0). We then load the in- put by preparing the register in a state |?k ) corresponding to the initial state
|? S(t0)) of the system to be simulated. Since the initial state is usually a simple product state of subsystems, no entanglement is present and this step can be accomplished easily using only a small number of logic gates. Next comes the di?cult part—simulation of the dynamics due to the Hamiltonian
S
H . For that we need to design a sequence of logic gates U1, U2,... Ul, whose
application to the register results in the evolution operator US(t) according

to UlUl?1 ... U1 = US(t). This transformation can be simulated e?ciently, if the interaction Hamiltonian can be represented as a sum V = .l V l involv-
ing a ?nite number of terms, polynomial in the size of the total system, each element V l acting only on a small number of subsystems at a time. This is the case for many physical systems of interest, where the interaction between the subsystems usually involves only two- or few-body interactions. Finally, we measure the quantum register whose state corresponds to that of the sim- ulated system. If the measured state is not an eigenstate of the register, we may have to perform many repetitions of this cycle, to attain a reliable prob- ability distribution for the ?nal state of the system. Provided the number of required repetitions does not grow exponentially with the system’s size, but only polynomially, we can claim that quantum computers can e?ciently


simulate quantum mechanics. Thus we see that this is essentially an ana- log computation, since, upon the program execution, the quantum computer imitates another physical system being simulated, as envisioned by Richard Feynman as early as 1982.