# How do you retrieve the Quantum Fourier Transform matrix from superposition expansion?

So I am trying to wrap my head around QFT working out the details. I have managed to retrieve the 2 qubit QFT matrix by expanding out the superposition of 2 qubits through QFT gate. I am now trying this for the 3 qubit case as follows:

$$\omega_{n}=e^{\frac{2\pi}{2^{n}}}$$

$$QFT |\Phi _{1} \Phi_{2} \Phi_{3}\rangle = |0\rangle+\omega_{1}^{\Phi _{1}}|1\rangle \otimes |0\rangle+\omega_{1}^{\Phi _{2}}\omega_{2}^{\Phi _{1}}|1\rangle\otimes|0\rangle+\omega_{1}^{\Phi _{3}}\omega_{2}^{\Phi _{2}}\omega_{3}^{\Phi _{1}}|1\rangle$$

$$=|000\rangle+\omega_{1}^{\Phi _{1}}|100\rangle+\omega_{1}^{\Phi _{2}}\omega_{2}^{\Phi _{1}}|010\rangle+\omega_{1}^{\Phi _{1}+\Phi _{2}}\omega_{2}^{\Phi _{1}}|110\rangle+\omega_{1}^{\Phi _{3}}\omega_{2}^{\Phi _{2}}\omega_{3}^{\Phi _{1}}|001\rangle+\omega_{1}^{\Phi _{1}+\Phi _{3}}\omega_{2}^{\Phi _{2}}\omega_{3}^{\Phi _{1}}|101\rangle+\omega_{1}^{\Phi _{2}+\Phi _{3}}\omega_{2}^{\Phi _{1}+\Phi _{2}}\omega_{3}^{\Phi _{1}}|011\rangle+\omega_{1}^{\Phi _{1}+\Phi _{2}+\Phi _{3}}\omega_{2}^{\Phi _{1}+\Phi _{2}}\omega_{3}^{\Phi _{1}}|111\rangle$$

And then I calculate the coefficients for each combination of $$\Phi_{1}\Phi_{1}\Phi_{1}$$:

$$QFT \begin{bmatrix} |000\rangle \\ |100\rangle \\ |010\rangle \\ |110\rangle \\ |001\rangle \\ |101\rangle \\ |011\rangle \\ |111\rangle \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & i & -i & ω & -ω & iω & -iω \\ 1 & 1 & -1 & -1 & i & i & -i & -i \\ 1 & -1 & -i & i & iω & -iω & ω & ω \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 \\ 1 & -1 & i & -i & -ω & ω & -iω & -iω \\ 1 & 1 & -1 & -1 & -i & -i & i & i \\ 1 & -1 & -i & i & -iω & iω & -ω & ω \\ \end{bmatrix}$$

But when I compare this with the matrix for $$QFT_{3}$$, it doesn't match. The periods for odd positions are not correct. For example, the period for 011 i get is $$[1 , i\omega , -i , \omega ,-1, -i\omega, i, -\omega]$$ when it should be $$[1 , i\omega , -i , \omega ,-1, -\omega, i, -i\omega]$$.

I have searched through for examples on the web but everyone seems to just end with shorthand expansion and I cannot figure out what I am doing wrong? Is this the correct way to retrieve the Fourier matrix?

• I'm not sure why you said "the period for 011 i get is [1,𝑖𝜔,−𝑖,𝜔,−1,−𝑖𝜔,𝑖,−𝜔] when it should be [1,𝑖𝜔,−𝑖,𝜔,−1,−𝜔,𝑖,−𝑖𝜔]". Shouldn't you be reading off the 2nd row from the bottom instead of 2nd column from the right? Feb 24, 2022 at 14:59
• I think because the periods should be read down the columns since each instance of phis is a column vector? Mar 2, 2022 at 14:03
• You've got your endianness backwards for seeing the pattern. Try rearranging so the second row is 001 not 100. Make the rows go 000, 001, 010, 011, 100, etc. Same for the columns. Nov 20, 2022 at 17:02

### Hack:

You could write the QFT matrix as below. Notice the exponents of $$\omega$$ are simply the elementary tables of 1,2,3,4 & so on across the columns in each row (except the first row and first column which are all 1s).

Here $$\omega=e^{2i\pi/8}$$

#### Step-1:

$$QFT = \frac{1}{\sqrt{8}} \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^{2} & \omega^{3} & \omega^{4} & \omega^{5} & \omega^{6} & \omega^{7} \\ 1 & \omega^{2} & \omega^{4} & \omega^{6} & \omega^{8} & \omega^{10} & \omega^{12} & \omega^{14} \\ 1 & \omega^{3} & \omega^{6} & \omega^{9} & \omega^{12} & \omega^{15} & \omega^{18} & \omega^{21} \\ 1 & \omega^{4} & \omega^{8} & \omega^{12} & \omega^{16} & \omega^{20} & \omega^{24} & \omega^{28} \\ 1 & \omega^{5} & \omega^{10} & \omega^{15} & \omega^{20} & \omega^{25} & \omega^{30} & \omega^{35} \\ 1 & \omega^{6} & \omega^{12} & \omega^{18} & \omega^{24} & \omega^{30} & \omega^{36} & \omega^{42} \\ 1 & \omega^{7} & \omega^{14} & \omega^{21} & \omega^{28} & \omega^{35} & \omega^{42} & \omega^{49} \\ \end{bmatrix}$$

#### Step-2:

This could further simplify by taking mod 8 ($$N=2^n=8, n=$$number of qubits).

$$QFT = \frac{1}{\sqrt{8}} \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^{2} & \omega^{3} & \omega^{4} & \omega^{5} & \omega^{6} & \omega^{7} \\ 1 & \omega^{2} & \omega^{4} & \omega^{6} & 1 & \omega^{2} & \omega^{4} & \omega^{6} \\ 1 & \omega^{3} & \omega^{6} & \omega & \omega^{4} & \omega^{7} & \omega^{2} & \omega^{5} \\ 1 & \omega^{4} & 1 & \omega^{4} & 1 & \omega^{4} & 1 & \omega^{4} \\ 1 & \omega^{5} & \omega^{2} & \omega^{7} & \omega^{4} & \omega & \omega^{6} & \omega^{3} \\ 1 & \omega^{6} & \omega^{4} & \omega^{2} & 1 & \omega^{6} & \omega^{4} & \omega^{2} \\ 1 & \omega^{7} & \omega^{6} & \omega^{5} & \omega^{4} & \omega^{3} & \omega^{2} & \omega \\ \end{bmatrix}$$

#### Step-3:

Further simplify the higher powers of $$\omega$$ using the fact that $$\omega^k = e^{2i\pi k/N} = cos(2\pi k / N) + i. sin(2\pi k / N)$$

Reference: If you are interested generating nicely formatted $$LaTeX$$ source for QFT matrix, check out this.