## Appendix B

**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 wave^{46}.

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 *y _{j}* is another complex vector

*Y*, also with

*n*elements

*Y*:

_{k}^{47}where* Ω* is a complex *n*-th root of unity given by

In matrix notation, the above Fourier transform can be expressed as

Y= Fy,

where the elements of the matrix *F* are given by

It can be shown that

which then allows us to invert the Fourier transform:

Hence

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 *2n ^{2}* 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 log*floating-point operations instead of in

_{2}n)*O(n*operations

^{2})^{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