12.10 Quantum Computing
227
Fig. 12.12 Circuit for the three-qubit quantum Fourier transform. The normalizing factors 1/
√
2
are omitted
|q 1 q 2 q 3 →
1
√
8
7
k=0
e
2πi jk/8
| ˜
q 1 ˜
q 2 ˜
q 3
=
1
√
8
1
˜
q 1 =0
1
˜
q 2 =0
1
˜
q 3 =0
e
2πi j ( ˜
q 1 4+ ˜
q 2 2+ ˜
q 3 )/8
| ˜
q 1 ˜
q 2 ˜
q 3
=
1
√
8
1
˜
q 1 =0
e
2πi j ˜
q 1 /2
| ˜
q 1 ⊗
1
˜
q 2 =0
e
2πi j ˜
q 2 /4
| ˜
q 2 ⊗
1
˜
q 3 =0
e
2πi j ˜
q 3 /8
| ˜
q 3
=
1
√
8
|0 + e
2πi j/2
|1
⊗
|0 + e
2πi j/4
|1
⊗
|0 + e
2πi j/8
|1
=
1
√
8
|0 + e
2πiq 3 /2
|1
⊗
|0 + e
2πi(q 2 /2+q 3 /4)
|1
⊗
|0 + e
2πi(q 1 /2+q 2 /4+q 3 /8)
|1
(12.40)
When evaluating the first bracket we use that e
2πi(2q 1 +q 2 )
= 1 for all values of q 1
and q 2 . Moreover, the factor 1/
√
8 ensures that the transformation is unitary. We
point out that it is straightforward to generalize the method to more qubits. The
last equality from (12.40) can be easily translated into the assembly of quantum
gates shown in Fig. 12.12. The Hadamard gates H provide the reversed signs for
|1 states, consistent with (12.38). The R k -gates cause a phase shift of the “1” state,
provided that the conditioning qubit, indicated by the black dot, is “1.” We point out
that all quantum gates and consequently also composite circuits are unitary, they are
invertible, which allows us to use the QFT circuit backwards to obtain the inverse
QFT. Moreover, note how these gates entangle three qubits to perform the Fourier
transform on N = 8 states with only six gates. This appears to be very efficient
considering that a classical Fourier transform of N data points requires N
2
= 64
multiplications. Even a fast Fourier-transfrom requires on the order of N log 2 N = 24
multiplications. On the other hand, extracting the desired spectral information from
the qubits at the output is difficult, because only phase information is present.
Even though the QFT does not directly provide spectral information, it is very
useful in other ways, such as determining of the period of a cyclic process, called
order finding, and estimating the phase φ of an unknown unitary operator U in eigen-
227
Fig. 12.12 Circuit for the three-qubit quantum Fourier transform. The normalizing factors 1/
√
2
are omitted
|q 1 q 2 q 3 →
1
√
8
7
k=0
e
2πi jk/8
| ˜
q 1 ˜
q 2 ˜
q 3
=
1
√
8
1
˜
q 1 =0
1
˜
q 2 =0
1
˜
q 3 =0
e
2πi j ( ˜
q 1 4+ ˜
q 2 2+ ˜
q 3 )/8
| ˜
q 1 ˜
q 2 ˜
q 3
=
1
√
8
1
˜
q 1 =0
e
2πi j ˜
q 1 /2
| ˜
q 1 ⊗
1
˜
q 2 =0
e
2πi j ˜
q 2 /4
| ˜
q 2 ⊗
1
˜
q 3 =0
e
2πi j ˜
q 3 /8
| ˜
q 3
=
1
√
8
|0 + e
2πi j/2
|1
⊗
|0 + e
2πi j/4
|1
⊗
|0 + e
2πi j/8
|1
=
1
√
8
|0 + e
2πiq 3 /2
|1
⊗
|0 + e
2πi(q 2 /2+q 3 /4)
|1
⊗
|0 + e
2πi(q 1 /2+q 2 /4+q 3 /8)
|1
(12.40)
When evaluating the first bracket we use that e
2πi(2q 1 +q 2 )
= 1 for all values of q 1
and q 2 . Moreover, the factor 1/
√
8 ensures that the transformation is unitary. We
point out that it is straightforward to generalize the method to more qubits. The
last equality from (12.40) can be easily translated into the assembly of quantum
gates shown in Fig. 12.12. The Hadamard gates H provide the reversed signs for
|1 states, consistent with (12.38). The R k -gates cause a phase shift of the “1” state,
provided that the conditioning qubit, indicated by the black dot, is “1.” We point out
that all quantum gates and consequently also composite circuits are unitary, they are
invertible, which allows us to use the QFT circuit backwards to obtain the inverse
QFT. Moreover, note how these gates entangle three qubits to perform the Fourier
transform on N = 8 states with only six gates. This appears to be very efficient
considering that a classical Fourier transform of N data points requires N
2
= 64
multiplications. Even a fast Fourier-transfrom requires on the order of N log 2 N = 24
multiplications. On the other hand, extracting the desired spectral information from
the qubits at the output is difficult, because only phase information is present.
Even though the QFT does not directly provide spectral information, it is very
useful in other ways, such as determining of the period of a cyclic process, called
order finding, and estimating the phase φ of an unknown unitary operator U in eigen-