# How Quantum Fourier Transform equal to Hadamard Transform on 4-by-4 matrix?

I just don't understand why $QFT_4$ become the same as Hadamard Transform $H_4$

The Hadamard matrix is as follwoing, $$H_2 = \frac12 \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 &-1 & 1\\ \end{pmatrix}$$

the Fourier matrix is as following,

$$H_2 = \frac12 \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i &-1 & i\\ \end{pmatrix}$$

I don't understand how on somehow some researchers says that they are doing the same job. Could you explain this to me.

Thank you

UPDATE:

I found that $QFT_2$ is the same as Hadamard gate $H_2$, hence this is why we can factor the $QFT_n$ into $H_2$ but we need to two extra gates for correctness, these are Phase shift gate and SWAP gate. [the user @udrv explained this with a good example for 2-qubit] so referring to my question the answer that $H_4$ is equal to $QFT_4$ is NO, except we enter extra gates.

• Who says this, and where? Can you give some references? – Norbert Schuch Nov 20 '15 at 15:25
• @NorbertSchuch see this paper (arxiv.org/pdf/1012.4583v1.pdf) on the last section, they give an example of two qubit to pass it through the network and take the measurement on the Hadamard basis (or Fourier basis for $|\sum | = 2$) so I thought there is some relationship between the two but they "author of the paper" explain much about this relationship; so makes me wonder whether we have a relationship between QFT and H in this case. – YOUSEFY Nov 21 '15 at 4:56
• Can you be more specific? Where exactly do you find the claim you claim? Also, it would make more sense to edit such things into the question rather than to make a comment. – Norbert Schuch Nov 21 '15 at 10:23

## 1 Answer

The discrepancy comes from the fact that there are different ways to define a quantum Fourier transform and the direct equivalence to the Hadamard transform holds for only one such definition. See for instance this Introduction to Quantum Computing.

Consider the general case of $N$ qubits, let the $2^N$ computational basis states be
$$|{\bf x}\rangle \equiv |x_1, x_2, x_3, ... ,x_N\rangle = |x_1\rangle \otimes |x_2\rangle \otimes |x_3\rangle \otimes ...|x_N\rangle \;\;\;\text{for} \;\;\; x_i = 0 \; \text{or} \; 1$$ and write an arbitrary state as $$|f \rangle = \sum_{{\bf x}}{f({\bf x})|{\bf x}\rangle}$$ The general definition of a quantum Fourier transform is $$|\hat{f}\rangle = \sum_{{\bf x}}{\hat{f}({\bf x})|{\bf x}\rangle}$$ where $$\hat{f}({\bf x}) = \frac{1}{2^{N/2}}\sum_{{\bf y}}{\chi_{{\bf y}}({\bf x}) f({\bf y})}$$ and for every ${\bf x}$ the numbers $\chi_{{\bf y}}({\bf x})$ are distinct $2^N$-th complex roots of the unit, $\left[\chi_{{\bf y}}({\bf x})\right]^{\left(2^N\right)} = 1$. The particular correspondence ${\bf x}, {\bf y} \rightarrow \chi_{{\bf y}}({\bf x})$ is formally introduced by means of a group representation on the computational basis states and the $\chi$-s represent group characters.

The choice of $\chi_{{\bf y}}({\bf x})$ for which the quantum Fourier transform is identical to a Hadamard transform corresponds to a direct discrete Fourier transform on the amplitudes $f({\bf x})$, $$\chi_{{\bf y}}({\bf x}) = (-1)^{{\bf x} \cdot {\bf y}}\\ \hat{f}({\bf x}) = \frac{1}{2^{N/2}}\sum_{{\bf y}}{(-1)^{{\bf x} \cdot {\bf y}} f({\bf y})}$$ In this case the transformation is a direct product of $N$ Hadamard transforms, $H_{2^N} = H_2\otimes H_2 \otimes ... \otimes H_2$. For $N=2$ this is $H_4 = H_2\otimes H_2$.

But the choice that reproduces the quantum Fourier transform in the question is $$\chi_{{\bf y}}({\bf x}) = e^{i\frac{2\pi\beta({\bf x})\beta({\bf y})}{2^N}} \\ \hat{f}({\bf x}) = \frac{1}{2^{N/2}}\sum_{{\bf y}}{e^{i\frac{2\pi\beta({\bf x})\beta({\bf y})}{2^N}} f({\bf y})}$$ which uses the binary map ${\bf x} \rightarrow \beta({\bf x}) \in \mathbb{N}$, $$\beta({\bf x}) = \sum_{k=0}^{N-1}{2^kx_k}$$ In this case the Hadamard transforms on individual qubits are each followed by a cascade of controlled phase-shifts on subsequent qubits:

For 2 qubits this becomes the circuit and matrix here.

• Thanks for your post, I have checked your example for 2 qubits, I have calculate all the possible ways for 2 qubits { 00, 01, 10, 11} I got a very long notation for each case, but when I want to try to do it using the matrix form (the one you posted it in your example) and I got different result. i.e. $|01\rangle$ should equal to the second column of the matrix, that is, $\frac12 \{ |00\rangle + i |01\rangle - |10\rangle - i|11\rangle \}$ However, when I multiply using Ket notation, I got different results $\frac12 \{ |00\rangle - i |01\rangle +i |10\rangle - i|11\rangle \}$ – YOUSEFY Nov 22 '15 at 10:24
• Ooops, sorry, there was a wrong minus sign in the exponent. For $|01\rangle$ I now have $\beta(01)=1$ and the entries from $\hat{f}({\bf x})$ as $(1/2) (e^0=1, e^{i\pi/2}=i, e^{i\pi}=-1, e^{3i\pi/2}=-i)$. Does it work now? – udrv Nov 22 '15 at 11:45
• Yes, it works fine... – YOUSEFY Nov 22 '15 at 20:55