![\"\"](\"https:\/\/learning.oreilly.com\/api\/v2\/epubs\/urn:orm:book:9781482238129\/files\/bgb6.png\")
<\/p>\n\n\n\nApplications<\/p>\n\n\n\n
The Fourier transform, a mathematical tool named after the 18th century<\/p>\n\n\n\n
French mathematician Joseph Fourier, is an invaluable tool in engineering<\/p>\n\n\n\n
and the sciences. No technical education is complete without a \ufb01rm grasp<\/p>\n\n\n\n
of this technique and its uses. The simplest way to understand the Fourier<\/p>\n\n\n\n
transform F of a function f (x) is to imagine the function as made up of<\/p>\n\n\n\n
various components that are periodic (like a sine function) with a frequency<\/p>\n\n\n\n
y, and F(f(x)) as a function<\/p>\n\n\n\n
\u02dc<\/p>\n\n\n\n
f(y) measuring the amplitude of each frequency<\/p>\n\n\n\n
component in the function. In other words, we construct a decomposition<\/p>\n\n\n\n
of the function in terms of the oscillatory exponential e<\/p>\n\n\n\n
\u22122\u03c0iyx<\/p>\n\n\n\n
, where the<\/p>\n\n\n\n
coe\ufb03cients in that decomposition are the Fourier transform:<\/p>\n\n\n\n
f(x) =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2\u03c0<\/p>\n\n\n\n
Z<\/p>\n\n\n\n
\u221e<\/p>\n\n\n\n
\u2212\u221e<\/p>\n\n\n\n
dy e<\/p>\n\n\n\n
2\u03c0iyx<\/p>\n\n\n\n
\u02dc<\/p>\n\n\n\n
f(y). (8.19)<\/p>\n\n\n\n
This formula is said to de\ufb01ne the inverse Fourier transform of<\/p>\n\n\n\n
\u02dc<\/p>\n\n\n\n
f(y), while the<\/p>\n\n\n\n
Fourier transform is de\ufb01ned as<\/p>\n\n\n\n
F(f(x)) =<\/p>\n\n\n\n
\u02dc<\/p>\n\n\n\n
f(y) =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2\u03c0<\/p>\n\n\n\n
Z<\/p>\n\n\n\n
\u221e<\/p>\n\n\n\n
\u2212\u221e<\/p>\n\n\n\n
dx e<\/p>\n\n\n\n
\u22122\u03c0iyx<\/p>\n\n\n\n
f(x). (8.20)<\/p>\n\n\n\n
The factor in front of the integral captures the normalization. A function<\/p>\n\n\n\n
can in general have an in\ufb01nite number of frequency components, and the<\/p>\n\n\n\n
frequencies can be distributed continuously. That\u2019s how the Fourier transform<\/p>\n\n\n\n
is a continuous function of the frequency y.<\/p>\n\n\n\n
The two Equations 8.20 and 8.19 de\ufb01ne a Fourier transform pair. The<\/p>\n\n\n\n
Fourier transform naturally produces complex numbers, so that f(x) and<\/p>\n\n\n\n
\u02dc<\/p>\n\n\n\n
f(y)<\/p>\n\n\n\n
are in general complex. When we compute the Fourier transform on a digi-<\/p>\n\n\n\n
tal machine, we need to discretize the integral to get the Discrete Fourier<\/p>\n\n\n\n
Transform (DFT).<\/p>\n\n\n\n
8.4.1 The discrete Fourier transform and classical algorithm<\/p>\n\n\n\n
When f(x) is a discrete function over the \ufb01nite range N = 2<\/p>\n\n\n\n
n<\/p>\n\n\n\n
of discrete n-<\/p>\n\n\n\n
bit inputs x, we can think of it as a vector with N components {f<\/p>\n\n\n\n
0<\/p>\n\n\n\n
f<\/p>\n\n\n\n
1<\/p>\n\n\n\n
… f<\/p>\n\n\n\n
N\u22121<\/p>\n\n\n\n
}.<\/p>\n\n\n\n
The integral over x in Equation 8.20 is then a sum over an index k with<\/p>\n\n\n\n
<\/p>\n\n\n\n
154 Introduction to Quantum Physics and Information Processing<\/p>\n\n\n\n
x \u2192 k\/N and the limits are restricted from 0 to N \u2212 1. We then get the<\/p>\n\n\n\n
discrete Fourier transform of order N de\ufb01ned as<\/p>\n\n\n\n
\u02dc<\/p>\n\n\n\n
f(y) =<\/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
k=0<\/p>\n\n\n\n
e<\/p>\n\n\n\n
\u22122\u03c0iyk\/N<\/p>\n\n\n\n
f<\/p>\n\n\n\n
k<\/p>\n\n\n\n
.<\/p>\n\n\n\n
This is another vector with N components {g<\/p>\n\n\n\n
0<\/p>\n\n\n\n
g<\/p>\n\n\n\n
1<\/p>\n\n\n\n
… g<\/p>\n\n\n\n
N\u22121<\/p>\n\n\n\n
}, given by<\/p>\n\n\n\n
g<\/p>\n\n\n\n
j<\/p>\n\n\n\n
=<\/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
k=0<\/p>\n\n\n\n
e<\/p>\n\n\n\n
\u22122\u03c0ijk\/N<\/p>\n\n\n\n
f<\/p>\n\n\n\n
k<\/p>\n\n\n\n
. (8.21)<\/p>\n\n\n\n
These are just the coe\ufb03cients of orthogonal harmonic components e<\/p>\n\n\n\n
2\u03c0ijk\/N<\/p>\n\n\n\n
of<\/p>\n\n\n\n
the function, which can be expressed as the inverse discrete Fourier transform<\/p>\n\n\n\n
(IDFT):<\/p>\n\n\n\n
f<\/p>\n\n\n\n
k<\/p>\n\n\n\n
=<\/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
j=0<\/p>\n\n\n\n
e<\/p>\n\n\n\n
2\u03c0ijk\/N<\/p>\n\n\n\n
g<\/p>\n\n\n\n
j<\/p>\n\n\n\n
. (8.22)<\/p>\n\n\n\n
We can regard the DFT as a complex matrix transformation of the vector<\/p>\n\n\n\n
{f<\/p>\n\n\n\n
k<\/p>\n\n\n\n
}:<\/p>\n\n\n\n
g<\/p>\n\n\n\n
j<\/p>\n\n\n\n
=<\/p>\n\n\n\n
N\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
k=0<\/p>\n\n\n\n
M<\/p>\n\n\n\n
jk<\/p>\n\n\n\n
f<\/p>\n\n\n\n
k<\/p>\n\n\n\n
; f<\/p>\n\n\n\n
k<\/p>\n\n\n\n
=<\/p>\n\n\n\n
N\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
j=0<\/p>\n\n\n\n
M<\/p>\n\n\n\n
\u22121<\/p>\n\n\n\n
jk<\/p>\n\n\n\n
g<\/p>\n\n\n\n
k<\/p>\n\n\n\n
, (8.23)<\/p>\n\n\n\n
where M<\/p>\n\n\n\n
jk<\/p>\n\n\n\n
are the elements of an N \u00d7 N matrix M given by<\/p>\n\n\n\n
M<\/p>\n\n\n\n
jk<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
N<\/p>\n\n\n\n
e<\/p>\n\n\n\n
2\u03c0ijk\/N<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
N<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
jk<\/p>\n\n\n\n
N<\/p>\n\n\n\n
. (8.24)<\/p>\n\n\n\n
Here \u03c9<\/p>\n\n\n\n
N<\/p>\n\n\n\n
= e<\/p>\n\n\n\n
2\u03c0i\/N<\/p>\n\n\n\n
is the N<\/p>\n\n\n\n
th<\/p>\n\n\n\n
root of unity. More explicitly,<\/p>\n\n\n\n
\uf8eb<\/p>\n\n\n\n
\uf8ec<\/p>\n\n\n\n
\uf8ec<\/p>\n\n\n\n
\uf8ec<\/p>\n\n\n\n
\uf8ec<\/p>\n\n\n\n
\uf8ed<\/p>\n\n\n\n
g<\/p>\n\n\n\n
0<\/p>\n\n\n\n
g<\/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
g<\/p>\n\n\n\n
N\u22121<\/p>\n\n\n\n
\uf8f6<\/p>\n\n\n\n
\uf8f7<\/p>\n\n\n\n
\uf8f7<\/p>\n\n\n\n
\uf8f7<\/p>\n\n\n\n
\uf8f7<\/p>\n\n\n\n
\uf8f8<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
N<\/p>\n\n\n\n
\uf8ee<\/p>\n\n\n\n
\uf8ef<\/p>\n\n\n\n
\uf8ef<\/p>\n\n\n\n
\uf8ef<\/p>\n\n\n\n
\uf8ef<\/p>\n\n\n\n
\uf8ef<\/p>\n\n\n\n
\uf8ef<\/p>\n\n\n\n
\uf8ef<\/p>\n\n\n\n
\uf8f0<\/p>\n\n\n\n
1 1 1 \u00b7\u00b7\u00b7 1<\/p>\n\n\n\n
1 \u03c9<\/p>\n\n\n\n
N<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
2<\/p>\n\n\n\n
N<\/p>\n\n\n\n
\u00b7\u00b7\u00b7 \u03c9<\/p>\n\n\n\n
N\u22121<\/p>\n\n\n\n
N<\/p>\n\n\n\n
1 \u03c9<\/p>\n\n\n\n
2<\/p>\n\n\n\n
N<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
4<\/p>\n\n\n\n
N<\/p>\n\n\n\n
\u00b7\u00b7\u00b7 \u03c9<\/p>\n\n\n\n
2(N\u22121)<\/p>\n\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
.<\/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
1 \u03c9<\/p>\n\n\n\n
N\u22121<\/p>\n\n\n\n
N<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
2(N\u22121)<\/p>\n\n\n\n
N<\/p>\n\n\n\n
\u00b7\u00b7\u00b7 \u03c9<\/p>\n\n\n\n
(N\u22121)<\/p>\n\n\n\n
2<\/p>\n\n\n\n
N<\/p>\n\n\n\n
\uf8f9<\/p>\n\n\n\n
\uf8fa<\/p>\n\n\n\n
\uf8fa<\/p>\n\n\n\n
\uf8fa<\/p>\n\n\n\n
\uf8fa<\/p>\n\n\n\n
\uf8fa<\/p>\n\n\n\n
\uf8fa<\/p>\n\n\n\n
\uf8fa<\/p>\n\n\n\n
\uf8fb<\/p>\n\n\n\n
\uf8eb<\/p>\n\n\n\n
\uf8ec<\/p>\n\n\n\n
\uf8ec<\/p>\n\n\n\n
\uf8ec<\/p>\n\n\n\n
\uf8ec<\/p>\n\n\n\n
\uf8ed<\/p>\n\n\n\n
f<\/p>\n\n\n\n
0<\/p>\n\n\n\n
f<\/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
f<\/p>\n\n\n\n
N\u22121<\/p>\n\n\n\n
\uf8f6<\/p>\n\n\n\n
\uf8f7<\/p>\n\n\n\n
\uf8f7<\/p>\n\n\n\n
\uf8f7<\/p>\n\n\n\n
\uf8f7<\/p>\n\n\n\n
\uf8f8<\/p>\n\n\n\n
(8.25)<\/p>\n\n\n\n
Example 8.4.1. The simple case of N = 2, \u03c9<\/p>\n\n\n\n
2<\/p>\n\n\n\n
= e<\/p>\n\n\n\n
i\u03c0<\/p>\n\n\n\n
= \u22121 and<\/p>\n\n\n\n
DFT<\/p>\n\n\n\n
2<\/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
“<\/p>\n\n\n\n
1 1<\/p>\n\n\n\n
1 \u03c9<\/p>\n\n\n\n
2<\/p>\n\n\n\n
#<\/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
“<\/p>\n\n\n\n
1 1<\/p>\n\n\n\n
1 \u22121<\/p>\n\n\n\n
#<\/p>\n\n\n\n
(8.26)<\/p>\n\n\n\n
which is just the Walsh\u2013Hadamard transform.<\/p>\n\n\n\n
<\/p>\n\n\n\n
Quantum Algorithms 155<\/p>\n\n\n\n
Exercise 8.1. Write out the DFT matrix for N = 4.<\/p>\n\n\n\n
Exercise 8.2. Calculate the DFT on the N -dimensional zero-vector.<\/p>\n\n\n\n
Example 8.4.2. Unitarity of the DFT:<\/p>\n\n\n\n
The crucial point that allows us to extend the DFT to an operator on<\/p>\n\n\n\n
quantum states is that it is unitary. To prove this, we need to show that<\/p>\n\n\n\n
M<\/p>\n\n\n\n
\u2020<\/p>\n\n\n\n
M = =\u21d2<\/p>\n\n\n\n
N\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
l=0<\/p>\n\n\n\n
M<\/p>\n\n\n\n
jl<\/p>\n\n\n\n
M<\/p>\n\n\n\n
\u2217<\/p>\n\n\n\n
lk<\/p>\n\n\n\n
= \u03b4<\/p>\n\n\n\n
jk<\/p>\n\n\n\n
(8.27)<\/p>\n\n\n\n
where M<\/p>\n\n\n\n
jk<\/p>\n\n\n\n
is de\ufb01ned by Equation 8.24.<\/p>\n\n\n\n
When j = k :<\/p>\n\n\n\n
1<\/p>\n\n\n\n
N<\/p>\n\n\n\n
X<\/p>\n\n\n\n
l<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
jl<\/p>\n\n\n\n
N<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
\u2212lj<\/p>\n\n\n\n
N<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
N<\/p>\n\n\n\n
X<\/p>\n\n\n\n
l<\/p>\n\n\n\n
1 = 1; (8.28)<\/p>\n\n\n\n
When j 6= l, then<\/p>\n\n\n\n
P<\/p>\n\n\n\n
l<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
l(j\u2212k)<\/p>\n\n\n\n
N<\/p>\n\n\n\n
is the sum of N terms of a geometric series whose<\/p>\n\n\n\n
\ufb01rst term is 1 and ratio is \u03c9<\/p>\n\n\n\n
(j\u2212k)<\/p>\n\n\n\n
N<\/p>\n\n\n\n
. So we have<\/p>\n\n\n\n
X<\/p>\n\n\n\n
l<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
l(j\u2212k)<\/p>\n\n\n\n
N<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1 \u2212 \u03c9<\/p>\n\n\n\n
N(j\u2212k)<\/p>\n\n\n\n
N<\/p>\n\n\n\n
1 \u2212 \u03c9<\/p>\n\n\n\n
(j\u2212k)<\/p>\n\n\n\n
N<\/p>\n\n\n\n
= 0 (8.29)<\/p>\n\n\n\n
Thus Equation 8.27 is proved.<\/p>\n\n\n\n
Box 8.2: Classical FFT Algorithm<\/p>\n\n\n\n
Computing the DFT<\/p>\n\n\n\n
N<\/p>\n\n\n\n
of a vector involves evaluating N<\/p>\n\n\n\n
2<\/p>\n\n\n\n
elements of the<\/p>\n\n\n\n
DFT matrix, and looks like a job that scales as 2<\/p>\n\n\n\n
2n<\/p>\n\n\n\n
with the number of bits<\/p>\n\n\n\n
n = log<\/p>\n\n\n\n
2<\/p>\n\n\n\n
N. In implementing the DFT transform on a digital machine, one<\/p>\n\n\n\n
can easily optimize by exploiting the properties of the integer powers of \u03c9<\/p>\n\n\n\n
N<\/p>\n\n\n\n
.<\/p>\n\n\n\n
There are cycles among elements of DFT<\/p>\n\n\n\n
N<\/p>\n\n\n\n
, since \u03c9<\/p>\n\n\n\n
N<\/p>\n\n\n\n
N<\/p>\n\n\n\n
= 1. So while a direct<\/p>\n\n\n\n
matrix multiplication of the form of Equation 8.24 would typically require<\/p>\n\n\n\n
O(N<\/p>\n\n\n\n
2<\/p>\n\n\n\n
) basic operations, the optimized fast Fourier transform (FFT) algorithm<\/p>\n\n\n\n
requires O(N log<\/p>\n\n\n\n
2<\/p>\n\n\n\n
N) operations only.<\/p>\n\n\n\n
For example, consider N = 4; \u03c9<\/p>\n\n\n\n
4<\/p>\n\n\n\n
= e<\/p>\n\n\n\n
2\u03c0i\/4<\/p>\n\n\n\n
= i, \u03c9<\/p>\n\n\n\n
2<\/p>\n\n\n\n
4<\/p>\n\n\n\n
= \u22121, \u03c9<\/p>\n\n\n\n
4<\/p>\n\n\n\n
4<\/p>\n\n\n\n
= 1.<\/p>\n\n\n\n
DFT<\/p>\n\n\n\n
4<\/p>\n\n\n\n
=<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\uf8eb<\/p>\n\n\n\n
\uf8ec<\/p>\n\n\n\n
\uf8ec<\/p>\n\n\n\n
\uf8ec<\/p>\n\n\n\n
\uf8ed<\/p>\n\n\n\n
1 1 1 1<\/p>\n\n\n\n
1 i \u22121 \u2212i<\/p>\n\n\n\n
1 \u22121 1 \u22121<\/p>\n\n\n\n
1 \u2212i \u22121 i<\/p>\n\n\n\n
\uf8f6<\/p>\n\n\n\n
\uf8f7<\/p>\n\n\n\n
\uf8f7<\/p>\n\n\n\n
\uf8f7<\/p>\n\n\n\n
\uf8f8<\/p>\n\n\n\n
(8.30)<\/p>\n\n\n\n
<\/p>\n\n\n\n
156 Introduction to Quantum Physics and Information Processing<\/p>\n\n\n\n
Now there is a relationship between the upper and lower halves of this matrix.<\/p>\n\n\n\n
Look at the highlighted columns, repeated for the upper and lower halves: they<\/p>\n\n\n\n
form a 2 \u00d7 2 matrix that acts on the even index components (note the index<\/p>\n\n\n\n
starts at 0).<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
1 1<\/p>\n\n\n\n
1 \u22121<\/p>\n\n\n\n
!<\/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
DFT<\/p>\n\n\n\n
2<\/p>\n\n\n\n
. (8.31)<\/p>\n\n\n\n
The part that acts on the odd index components is for the upper half<\/p>\n\n\n\n
1<\/p>\n\n\n\n
2<\/p>\n\n\n\n
1 1<\/p>\n\n\n\n
i \u2212i<\/p>\n\n\n\n
!<\/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
1 0<\/p>\n\n\n\n
0 i<\/p>\n\n\n\n
!<\/p>\n\n\n\n
\u00d7 DFT<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(8.32)<\/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
Diag(1 \u03c9<\/p>\n\n\n\n
4<\/p>\n\n\n\n
) \u00d7 DFT<\/p>\n\n\n\n
2<\/p>\n\n\n\n
.<\/p>\n\n\n\n
The negative of this acts on the lower half. Thus the DFT of a 4-d vector is<\/p>\n\n\n\n
reduced to two DFT\u2019s of a 2-d vector. This is at the heart of the classical FFT<\/p>\n\n\n\n
algorithm.<\/p>\n\n\n\n
The above example shows that DFT<\/p>\n\n\n\n
N<\/p>\n\n\n\n
can be reduced to DFT<\/p>\n\n\n\n
N\/2<\/p>\n\n\n\n
. The<\/p>\n\n\n\n
FFT algorithm works by recursively dividing the original vector into even<\/p>\n\n\n\n
numbered and odd numbered elements, until at the \ufb01nal stage there are just<\/p>\n\n\n\n
two terms and DFT<\/p>\n\n\n\n
2<\/p>\n\n\n\n
can be applied. The process is then reversed by succes-<\/p>\n\n\n\n
sively doubling the vectors and eventually covering the entire input. Let\u2019s see<\/p>\n\n\n\n
how this is possible in general: let N = 2M .<\/p>\n\n\n\n
DFT<\/p>\n\n\n\n
N<\/p>\n\n\n\n
(f(x)) =<\/p>\n\n\n\n
\u02dc<\/p>\n\n\n\n
f(y) =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2M<\/p>\n\n\n\n
2M\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
x=0<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
xy<\/p>\n\n\n\n
2M<\/p>\n\n\n\n
f(x). (8.33)<\/p>\n\n\n\n
Breaking this up into even and odd terms,<\/p>\n\n\n\n
DFT<\/p>\n\n\n\n
2M<\/p>\n\n\n\n
(f(x)) =<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
2M<\/p>\n\n\n\n
M\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
x=0<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
2xy<\/p>\n\n\n\n
2M<\/p>\n\n\n\n
f(2x) +<\/p>\n\n\n\n
M\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
x=0<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
(2x+1)y<\/p>\n\n\n\n
2M<\/p>\n\n\n\n
f(2x + 1)<\/p>\n\n\n\n
!<\/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
\ue012<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
M<\/p>\n\n\n\n
M\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
x=0<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
xy<\/p>\n\n\n\n
M<\/p>\n\n\n\n
f(2x)<\/p>\n\n\n\n
| {z }<\/p>\n\n\n\n
DFT<\/p>\n\n\n\n
M<\/p>\n\n\n\n
of even terms<\/p>\n\n\n\n
+<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u221a<\/p>\n\n\n\n
M<\/p>\n\n\n\n
M\u22121<\/p>\n\n\n\n
X<\/p>\n\n\n\n
x=0<\/p>\n\n\n\n
\u03c9<\/p>\n\n\n\n
(x)y<\/p>\n\n\n\n
M<\/p>\n\n\n\n
f(2x + 1)<\/p>\n\n\n\n
| {z }<\/p>\n\n\n\n
DFT<\/p>\n\n\n\n
M<\/p>\n\n\n\n
of odd terms<\/p>\n\n\n\n
\u00d7\u03c9<\/p>\n\n\n\n
y<\/p>\n\n\n\n
2M<\/p>\n\n\n\n
\ue013<\/p>\n\n\n\n
(8.34)<\/p>\n\n\n\n
At any stage l of evaluating the DFT, one can divide the input into two<\/p>\n\n\n\n
to write it in terms of DFT<\/p>\n\n\n\n
l\/2<\/p>\n\n\n\n
, and continue successively until one is left with<\/p>\n\n\n\n
DFT<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\u2019s.<\/p>\n\n\n\n
Successive division of the terms in the input into two until we reach the<\/p>\n\n\n\n
two-term pairs is called decimation. The process of decimating higher-order<\/p>\n\n\n\n
DFT\u2019s looks like the following for N = 8:<\/p>\n\n\n\n
<\/p>\n\n\n\n
Quantum Algorithms 157<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
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
4<\/p>\n\n\n\n
x<\/p>\n\n\n\n
5<\/p>\n\n\n\n
x<\/p>\n\n\n\n
6<\/p>\n\n\n\n
x<\/p>\n\n\n\n
7<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
x<\/p>\n\n\n\n
2<\/p>\n\n\n\n
x<\/p>\n\n\n\n
4<\/p>\n\n\n\n
x<\/p>\n\n\n\n
6<\/p>\n\n\n\n
x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
x<\/p>\n\n\n\n
3<\/p>\n\n\n\n
x<\/p>\n\n\n\n
5<\/p>\n\n\n\n
x<\/p>\n\n\n\n
7<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
x<\/p>\n\n\n\n
4<\/p>\n\n\n\n
x<\/p>\n\n\n\n
2<\/p>\n\n\n\n
x<\/p>\n\n\n\n
6<\/p>\n\n\n\n
x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
x<\/p>\n\n\n\n
5<\/p>\n\n\n\n
x<\/p>\n\n\n\n
3<\/p>\n\n\n\n
x<\/p>\n\n\n\n
7<\/p>\n\n\n\n
x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
x<\/p>\n\n\n\n
4<\/p>\n\n\n\n
x<\/p>\n\n\n\n
2<\/p>\n\n\n\n
x<\/p>\n\n\n\n
6<\/p>\n\n\n\n
x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
x<\/p>\n\n\n\n
5<\/p>\n\n\n\n
x<\/p>\n\n\n\n
3<\/p>\n\n\n\n
x<\/p>\n\n\n\n
7<\/p>\n\n\n\n
even<\/p>\n\n\n\n
odd<\/p>\n\n\n\n
We then start evaluating upward from the 2-point DFTs, successively dou-<\/p>\n\n\n\n
bling at each stage. The generic 2-point DFT looks like Figure 8.8, called a<\/p>\n\n\n\n
butter\ufb02y diagram for its symmetric structure. The labels on the sides represent<\/p>\n\n\n\n
the multiplicative factors and two lines joined at a node represent addition of<\/p>\n\n\n\n
the corresponding terms.<\/p>\n\n\n\n
FIGURE 8.8: The 2-point DFT: butter\ufb02y diagram.<\/p>\n\n\n\n
For N = 8, we have worked out the decimation process in Example 8.4.4.<\/p>\n\n\n\n
The butter\ufb02y diagram looks like Figure 8.9.<\/p>\n\n\n\n
FIGURE 8.9: Butter\ufb02y diagram for computing an 8-point DFT.<\/p>\n\n\n\n
The output vector {y<\/p>\n\n\n\n
0<\/p>\n\n\n\n
y<\/p>\n\n\n\n
1<\/p>\n\n\n\n
. . . y<\/p>\n\n\n\n
8<\/p>\n\n\n\n
} is the DFT of the input vector.<\/p>\n","protected":false},"excerpt":{"rendered":"
Applications The Fourier transform, a mathematical tool named after the 18th century French mathematician Joseph Fourier, is an invaluable tool in engineering and the sciences. No technical education is complete without a \ufb01rm grasp of this technique and its uses. The simplest way to understand the Fourier transform F of a function f (x) is […]<\/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-4090","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\/4090","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=4090"}],"version-history":[{"count":2,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4090\/revisions"}],"predecessor-version":[{"id":4586,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4090\/revisions\/4586"}],"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=4090"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4090"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4090"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}