The Discrete Fourier Transform

The Fourier Transformation is a high level mathematical function using the integrals over a continuous wave to compute the component that make up such a wave. As this is done in a continuous fashion, the Discrete Fourier Transform(DFT) is not. The DFT uses the summation of real numbers representing points in time of wave motion. Which makes it an extremely powerful tool to computers because of their discrete nature.

This transformation is accomplished by computing the value of each signal component using every point in time chosen. Every signal value is made of a summation of all the points in time chosen with the value of the signal applied. This is done in the form of circle rotation. Euler’s formula allows us to recognize a basis of imaginary polar coordinates where $e^{ix} = cos(x) + sin(x)i$ , thus creating an arbitrary point in $R^2$ . This basis allows us to apply an exponential rotation to all of our points $x_n$ , where K is the signal component being evaluated and n is the point in time. After the transformation is complete we are left with a “list” containing all of the signal components of the original wave.

Written as:

$X_k = \LARGE {\sum_{n=0}^{N-1} x_n e^{-i2 \pi k \frac{n}{N}}}$

When the DFT is implemented on an algorithmic level it becomes quickly apparent that this runs at an $N^2$ time complexity belonging to $O(n^2)$ . That is because to compute every value K we must add together all of the point by point computations. Also, because of the discrete computation this algorithm is implemented using arrays. Where every index in array K is filled with the summation of points stored in array n. Finally, array K contains the value of every signal component spanned by the wave points chosen. While $O(n^2)$ isn’t inapplicable, the Fast Fourier Transform creates a one layer speed up in time complexity to reach $O(n \log n)$ .

The Fast Fourier Transform

The Fast Fourier Transform, or FFT, is a proven way to implement a substantial array transformation on a large amount of data, due to its time complexity of $O(n \log n)$ . This speed up was possible due to the amount of redundant calculations made by the Discrete Fourier Transform. These redundant calculations come from the periodic nature of imaginary numbers, where $i^t = -i^{4t}$ . Due to this property, by splitting the data up into even and odd indices, we are then able to apply the logarithmic time complexity. Using our original equation

$X_k = \LARGE {\sum_{n=0}^{N-1} x_n e^{-i2 \pi k \frac{n}{N}}}$ ,

and denoting $e^{-i2 \pi k \frac{n}{N}}$ as $W^{nk}_{N}$ . So we have

$X_k = \LARGE {\sum_{n=0}^{N-1} x_n W^{nk}_{N}}$ ,

Now that we’ve condensed the formula, it becomes possible to split between indices $2m$ and $2m+1$ , as halves of the array n respectively, to perform the Fourier transform as:

$X_k = \LARGE {\sum_{m=0}^{\frac{N}{2}-1} x_{2m} W^{2mk}_{N}} + \LARGE {\sum_{m=0}^{\frac{N}{2}-1} x_{2m+1} W^{(2m+1)k}_{N}}$

Now that the formula has been established and we are aware of the properties of W as

$W^{4k}_{8} = -W^{0k}_{8}$

$W^{5k}_{8} = -W^{1k}_{8}$

$W^{6k}_{8} = -W^{2k}_{8}$ …

$W^{mk}_{8} = -W^{(m-4)k}_{8}$

Where N is equal to 8.

We define the even summation of the FFT as $latex G[m] $ and the odd summation as $H[m]$ . Therefore we can see that:

$X_0 = G[0] + W^{0k}_{8}H[0]$

$X_1 = G[1] + W^{1k}_{8}H[1]$

$X_2 = G[2] + W^{2k}_{8}H[2]$ …

$X_4 = G[0] + W^{4k}_{8}H[0] = G[0] - W^{0k}_{8}H[0]$

$X_5 = G[1] + W^{5k}_{8}H[1] = G[1] - W^{1k}_{8}H[1]$

Given that the input is a power of 2, we can then perform the operation know as the decimating-in-time-algorithm. This is, recursively breaking down every set of transforms into even and odd inputs until only two point DFT’s remain. That is, $\frac{N}{2}$ point transformations, where we implement the recursion $\frac{N}{2}...\frac{N}{N/2}$ until hitting summations or arrays of length 1. At each stage of the algorithm $\frac{N}{2}$ complex operations are needed to build the previous level. Because of the stage construction in \log N, we only have to compute the summations of values themselves N, while recycling the complex computations.

Quantum Fourier Transform

Now that this basis has been firmly established and we have denoted the fastest time complexity of the Fourier transform using classical computing as $O(n \log n)$ , we can further use Quantum gate transformations to a achieve a time complexity such as $O(\log n)$ . Needless to say, this is an exponential speed up of an entire magnitude. To define the transform we first note that $X_k$ can also be defined as set of column matrices denoted as $X^{(s)}$ , where s the index of the “array”. We then form the formula as

$X^{(s)}_{j} = \LARGE {\sum_{n=0}^{N-1} P^{(s)}_{jk} X^{(s+1)}_{k}}$

While this may seem complex, it is important to realize this is a re-representation of the previously defined FFT formula in order to define $P^{(s)}$ as a form of column matrices. As we know from the previous post, qubits are defined as column vectors representing system state probability. If we can reform our input array to be represented as such then we can apply our gate matrices in order to introduce a state of superposition.

Following this the form of basis P is proven under a few propositions, however for the sake of this article we will assume the propositions as true while giving a brief explanation for each.

1. Each row of matrices $P^{(s)}$ only contains two non zero entries

In the matrices of $P^{(s)}$ we see that the non zero entries are located in the main diagonal and the sub-diagonal depending on the column values of $j$ . If we look at this a little closer it becomes clear why this. Putting at this in terms of a double array, if indices $i$ and j are equal at all times then we will receive only the diagonal values stored in the array and the same for our matrices. When $i = j$ we traverse all indices in the main diagonal of each matrix, when $i = j - 2$ we receive all entries in the lower sub-diagonal, and $i = j + 2$ yields all entries in the upper sub-diagonal. Because we assumed proposition one we can now say each matrix has been defined depending on the piece-wise function of the indices i and j.

2. The matrices of P are unitary

If you refer from the last post, unitary is defined as a square matrix where the conjugate transpose is also its inverse. Recall, we need this to be true in order to evaluate output transformations as we due input, in our time steps denoted by t. Subsequently, this allows these quantum gates to be implemented on a quantum computer. However, we must determine what these gates are first. We do this by whats called QR decomposition. The decomposition states that any matrix belonging to $P^{(s)}$ can be broken up into the product of a unitary matrix $M^{(s)}$ and an upper triangular matrix $N^{(s)}$ . This then brings us to our next proposition.

3. For any matrix s belonging to $P^{(s)}, s$ can be made up of the matrices $M^{(s)}$ and $N^{(s)}$

Because the depth of the proofs are being conceded right now, I am going to use proposition three in order to explain the mathematical composition of both $M^{(s)}$ and $N^{(s)}$ . Firstly, by multiplying the matrices M and N before traversing the matrix on the left side of the solution we can see that these sets of matrices build $P^{(s)}$ , such as

$\LARGE {(M^{(s)} N^{(s)})_{jk} = M^{(s)}_{jk} N^ {(s)}_{kk}} =P^{(s)}_{jj}$

We then denote that matrix $M^{(s)}$ can be written as its form of induction using the Identity $I$ and the Hadamard matrix H. By recursively using the formula $\LARGE {M^{(0)}_{2n \times 2n} = I^{\otimes (n-1)} \otimes H}$

for every matrix of matrices $M^{(s)}$ we can see this induction compose to

$\LARGE {M^{(s)}_{2n \times 2n} = M^{(s-1)}_{2n-1 \times 2n-1} \otimes I \otimes H}$

Thus, building every matrix belonging to $M^{(s)}$ and completing the unitary requirement of $P^{(s)}$

Lastly, we form our matrices of N as triangular matrices. This is simply the product of all triangular matrices in reverse using R at time $u = t - s + 1$ denoted by

$N^{(s)} = \LARGE {\prod_{t=s+1}^{n-1} P^{(s,t,u)}}$

Finally, we are able to build the Quantum Fourier Transform from the defined decomposition. We first prepare our quantum state as $\left|\varphi \right>$ and every complex matrix in $P^{(s)}$ such as,

$\left|\varphi_0 \right> = P^0, P^1......P^{(n-1)} \left|\varphi_n \right>$

Where $\left|\varphi_n \right>$ contains every value of the input $X^{(n)}$ in the form of ket complex matrices.

Thus we can say, $\left|\varphi_0 \right> = \sum_{c_{n-1} ... c_{0} < 1} X^0_{c_0... c_n-1} \left|c_{n-1} ... c_0 \right>$

The algorithm takes a complex array X as input and uses our quantum gates in $P^{(s)}$ to output a quantum state that correspond the probabilities of the real values and amplitudes, given by the original DFT. Thus, we prepare our quantum register of input as

$\left|\varphi_n \right> = \sum_{k = 0}^{N-1} X_k \left |k \right >$

We then move in reverse as an outer loop from $s = n -1 \rightarrow 0$

and as an inner loop from

$t = n -1 \rightarrow s + 1$ .

At every step in t, we apply our unitary gate operation of $N^{(s)}$ as

$R^{(s,t, t -s +1)}$

After applying the quantum gate operation to every matrix at step t, we apply the Hadamard matrix H to the value of $X^{(n)}$ at time step s.

After completing every matrix in the reverse time step of s, we have completed the algorithm, this yielding a quantum state $latex \left|\varphi_n \right> $ corresponding to elements of the complex matrix Y.

If we evaluate the time complexity of this transformation we see that the outer loop as $n(n+1)/2$ steps or equivalently $O(n^2)$ . We see that classically this is equal to the original DTF, however every qubit operation compounds the probabilistic superposition to $2^n bits$ . Due to this we can say that the operation becomes $O(log n)$ . This incredible exponential speed up becomes the driving factor of the algorithm and the reason it must be defined in terms of qubits and quantum space.

Written By: Mitchell Mesecher

Ars Geometrica

The Bowers/Taalman Research Lab in Discrete Geometry

Featured

Image: non-physically-based light transport through bubble cluster

On Representing Circles and Disks

Student Post: Sphere Packing Honors Thesis Proposal

New Paper: Rigidity of Circle Polyhedra in the 2-Sphere and of Hyperideal Polyhedra in Hyperbolic 3-Space

Student Post: The Quantum Fourier Transform

The Discrete Fourier Transform

The Fast Fourier Transform

Quantum Fourier Transform

Leave a Reply Cancel reply

The Discrete Fourier Transform

The Fast Fourier Transform

Quantum Fourier Transform

Share this:

Like this:

Related

Leave a Reply Cancel reply