The Quantum Fourier Transform

Let us assume that we start with the state

$$\vert x>= \vert x_{N-1}>\vert x_{N-2}>...\vert x_1>\vert x_0>$$ (1)

which is the bit representation of the $N$ digit number $x$ with $x_0$ being th value of the least significant bit, and $x_{N-1}$ that value of the most significant bit. Thus the number $x$ is given by

$$x= \sum_{m=0}^{N-1} x_m 2^m$$ (2)

with the $x_m$ taking the values $0$ or 1. We now want to take this state to the state

$$F\vert x> = {1\over 2^{N/2}}\sum_k e^{i 2\pi k x 2^{-N}} \vert k_0...k_N>$$ (3)

where $k$ is the number represented by

$$k= \sum_{n=0}^{N-1} k_n 2^n$$ (4)

Note that we have reversed the representation for $k$ so that the least significant bit is represented by the first qubit state, and the most significant is represented by the last qubit state.

Now, the phase factor can be rewritten as

$$e^{i 2\pi k x 2^{-N}} = e^{i2\pi \sum^{N-1}_{n=0} k_n \sum_{m=0}^{N-1} x_m 2^{n+m-N}}$$

$$= e^{i 2\pi \sum_{n=0}^{N-1} k_n \sum_{m=0}^{N-1-n}x_m 2^{n+m-N}}$$ (5)

since $e^{i 2\pi 2^{n+m-N}}=1$ if $n+m-N\geq 0$. We thus notice that the phase for any given value of $n$ (ie the n-th least significant bit of k) depends only on the values of the bits of $x$ of order less that $N-1-n$. If we line up the bit representations of $k$ and $x$ we have

$x_{N-1}$	$x_{N-2}$	...	$x_{N-1-n}$	...	$x_1$	$x_0$
$k_0$	$k_1$	...	$k_n$	....	$k_{N-2}$	$k_{N-1}$

The Fourier factor which depends on $k_n$ is

$$e^{i 2\pi k_n \sum_{m=0}^{N-1-n}x_m 2^{n+m-N}}= e^{i 2\pi k_n \sum_{m=0}^{N-1-n} x_{N-1-n-m} 2^{-(m+1)}}$$ (6)

and depends only on those bits of the representation of $x$ which lie at or to the right of that bit in the representation of $k$. Furthermore, we note that in the factor which depends on $k_n$, the phase which depends on the largest $x$ bit, namely $x_{N-1-n}$ is $e^{i\pi k_n x_{N-1-n}}$ which has only values of plus or minus 1 .

We can now perform the Fourier Transform bit by bit starting with the lowest digit of $k$, namely $k_0$. Let me assume that we have managed to transform the state $\vert x>$ by replacing the $r-1$ highest digits of $x$ with the lowest $r-1$ digits of $k$. I.e., I have created, by some sequence of transformations, the state

$$\vert x>\rightarrow {1\over 2^{(r-1)/2}} \sum _{\{k_0..k_{... ..._{N-r-m} 2^{-(m+1)}} \vert k_0 k_1...k_{r-1}x_{N-1-r}...x_0>$$ (7)

I now show how to advance this to next stage where we will create the expression up to the $rth$ bit. . We can accomplish this by generating a transformation of the form

$$~ \vert k_0...k_{r-1} x_{N-1-r}...x_0>$$

$$\rightarrow {1\over \sqrt{2}} \vert k_0...k_{r-1}>\left(\sum_{k_r=0}^1 \left[... ...e^{i \pi k_r\sum_{m=1}^{N-1-r}x_{N-1-r-m} 2^{-m}}\right) \vert x_{N-r-2}...x_0>$$ (8)

This transformation can be decomposed into the two sets of transformations

$$~ \vert k_0...k_{r-1}>\vert x_{N-1-r}>\vert x_{N-r-2}...x_0>$$

$$\rightarrow {1\over \sqrt{2}}\vert k_0...k_{r-1}>\left(\sum_{k_r=0}^1 (-1)^{k_rx_{N-1-r}} \vert k_r>\right)\vert x_{N-r-2}...x_0>$$ (9)

and

$$~ \vert k_0...k_{r}>\vert x_{N-r-2}...x_0>$$

$$\rightarrow e^{i 2\pi k_r \sum_{m=1}^{N-1-r} x_{N-1-r-m} 2^{-m}}\vert k_0...k_{r}>\vert x_{N-r-2}...x_0>$$ (10)

The first transformation is just a $\pi/2$ rotation of the $r^{th}$ bit.

$$\vert> -> {1\over \sqrt{2}} (\vert>+\vert 1>)$$

$$\vert 1> -> {1\over \sqrt{2}} (\vert>-\vert 1>)$$ (11)

The second set just correspond to a series of controlled one bit phase rotations.

$$~ e{}^{i 2\pi k_r \sum_{m=1}^{N-1-r} x_{N-1-r-m} 2^{-(m+1)}}\vert k_0...k_{r}>\vert x_{N-r-2}...x_0>$$

$$= \vert k_0...k_{r}>\prod_{m=1}^{N-1-r} \left( e^{2\pi k_r x_{N-1-m-r} 2^{-(m+1)}} \vert x_{N-1-r-m}>\right)$$ (12)

I.e., these are transformations which phase rotate the $\vert x_{N-1-r-m}>$ bit depending on whether $\vert k_r>$ bit is one or zero.

Thus given the transform up to $r-1$ bits, it requires a single $\pi/2$ rotation of a single bit, and $N-r-1$ controlled single-bit phase rotations, for a total of $N-r$ operations. Thus the whole Fourier transformation requires $\sum_{r=0}^{N-1} (N-r)=N(N+1)/2$ operations ($N$, we recall is the number of bits in each of the numbers).

If we apply this Fourier transform to a state of the form

$$\vert\phi>= \sum_x \alpha_x \vert x>$$ (13)

we get for the Quantum Fourier Transform

$$QFT\vert\phi>= \sum_x\alpha_x \sum_k{1\over 2^{N/2}} e^{i 2\... ...left(\sum_x{1\over 2^{N/2}}e^{i\pi kx}\alpha_x\right) \vert k>$$ (14)

The term in the brackets is just the discrete Fourier transform of $\alpha_x$.

Note again that the representation $\vert k>$ is the bit reversed of the representation of $x$. While one could do a bit reversal operation to get $\vert k>$ into the same bit order as $\vert x>$, there is no point.