# What is the relation between Hadamard transformation and QFT?

I am new to the field and I can't help having a feeling that Hadamard and Fourier Transform are somehow related, but it is not clear to me how.

Any explanation on how these two are related would be appreciated.

To summarize the relation in one line, the Hadamard Transform is essentially the Quantum Fourier Transform for the special case of a single qubit. Traditionally, the Quantum Fourier Transform $$U_{FT}$$ for $$n$$ qubits is defined as

$$U_{FT}|x\rangle_n = \frac{1}{2^{n/2}} \sum_{y=0}^{2^n - 1} e^{2 \pi i x y / 2^n}|y\rangle_n$$

However, this is not really the most general definition. The factor $$2^n$$ really comes from the fact that an $$n$$ qubit quantum system is essentially a $$2^n$$ dimensional quantum system. We can generalize this to a general $$d$$ level quantum system (also known as a qudit).

$$U_{FT}|x\rangle = \frac{1}{\sqrt{d}} \sum_{y=0}^{d - 1} e^{2 \pi i x y / d}|y\rangle$$

Here, $$|x\rangle, |y\rangle \in \{|0\rangle, |1\rangle, \dots |d-1\rangle\}$$. Now, the $$H$$ operator basically transfers between eigenvectors of the $$Z$$ and $$X$$ operators, that is $$H|0\rangle = |+\rangle$$ and $$H|+\rangle = |0\rangle$$ and similarly for $$|1\rangle$$ and $$|-\rangle$$. So, we may write

$$H = |+ \rangle\langle 0| + |- \rangle\langle 1|$$

So, before generalizing the $$H$$ operator to $$d$$ level systems, we will need to generalize the $$Z$$ and $$X$$ operators. The generalized version of the $$Z$$ operator (denoted $$Z_g$$, subscript $$g$$ for 'generalized') is written as

$$Z_g = \sum_{x=0}^{d-1} e^{2 \pi i x / d}| x\rangle\langle x|$$

It is easy to check that putting $$d = 2$$ reduces this to the familiar single qubit $$Z = |0 \rangle\langle 0| - |1 \rangle\langle 1|$$. We define the generalized version of the $$X$$ operator (denoted $$X_g$$) by

$$X_g|x\rangle = |x \oplus 1 \rangle$$

Here, $$\oplus$$ represents the cyclic right shift operator. It takes $$0$$ to $$1$$, $$1$$ to $$2$$, $$d - 1$$ to $$0$$ and so on. Again, it is easy to see that this mimics the familiar $$X|0\rangle = |1\rangle$$ and $$X|1\rangle = |0\rangle$$ when $$d = 2$$.

The eigenvectors of $$Z_g$$ are easily seen to be the computational basis $$\{|x\rangle\}_{x=0}^{d-1}$$ with corresponding eigenvalues $$e^{2 \pi i x / d}$$. The same is not as obvious for $$X_g$$, but a short and simple calculation (which I will leave to the reader) reveals the eigenvectors of $$X_g$$ to be

$$|\tilde{x}\rangle = \frac{1}{\sqrt{d}} \sum_{y=0}^{d - 1} e^{2 \pi i x y / d}|y\rangle$$

with corresponding eigenvalues $$e^{-2 \pi i x / d}$$. Since the $$H$$ Transform takes eigenvectors of the $$Z$$ operator to the eigenvectors of the $$X$$ operator, the generalized version of the $$H$$ Transform (denoted $$H_g$$) may be defined as

$$H_g|x\rangle = |\tilde{x}\rangle = \frac{1}{\sqrt{d}} \sum_{y=0}^{d - 1} e^{2 \pi i x y / d}|y\rangle$$

Now, this is just the Quantum Fourier Transform! It is worth pointing out that the above is a special case of the application of what is known as the Heisenberg-Weyl Operators. More details may be found in section 3.7 of Mark Wilde's textbook on Quantum Information Theory

• @Akonaire, Thank you for the kind explanation but I am a bit lost. here " Now, this is just the Quantum Fourier Transform!". If I look at 4x4 transformation of H vs. QFT, they look different right? Also, QFT circuit is not just made out of Hadarmard gates . Sorry I must have missed the important message here. Jun 4 at 20:28
• @JohnParker The H transform in the last line is not your familiar 2 x 2 H transform. It is the generalized version of H for d-level systems, so it is a d x d matrix. You can think of the QFT as a family of transforms defined on d-level systems (For qubits, d = 2). Every member of this family transforms the eigenvectors of the Z operator to the eigenvectors of the X operator. So d-level QFT transforms the eigenvectors of d-level generalized Z to that of d-level generalized X in much the same way as the 2-level H transforms the eigenvectors of 2-level Z to that of 2-level X. Jun 5 at 6:13