Fourier series and analysis
The weirdness of quantum mechanics is that a quantum object shows both particle-like and wave-like behavior. An understanding of waves and Fourier analysis is therefore central to quantum computing.
In physics, all systems which oscillate harmonically are quantized in terms of their energy, whether these systems are material oscillators, sound waves, or electromagnetic waves. Since we see diverse systems interacting with each other, it follows that the quantization of any one type of harmonic oscillator will require a similar quantization of all other types. Reflection, refraction, interference, and diffraction are characteristic behaviors of all types of wave46.
Interference is the test for wave motion. In quantum mechanics, of primary interest are probability waves that give the probability amplitude of finding a particle at a given place—the so-called “matter waves”. Their frequency is proportional to the energy and their wave number is proportional to the momentum of the particle. Complex algebra amazingly allows us to calculate the striking interference effects seen in quantum phenomena. Fourier analysis allows us to estimate the period from a discrete set of values sampled at a fixed rate.
The finite, or discrete, Fourier transform of a complex vector y with n elements yj is another complex vector Y, also with n elements Yk47:
where Ω is a complex n-th root of unity given by
In matrix notation, the above Fourier transform can be expressed as
where the elements of the matrix F are given by
It can be shown that
which then allows us to invert the Fourier transform:
It is obvious that F√n is unitary. A direct application of the Fourier transform
requires n multiplications and n additions for each of the n components of Y for a total of 2n2 floating-point operations in addition to the operations required to generate the powers of Ω . Smart calculation strategies, generally known as fast-Fourier transform (FFT) algorithms are able to do the calculations in
O(n log2 n) floating-point operations instead of in O(n2) operations 48. The importance of Fourier analysis in quantum computing became evident once it was realized that quantum computers could perform a type of Fourier transform much faster than classical computers. This enabled many important quantum algorithms to be developed.
46 See: Wave Behavior, http://www.aktsunami.com/lessons/9-12/unit6/9-12_3WaveBehavior.pdf,
http://hyperphysics.phy-astr.gsu.edu/hbase/sound/p2032.html for an elementary school-level recap on waves; and
VanCleave (2006). VanCleave, J. P. Janice VanCleave’s Energy for Every Kid. Hoboken, Wiley & Sons, N.J. 2006.
47 See, e.g., MATLAB, Chapter 8, Fourier Analysis, http://www.mathworks.com/moler/fourier.pdf
48 See, e.g., Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. Numerical Recipes in C. Cambri.ge Press, Cambridge, Second Edition, 2002. https://www2.units.it/ipl/students_area/imm2/files/Numerical_Recipes.pdf