Introduction to Quantum Physics and Information Processing

158 Introduction to Quantum Physics and Information Processing

Exercise 8.3. Show how the DFT of a 6-d vector reduces to the DFT’s of the

even and odd indexed 3-d components.

8.4.2 Complexity of the classical FFT algorithm

Suppose the computation of DFT

N

requires T (N) basic operations. From

Equation 8.34, we see that this is related to T (N/2) since we need to evaluate

two DFT’s of order N/2 and also do N multiplications of the exponential

factors. Thus,

T (N ) = 2T (N/2) + O(N). (8.35)

Using this recursively to solve for T (N) one gets

T (N ) = O(N log

2

N). (8.36)

8.5 Definition of the QFT from Discrete Fourier Trans-

form

The quantum Fourier transform