![\"\"](\"https:\/\/learning.oreilly.com\/api\/v2\/epubs\/urn:orm:book:9781482238129\/files\/bgb9.png\")
<\/p>\n\n\n\nThe quantum Fourier transform (QFT) is simply the DFT operation on the<\/p>\n\n\n\n
amplitudes of a quantum state. The DFT matrix is unitary, and can therefore<\/p>\n\n\n\n
represent a quantum transformation. We can de\ufb01ne the QFT (order N = 2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
)<\/p>\n\n\n\n
of an n-qubit basis state |xi by<\/p>\n\n\n\n
\u02c6<\/p>\n\n\n\n
F<\/p>\n\n\n\n
N<\/p>\n\n\n\n
|xi =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
N<\/p>\n\n\n\n
N\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
y=0<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
xy<\/p>\n\n\n\n
N<\/p>\n\n\n\n
|yi. (8.37)<\/p>\n\n\n\n
Interestingly, as we have seen in Equation 8.26, the QFT transform for n = 2<\/p>\n\n\n\n
is just the Hadamard gate.<\/p>\n\n\n\n
When applied to a superposition state |\u03c8i =<\/p>\n\n\n\n
P<\/p>\n\n\n\n
i<\/p>\n\n\n\n
C<\/p>\n\n\n\n
i<\/p>\n\n\n\n
|ii, the QFT performs<\/p>\n\n\n\n
a DFT on the coe\ufb03cients C<\/p>\n\n\n\n
i<\/p>\n\n\n\n
:<\/p>\n\n\n\n
\u02c6<\/p>\n\n\n\n
F<\/p>\n\n\n\n
N<\/p>\n\n\n\n
|\u03c8i =<\/p>\n\n\n\n
X<\/p>\n\n\n\n
i<\/p>\n\n\n\n
C<\/p>\n\n\n\n
i<\/p>\n\n\n\n
U<\/p>\n\n\n\n
N<\/p>\n\n\n\n
|ii<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
X<\/p>\n\n\n\n
i<\/p>\n\n\n\n
C<\/p>\n\n\n\n
i<\/p>\n\n\n\n
X<\/p>\n\n\n\n
j<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
ij<\/p>\n\n\n\n
N<\/p>\n\n\n\n
|ji (8.38)<\/p>\n\n\n\n
=<\/p>\n\n\n\n
X<\/p>\n\n\n\n
j<\/p>\n\n\n\n
\ue000<\/p>\n\n\n\n
DFT<\/p>\n\n\n\n
N<\/p>\n\n\n\n
C<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
j<\/p>\n\n\n\n
|ji. (8.39)<\/p>\n\n\n\n
where C denotes the vector of coe\ufb03cients in the state representation.<\/p>\n\n\n\n
An e\ufb03cient algorithm for evaluating the QFT is inspired by the FFT<\/p>\n\n\n\n
algorithm, where we compute the bit-wise breakup of the action of<\/p>\n\n\n\n
\u02c6<\/p>\n\n\n\n
F on its<\/p>\n\n\n\n
<\/p>\n\n\n\n
Quantum Algorithms 159<\/p>\n\n\n\n
input. Remember, |yi<\/p>\n\n\n\n
n<\/p>\n\n\n\n
=<\/p>\n\n\n\n
N<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
j=0<\/p>\n\n\n\n
|y<\/p>\n\n\n\n
j<\/p>\n\n\n\n
i. Each y<\/p>\n\n\n\n
j<\/p>\n\n\n\n
takes a value 0 or 1. The QFT<\/p>\n\n\n\n
has superpositions of |yi with a phase \u03c9<\/p>\n\n\n\n
xy\/N<\/p>\n\n\n\n
N<\/p>\n\n\n\n
, containing the integer product<\/p>\n\n\n\n
of x and y. We want to break this up into the constituent bits, the y<\/p>\n\n\n\n
j<\/p>\n\n\n\n
s. So we<\/p>\n\n\n\n
write<\/p>\n\n\n\n
xy =<\/p>\n\n\n\n
\ue000<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
+ 2x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
+ \u00b7\u00b7\u00b7 + 2<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
x<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
\ue001\ue000<\/p>\n\n\n\n
y<\/p>\n\n\n\n
0<\/p>\n\n\n\n
+ 2y<\/p>\n\n\n\n
1<\/p>\n\n\n\n
+ \u00b7\u00b7\u00b72<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
y<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
. (8.40)<\/p>\n\n\n\n
Now any product in this expansion that has a coe\ufb03cient of 2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
or higher can<\/p>\n\n\n\n
be dropped since it would contribute unity to the phase: \u03c9<\/p>\n\n\n\n
2n<\/p>\n\n\n\n
N<\/p>\n\n\n\n
= 1. So we \ufb01nd<\/p>\n\n\n\n
xy<\/p>\n\n\n\n
N<\/p>\n\n\n\n
=<\/p>\n\n\n\n
\ue010<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
+<\/p>\n\n\n\n
x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
+ \u00b7\u00b7\u00b7 +<\/p>\n\n\n\n
x<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\ue011<\/p>\n\n\n\n
y<\/p>\n\n\n\n
0<\/p>\n\n\n\n
+<\/p>\n\n\n\n
\ue010<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
+<\/p>\n\n\n\n
x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
+ \u00b7\u00b7\u00b7 +<\/p>\n\n\n\n
x<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\ue011<\/p>\n\n\n\n
y<\/p>\n\n\n\n
1<\/p>\n\n\n\n
.<\/p>\n\n\n\n
.<\/p>\n\n\n\n
.<\/p>\n\n\n\n
+<\/p>\n\n\n\n
\ue010<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
2<\/p>\n\n\n\n
2<\/p>\n\n\n\n
+<\/p>\n\n\n\n
x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\ue011<\/p>\n\n\n\n
y<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
+<\/p>\n\n\n\n
\ue010<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\ue011<\/p>\n\n\n\n
y<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
. (8.41)<\/p>\n\n\n\n
Using the binary \u201cpoint\u201d notation<\/p>\n\n\n\n
0.x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
x<\/p>\n\n\n\n
2<\/p>\n\n\n\n
x<\/p>\n\n\n\n
3<\/p>\n\n\n\n
…x<\/p>\n\n\n\n
n<\/p>\n\n\n\n
=<\/p>\n\n\n\n
x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
+<\/p>\n\n\n\n
x<\/p>\n\n\n\n
2<\/p>\n\n\n\n
2<\/p>\n\n\n\n
2<\/p>\n\n\n\n
+<\/p>\n\n\n\n
x<\/p>\n\n\n\n
3<\/p>\n\n\n\n
2<\/p>\n\n\n\n
3<\/p>\n\n\n\n
+ …<\/p>\n\n\n\n
x<\/p>\n\n\n\n
n<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
, (8.42)<\/p>\n\n\n\n
xy<\/p>\n\n\n\n
N<\/p>\n\n\n\n
= y<\/p>\n\n\n\n
0<\/p>\n\n\n\n
(0.x<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
x<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
\u00b7\u00b7\u00b7x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
) + y<\/p>\n\n\n\n
1<\/p>\n\n\n\n
(0.x<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
\u00b7\u00b7\u00b7x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
) + \u00b7\u00b7\u00b7 + y<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
(0.x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
). (8.43)<\/p>\n\n\n\n
Using this to write the QFT in bit-wise expansion, we can associate an expo-<\/p>\n\n\n\n
nential factor with each bit of y, the output becomes the following product<\/p>\n\n\n\n
state:<\/p>\n\n\n\n
\u02c6<\/p>\n\n\n\n
F<\/p>\n\n\n\n
N<\/p>\n\n\n\n
|xi =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
X<\/p>\n\n\n\n
y<\/p>\n\n\n\n
e<\/p>\n\n\n\n
2\u03c0ixy\/N<\/p>\n\n\n\n
|y<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i \u2297 |y<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i\u00b7\u00b7\u00b7|y<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
i<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
X<\/p>\n\n\n\n
y<\/p>\n\n\n\n
0<\/p>\n\n\n\n
=0,1<\/p>\n\n\n\n
e<\/p>\n\n\n\n
2\u03c0iy<\/p>\n\n\n\n
0<\/p>\n\n\n\n
(0.x<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
x<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
\u00b7\u00b7\u00b7x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
)<\/p>\n\n\n\n
|y<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i<\/p>\n\n\n\n
!<\/p>\n\n\n\n
\u2297<\/p>\n\n\n\n
X<\/p>\n\n\n\n
y<\/p>\n\n\n\n
1<\/p>\n\n\n\n
=0,1<\/p>\n\n\n\n
e<\/p>\n\n\n\n
2\u03c0iy<\/p>\n\n\n\n
1<\/p>\n\n\n\n
(0.x<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
\u00b7\u00b7\u00b7x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
)<\/p>\n\n\n\n
|y<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i<\/p>\n\n\n\n
!<\/p>\n\n\n\n
\u2297<\/p>\n\n\n\n
\u00b7\u00b7\u00b7 \u2297<\/p>\n\n\n\n
\uf8eb<\/p>\n\n\n\n
\uf8ed<\/p>\n\n\n\n
X<\/p>\n\n\n\n
y<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
=0,1<\/p>\n\n\n\n
e<\/p>\n\n\n\n
2\u03c0iy<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
(0.x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
)<\/p>\n\n\n\n
|y<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
i<\/p>\n\n\n\n
\uf8f6<\/p>\n\n\n\n
\uf8f8<\/p>\n\n\n\n
=<\/p>\n\n\n\n
\ue012<\/p>\n\n\n\n
|0i + e<\/p>\n\n\n\n
2\u03c0i(0.x<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
x<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
\u00b7\u00b7\u00b7x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
)<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\ue013<\/p>\n\n\n\n
\u2297<\/p>\n\n\n\n
\ue012<\/p>\n\n\n\n
|0i + e<\/p>\n\n\n\n
2\u03c0i(0.x<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
\u00b7\u00b7\u00b7x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
)<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\ue013<\/p>\n\n\n\n
\u2297<\/p>\n\n\n\n
\u00b7\u00b7\u00b7 \u2297<\/p>\n\n\n\n
\ue012<\/p>\n\n\n\n
|0i + e<\/p>\n\n\n\n
2\u03c0i(0.x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
)<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\ue013<\/p>\n\n\n\n
(8.44)<\/p>\n\n\n\n
<\/p>\n\n\n\n
160 Introduction to Quantum Physics and Information Processing<\/p>\n\n\n\n
Each term in the product of Equation 8.44 is the state of an output qubit<\/p>\n\n\n\n
for the corresponding qubit of the input. This translates into a circuit for<\/p>\n\n\n\n
evaluating<\/p>\n\n\n\n
\u02c6<\/p>\n\n\n\n
F<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
. The order of occurrence of the terms must be noted: the \ufb01rst<\/p>\n\n\n\n
term is the least signi\ufb01cant bit, and the last is the most signi\ufb01cant bit of the<\/p>\n\n\n\n
output.<\/p>\n\n\n\n
Example 8.5.1. QFT circuit for n = 2:<\/p>\n\n\n\n
|x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i<\/p>\n\n\n\n
\u02c6<\/p>\n\n\n\n
F<\/p>\n\n\n\n
\u2212\u2192<\/p>\n\n\n\n
|0i + e<\/p>\n\n\n\n
2\u03c0i(0.x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
)<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\u2297<\/p>\n\n\n\n
|0i + e<\/p>\n\n\n\n
2\u03c0i(0.x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
)<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
This means<\/p>\n\n\n\n
|x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i \u2212\u2192<\/p>\n\n\n\n
|0i + e<\/p>\n\n\n\n
2\u03c0i(<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
2<\/p>\n\n\n\n
)<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
= |y<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i<\/p>\n\n\n\n
|x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i \u2212\u2192<\/p>\n\n\n\n
|0i + e<\/p>\n\n\n\n
2\u03c0i(<\/p>\n\n\n\n
x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
+<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
4<\/p>\n\n\n\n
)<\/p>\n\n\n\n
|1i<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2<\/p>\n\n\n\n
= |y<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i<\/p>\n\n\n\n
Here |y<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i has an x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
-dependent phase of e<\/p>\n\n\n\n
i\u03c0<\/p>\n\n\n\n
for |1i, which can be obtained<\/p>\n\n\n\n
by an H acting on |x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i. Similarly |y<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i has a x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
-dependent phase of e<\/p>\n\n\n\n
i\u03c0<\/p>\n\n\n\n
and<\/p>\n\n\n\n
an x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
-dependent phase of e<\/p>\n\n\n\n
i\u03c0\/2<\/p>\n\n\n\n
for |1i. The \ufb01rst is obtained by an H on |x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i<\/p>\n\n\n\n
while the second is the x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
-controlled action of the gate R<\/p>\n\n\n\n
1<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1 0<\/p>\n\n\n\n
0 e<\/p>\n\n\n\n
i\u03c0\/2<\/p>\n\n\n\n
!<\/p>\n\n\n\n
:<\/p>\n\n\n\n
|x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i<\/p>\n\n\n\n
H<\/p>\n\n\n\n
R<\/p>\n\n\n\n
1<\/p>\n\n\n\n
|y<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i<\/p>\n\n\n\n
|x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i<\/p>\n\n\n\n
\u2022<\/p>\n\n\n\n
H<\/p>\n\n\n\n
|y<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i<\/p>\n\n\n\n
Note that the output is to be read in reverse order!<\/p>\n\n\n\n
Exercise 8.4. Work out the circuit for the QFT for n = 3.<\/p>\n\n\n\n
|x<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
i<\/p>\n\n\n\n
H<\/p>\n\n\n\n
R<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
R<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
. . .<\/p>\n\n\n\n
R<\/p>\n\n\n\n
1<\/p>\n\n\n\n
|y<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i<\/p>\n\n\n\n
|x<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
i<\/p>\n\n\n\n
\u2022<\/p>\n\n\n\n
H<\/p>\n\n\n\n
R<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
R<\/p>\n\n\n\n
n\u22123<\/p>\n\n\n\n
. . .<\/p>\n\n\n\n
|y<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i<\/p>\n\n\n\n
.<\/p>\n\n\n\n
.<\/p>\n\n\n\n
.<\/p>\n\n\n\n
.<\/p>\n\n\n\n
.<\/p>\n\n\n\n
.<\/p>\n\n\n\n
.<\/p>\n\n\n\n
.<\/p>\n\n\n\n
.<\/p>\n\n\n\n
|x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i<\/p>\n\n\n\n
\u2022 \u2022<\/p>\n\n\n\n
H<\/p>\n\n\n\n
R<\/p>\n\n\n\n
1<\/p>\n\n\n\n
|y<\/p>\n\n\n\n
n\u22122<\/p>\n\n\n\n
i<\/p>\n\n\n\n
|x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i<\/p>\n\n\n\n
\u2022 \u2022 \u2022<\/p>\n\n\n\n
H<\/p>\n\n\n\n
|y<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
i<\/p>\n\n\n\n
FIGURE 8.10: Circuit for the quantum Fourier transform<\/p>\n\n\n\n
\u02c6<\/p>\n\n\n\n
F<\/p>\n\n\n\n
2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
, on n qubits.<\/p>\n\n\n\n
You should now be able to work out that Figure 8.10 is an e\ufb03cient quantum<\/p>\n\n\n\n
circuit for the QFT on n qubits.. We require controlled phase gates, with phase<\/p>\n\n\n\n
![\"\"](\"https:\/\/learning.oreilly.com\/api\/v2\/epubs\/urn:orm:book:9781482238129\/files\/bgba.png\")
<\/p>\n\n\n\n
Quantum Algorithms 161<\/p>\n\n\n\n
matrices like<\/p>\n\n\n\n
R<\/p>\n\n\n\n
d<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1 0<\/p>\n\n\n\n
0 e<\/p>\n\n\n\n
i\u03c0\/2<\/p>\n\n\n\n
d<\/p>\n\n\n\n
!<\/p>\n\n\n\n
, (8.45)<\/p>\n\n\n\n
where d can be interpreted as the distance from the control bit. Notice that<\/p>\n\n\n\n
the output bits are in reverse order. One can either agree to read the output<\/p>\n\n\n\n
in reverse order or to perform a swap at the end.<\/p>\n\n\n\n
The e\ufb03ciency of this circuit is related to the number of basic gate oper-<\/p>\n\n\n\n
ations required per input bit. We can easily see that this is n H-gates and<\/p>\n\n\n\n
n(n \u2212 1)\/2 C-R-gates for n bits, which is O(n<\/p>\n\n\n\n
2<\/p>\n\n\n\n
). This is exponentially faster<\/p>\n\n\n\n
than the classical FFT which takes O(n2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
). Hurray for quantum algorithms!<\/p>\n\n\n\n
But before we exult too much, observe that the output of the quantum<\/p>\n\n\n\n
Fourier transform is a superposition of basis states whose phases represent the<\/p>\n\n\n\n
Fourier transform of the corresponding input bit. A measurement at the end of<\/p>\n\n\n\n
the above circuit gives us no information whatsoever about the Fourier trans-<\/p>\n\n\n\n
form of the input! So we cannot use this circuit as a super-e\ufb03cient Fourier<\/p>\n\n\n\n
transform computer! Instead, we have to incorporate it in procedures that re-<\/p>\n\n\n\n
quire FT-dependent phases. And Peter Shor did just that in his path-breaking<\/p>\n\n\n\n
algorithm for prime factorization.<\/p>\n\n\n\n
8.5.1 Period-\ufb01nding using QFT<\/p>\n\n\n\n
Preliminary to the Shor algorithm, let\u2019s focus on one that lends itself<\/p>\n\n\n\n
naturally to the QFT: computing the period r of a periodic n-bit function<\/p>\n\n\n\n
f : {0, 1}<\/p>\n\n\n\n
n<\/p>\n\n\n\n
7\u2192 {0, 1}<\/p>\n\n\n\n
n<\/p>\n\n\n\n
such that f(x + r) = f(x), r \u2208 [0, 2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\u2212 1]. (8.46)<\/p>\n\n\n\n
We will take 2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
= N in what follows. The function could repeat more than<\/p>\n\n\n\n
once in the interval [0, N \u2212 1], so we have<\/p>\n\n\n\n
f(x + kr) = f (x), kr < N.<\/p>\n\n\n\n
We assume we are presented with a black box (oracle) that evaluates such a<\/p>\n\n\n\n
function. The algorithm uses a circuit that is a direct extension of Simon\u2019s<\/p>\n\n\n\n
algorithm (Section 8.3), in which we\u2019ll use the full QFT instead of the 1-bit<\/p>\n\n\n\n
version (the Hadamard transform) used there. The circuit (Figure 8.11) is<\/p>\n\n\n\n
straightforward.<\/p>\n\n\n\n
|0i<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\/<\/p>\n\n\n\n
n<\/p>\n\n\n\n
H<\/p>\n\n\n\n
\u2297n<\/p>\n\n\n\n
U<\/p>\n\n\n\n
f<\/p>\n\n\n\n
\/<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\u02c6<\/p>\n\n\n\n
F<\/p>\n\n\n\n
N<\/p>\n\n\n\n
\/<\/p>\n\n\n\n
n<\/p>\n\n\n\n
|0i<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\/<\/p>\n\n\n\n
n<\/p>\n\n\n\n
|\u03c8<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i |\u03c8<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i<\/p>\n\n\n\n
FIGURE 8.11: Circuit for quantum period \ufb01nding.<\/p>\n\n\n\n
<\/p>\n\n\n\n
162 Introduction to Quantum Physics and Information Processing<\/p>\n\n\n\n
The input to the U<\/p>\n\n\n\n
f<\/p>\n\n\n\n
black box is once again<\/p>\n\n\n\n
|\u03c8<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
N<\/p>\n\n\n\n
N\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
x=0<\/p>\n\n\n\n
|xi<\/p>\n\n\n\n
n<\/p>\n\n\n\n
\u2297 |0i<\/p>\n\n\n\n
n<\/p>\n\n\n\n
, (8.47)<\/p>\n\n\n\n
So the output ought to be<\/p>\n\n\n\n
|\u03c8<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
N<\/p>\n\n\n\n
N\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
x=0<\/p>\n\n\n\n
|xi \u2297 |f(x)i. (8.48)<\/p>\n\n\n\n
We will again assume that we measure the lower register at this point, ob-<\/p>\n\n\n\n
taining some number f<\/p>\n\n\n\n
0<\/p>\n\n\n\n
. Then the top register collapses to a superposition of<\/p>\n\n\n\n
only those states |xi for which f(x) = f<\/p>\n\n\n\n
0<\/p>\n\n\n\n
. All such x\u2019s are of the form x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
+ kr<\/p>\n\n\n\n
for some x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
< r, and some integer k : kr < N. Suppose the number of periods<\/p>\n\n\n\n
within the interval [0, N \u2212 1] is p:<\/p>\n\n\n\n
p = [N\/r] , (8.49)<\/p>\n\n\n\n
where the square bracket notation stands for the ceiling function (greatest<\/p>\n\n\n\n
integer less than the argument). The state of the computer is then a superpo-<\/p>\n\n\n\n
sition of p terms of the form<\/p>\n\n\n\n
|\u03c8<\/p>\n\n\n\n
1<\/p>\n\n\n\n
i =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
p<\/p>\n\n\n\n
p\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
k=0<\/p>\n\n\n\n
|x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
+ kri \u2297 |f<\/p>\n\n\n\n
0<\/p>\n\n\n\n
i. (8.50)<\/p>\n\n\n\n
Now subjecting the top register to a QFT, we get<\/p>\n\n\n\n
\u02c6<\/p>\n\n\n\n
F<\/p>\n\n\n\n
N<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
p<\/p>\n\n\n\n
p\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
k=0<\/p>\n\n\n\n
|x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
+ kri<\/p>\n\n\n\n
!<\/p>\n\n\n\n
=<\/p>\n\n\n\n
N\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
y=0<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
Np<\/p>\n\n\n\n
p\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
k=0<\/p>\n\n\n\n
e<\/p>\n\n\n\n
2\u03c0i(x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
+kr)y\/N<\/p>\n\n\n\n
!<\/p>\n\n\n\n
|yi. (8.51)<\/p>\n\n\n\n
This is a superposition of basis states with a probability of occurrence of a<\/p>\n\n\n\n
particular y given by the mod-squared of the term in the brackets:<\/p>\n\n\n\n
P(y) =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
Np<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
p\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
k=0<\/p>\n\n\n\n
e<\/p>\n\n\n\n
2\u03c0i(x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
+kr)\/N<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
2<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
Np<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
p\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
k=0<\/p>\n\n\n\n
e<\/p>\n\n\n\n
2\u03c0ikry\/N<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(8.52)<\/p>\n\n\n\n
So y has an r-dependent probability of occurrence. The crux of this algorithm<\/p>\n\n\n\n
is that the most probable value of y gives us enough information about r for<\/p>\n\n\n\n
us to compute it. In fact, the claim is that the values of y that are measured<\/p>\n\n\n\n
are close to an integer multiple of N\/r.<\/p>\n\n\n\n
Let\u2019s \ufb01rst see this in the special case when there are exactly integer number<\/p>\n\n\n\n
of periods in the interval [0, N \u2212 1], i.e., when<\/p>\n\n\n\n
p =<\/p>\n\n\n\n
N<\/p>\n\n\n\n
r<\/p>\n\n\n\n
.<\/p>\n\n\n\n
We will compare the probability of y for mp when m is some integer, and<\/p>\n\n\n\n
when not:<\/p>\n\n\n\n
P(y) =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
r<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
1<\/p>\n\n\n\n
p<\/p>\n\n\n\n
p\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
k=0<\/p>\n\n\n\n
e<\/p>\n\n\n\n
2\u03c0iky\/p<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
2<\/p>\n\n\n\n
. (8.53)<\/p>\n\n\n\n
P(y = mp) =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
r<\/p>\n\n\n\n
, (8.54)<\/p>\n\n\n\n
P(y 6= mp) =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
rp<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
p\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
k=0<\/p>\n\n\n\n
e<\/p>\n\n\n\n
ik\u03b8<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
2<\/p>\n\n\n\n
, where \u03b8 = 2\u03c0<\/p>\n\n\n\n
y<\/p>\n\n\n\n
p<\/p>\n\n\n\n
, (8.55)<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
rp<\/p>\n\n\n\n
2<\/p>\n\n\n\n
sin<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(p\u03b8\/2)<\/p>\n\n\n\n
sin<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(\u03b8\/2)<\/p>\n\n\n\n
= 0<\/p>\n\n\n\n
\ue000<\/p>\n\n\n\n
since p\u03b8 is an integer multiple of 2\u03c0<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
. (8.56)<\/p>\n\n\n\n
So the only values of y obtained in this case are integer multiples of N\/r.<\/p>\n\n\n\n
For a general function, it is highly unlikely that there are exactly integer<\/p>\n\n\n\n
numbers of periods in the interval [0, N \u22121]. Yet, the most probable values of<\/p>\n\n\n\n
y turn out to be close to integer multiples of N\/r! To see this, let us start by<\/p>\n\n\n\n
writing<\/p>\n\n\n\n
y = m<\/p>\n\n\n\n
N<\/p>\n\n\n\n
r<\/p>\n\n\n\n
+ \u03b4<\/p>\n\n\n\n
m<\/p>\n\n\n\n
, (8.57)<\/p>\n\n\n\n
where m is an integer and |\u03b4<\/p>\n\n\n\n
m<\/p>\n\n\n\n
| \u2264<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
. Let\u2019s substitute this in Equation 8.52:<\/p>\n\n\n\n
P(y) =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
Np<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
p\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
k=0<\/p>\n\n\n\n
e<\/p>\n\n\n\n
2\u03c0ikr(mN\/r+\u03b4<\/p>\n\n\n\n
m<\/p>\n\n\n\n
)\/N<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
2<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
Np<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
p\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
k=0<\/p>\n\n\n\n
e<\/p>\n\n\n\n
2\u03c0ikr\u03b4<\/p>\n\n\n\n
m<\/p>\n\n\n\n
\/N<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
\ue00c<\/p>\n\n\n\n
2<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
Np<\/p>\n\n\n\n
sin<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(p\u03b8<\/p>\n\n\n\n
m<\/p>\n\n\n\n
)<\/p>\n\n\n\n
sin<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\u03b8<\/p>\n\n\n\n
m<\/p>\n\n\n\n
, where \u03b8<\/p>\n\n\n\n
m<\/p>\n\n\n\n
=<\/p>\n\n\n\n
\u03c0r<\/p>\n\n\n\n
N<\/p>\n\n\n\n
\u03b4<\/p>\n\n\n\n
m<\/p>\n\n\n\n
. (8.58)<\/p>\n\n\n\n
Now since p is nearly N\/r, the numerator is nearly sin<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(\u03c0\u03b4<\/p>\n\n\n\n
m<\/p>\n\n\n\n
). Also, r\u03b4<\/p>\n\n\n\n
m<\/p>\n\n\n\n
\/N<\/p>\n\n\n\n
is very small, so the denominator is nearly \u03b8<\/p>\n\n\n\n
m<\/p>\n\n\n\n
\u223c \u03c0\u03b4<\/p>\n\n\n\n
m<\/p>\n\n\n\n
r\/N.<\/p>\n\n\n\n
Therefore,<\/p>\n\n\n\n
P(y) \u223c<\/p>\n\n\n\n
1<\/p>\n\n\n\n
Np<\/p>\n\n\n\n
sin<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(\u03c0\u03b4<\/p>\n\n\n\n
m<\/p>\n\n\n\n
)<\/p>\n\n\n\n
(\u03c0\u03b4<\/p>\n\n\n\n
m<\/p>\n\n\n\n
r\/N)<\/p>\n\n\n\n
2<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
r<\/p>\n\n\n\n
sin<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(\u03c0\u03b4<\/p>\n\n\n\n
m<\/p>\n\n\n\n
)<\/p>\n\n\n\n
(\u03c0\u03b4<\/p>\n\n\n\n
m<\/p>\n\n\n\n
)<\/p>\n\n\n\n
2<\/p>\n\n\n\n
. (8.59)<\/p>\n\n\n\n
Since \u03b4<\/p>\n\n\n\n
m<\/p>\n\n\n\n
< 1\/2, and<\/p>\n\n\n\n
sin \u03b8<\/p>\n\n\n\n
\u03b8<\/p>\n\n\n\n
\u2265<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\u03c0<\/p>\n\n\n\n
for 0 \u2264 \u03b8 \u2264 \u03c0\/2, (see Figure 8.12), we have<\/p>\n\n\n\n
P(y \u223c m\/r) \u2265<\/p>\n\n\n\n
4<\/p>\n\n\n\n
\u03c0<\/p>\n\n\n\n
2<\/p>\n\n\n\n
r<\/p>\n\n\n\n
. (8.60)<\/p>\n\n\n\n
![\"\"](\"https:\/\/learning.oreilly.com\/api\/v2\/epubs\/urn:orm:book:9781482238129\/files\/bgbd.png\")
<\/p>\n\n\n\n
164 Introduction to Quantum Physics and Information Processing<\/p>\n\n\n\n
FIGURE 8.12: Graph comparing sin \u03b8 and 2\u03b8\/\u03c0.<\/p>\n\n\n\n
There are r possible such y\u2019s, so the probability of any such y is greater<\/p>\n\n\n\n
than 4\/\u03c0<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\u223c 40%. This result is to be interpreted as saying that when we<\/p>\n\n\n\n
rerun the algorithm many times, with high probability we measure y\u2019s that<\/p>\n\n\n\n
are integer multiples of N\/r. Now from such numbers we can use classical<\/p>\n\n\n\n
algorithms to deduce r, most famously the Euclid algorithm for continued<\/p>\n\n\n\n
fractions. The period-\ufb01nding algorithm thus succeeds to a high probability.<\/p>\n\n\n\n
Such analyses of the probability of obtaining good results are a common<\/p>\n\n\n\n
feature of most known quantum algorithms.<\/p>\n\n\n\n
Box 8.3: Finding r Given N\/r: Continued Fractions<\/p>\n\n\n\n
The output y of a run of the period-\ufb01nding algorithm is close to an integer<\/p>\n\n\n\n
multiple of N\/r. Consider the number x = y\/N \u223c m\/r. We now look at the<\/p>\n\n\n\n
continued fraction expansion of x:<\/p>\n\n\n\n
x = c<\/p>\n\n\n\n
0<\/p>\n\n\n\n
+<\/p>\n\n\n\n
1<\/p>\n\n\n\n
x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
= c<\/p>\n\n\n\n
0<\/p>\n\n\n\n
+<\/p>\n\n\n\n
1<\/p>\n\n\n\n
c<\/p>\n\n\n\n
1<\/p>\n\n\n\n
+<\/p>\n\n\n\n
1<\/p>\n\n\n\n
x<\/p>\n\n\n\n
2<\/p>\n\n\n\n
= c<\/p>\n\n\n\n
0<\/p>\n\n\n\n
+<\/p>\n\n\n\n
1<\/p>\n\n\n\n
c<\/p>\n\n\n\n
1<\/p>\n\n\n\n
+<\/p>\n\n\n\n
1<\/p>\n\n\n\n
c<\/p>\n\n\n\n
2<\/p>\n\n\n\n
+<\/p>\n\n\n\n
1<\/p>\n\n\n\n
x<\/p>\n\n\n\n
3<\/p>\n\n\n\n
= \u00b7\u00b7\u00b7 (8.61)<\/p>\n\n\n\n
= c<\/p>\n\n\n\n
0<\/p>\n\n\n\n
+<\/p>\n\n\n\n
1<\/p>\n\n\n\n
c<\/p>\n\n\n\n
1<\/p>\n\n\n\n
+<\/p>\n\n\n\n
1<\/p>\n\n\n\n
c<\/p>\n\n\n\n
2<\/p>\n\n\n\n
+<\/p>\n\n\n\n
1<\/p>\n\n\n\n
c<\/p>\n\n\n\n
3<\/p>\n\n\n\n
+ \u00b7\u00b7\u00b7<\/p>\n\n\n\n
(8.62)<\/p>\n\n\n\n
At each stage of the expansion (Equations 8.61), c<\/p>\n\n\n\n
i<\/p>\n\n\n\n
is the integer part of<\/p>\n\n\n\n
the denominator x<\/p>\n\n\n\n
i<\/p>\n\n\n\n
from the previous stage, and each x<\/p>\n\n\n\n
i<\/p>\n\n\n\n
, known as the i<\/p>\n\n\n\n
th<\/p>\n\n\n\n
partial sum, is a fraction \u2208 [0, 1]. To \ufb01nd the fractional expression for<\/p>\n\n\n\n
1<\/p>\n\n\n\n
x<\/p>\n\n\n\n
i<\/p>\n\n\n\n
,<\/p>\n\n\n\n
Euclid\u2019s GCD algorithm can be used. Equation 8.62 is the continued fraction<\/p>\n\n\n\n
expansion of x. If x is a rational number then the continued fraction expansion<\/p>\n\n\n\n
terminates after a \ufb01nite number of steps. For n-bit m and r, it turns out that<\/p>\n\n\n\n
the continued fraction can be computed in O(n<\/p>\n\n\n\n
3<\/p>\n\n\n\n
) steps.<\/p>\n\n\n\n
Now there is a theorem (proved in [50], Appendix 4) stating that m\/r is<\/p>\n\n\n\n
<\/p>\n\n\n\n
Quantum Algorithms 165<\/p>\n\n\n\n
one of the partial sums x<\/p>\n\n\n\n
i<\/p>\n\n\n\n
of the continued fraction of x. r < N, and the<\/p>\n\n\n\n
best guess for r is the partial sum having the largest denominator less than<\/p>\n\n\n\n
N. This is tested out and if it is not the period then the we try again with a<\/p>\n\n\n\n
di\ufb00erent x.<\/p>\n\n\n\n
8.5.1.1 Shor\u2019s factorization algorithm<\/p>\n\n\n\n
The above algorithm for period \ufb01nding, due in some form to Peter Shor,<\/p>\n\n\n\n
is really the heart of the factorization algorithm. For the more curious, the<\/p>\n\n\n\n
relationship between factoring and period-\ufb01nding is through a series of mathe-<\/p>\n\n\n\n
matical results that we will outline here. (This section is purely for the purpose<\/p>\n\n\n\n
of completeness, and the results of pure mathematics used will not be derived<\/p>\n\n\n\n
or explained.)<\/p>\n\n\n\n
For a good understanding of what follows, one must be familiar with mod-<\/p>\n\n\n\n
ular algebra, that is algebra restricted to the range [0, N \u2212 1] by considering<\/p>\n\n\n\n
all results of algebraic operations as periodic with period N . Then \u201cmod N\u201d<\/p>\n\n\n\n
essentially means \u201cthe remainder after dividing the result by N\u201d. For example,<\/p>\n\n\n\n
addition mod 4 will mean 2 + 2 = 0 and 2 + 3 = 1.<\/p>\n\n\n\n
\u2022 If a is a random integer < N such that a and N are coprime, then it is<\/p>\n\n\n\n
possible to \ufb01nd an integer r \u2208 [1, N] such that<\/p>\n\n\n\n
a<\/p>\n\n\n\n
r<\/p>\n\n\n\n
mod N = 1.<\/p>\n\n\n\n
r is called the order of a in mod N .<\/p>\n\n\n\n
\u2022 For a with order r mod N, the function<\/p>\n\n\n\n
f(x) = a<\/p>\n\n\n\n
x<\/p>\n\n\n\n
mod N,<\/p>\n\n\n\n
is periodic with period r. To see how:<\/p>\n\n\n\n
f(x + r) = a<\/p>\n\n\n\n
x+r<\/p>\n\n\n\n
mod N = (a<\/p>\n\n\n\n
x<\/p>\n\n\n\n
mod N)(a<\/p>\n\n\n\n
r<\/p>\n\n\n\n
mod N)<\/p>\n\n\n\n
= a<\/p>\n\n\n\n
x<\/p>\n\n\n\n
mod N \u00d7 1 = f(x).<\/p>\n\n\n\n
Therefore, \ufb01nding the period of a function f(x) is the same as \ufb01nding<\/p>\n\n\n\n
the order of some integer coprime with N.<\/p>\n\n\n\n
\u2022 Now if N is a large integer, choose a random integer a coprime with N<\/p>\n\n\n\n
and \ufb01nd its order r using the period-\ufb01nding algorithm. Now if r is even<\/p>\n\n\n\n
then construct b = a<\/p>\n\n\n\n
r\/2<\/p>\n\n\n\n
.<\/p>\n\n\n\n
b<\/p>\n\n\n\n
2<\/p>\n\n\n\n
= 1 mod N<\/p>\n\n\n\n
=\u21d2 b<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\u2212 1 = 0 mod N<\/p>\n\n\n\n
So b \u00b11 must have factors common with N. If we \ufb01nd the GCDs of b \u00b11<\/p>\n\n\n\n
and N we have the prime factors of N!<\/p>\n","protected":false},"excerpt":{"rendered":"
The quantum Fourier transform (QFT) is simply the DFT operation on the amplitudes of a quantum state. The DFT matrix is unitary, and can therefore represent a quantum transformation. We can de\ufb01ne the QFT (order N = 2 n ) of an n-qubit basis state |xi by \u02c6 F N |xi = 1 \u221a N […]<\/p>\n","protected":false},"author":1,"featured_media":4042,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[497],"tags":[],"class_list":["post-4092","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-quantum-algorithms"],"jetpack_featured_media_url":"https:\/\/workhouse.sweetdishy.com\/wp-content\/uploads\/2024\/09\/algorithm-1.png","_links":{"self":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4092","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/comments?post=4092"}],"version-history":[{"count":3,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4092\/revisions"}],"predecessor-version":[{"id":4587,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4092\/revisions\/4587"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media\/4042"}],"wp:attachment":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media?parent=4092"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4092"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4092"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}