# Proof that the quantum Fourier transform is unitary

I'm trying to work through the proof that the quantum Fourier transform can be described by a unitary operator, i.e $F^{\dagger}F=\mathbb{1}$, where $$F=\frac{1}{\sqrt{N}}\sum_{j,k=0}^{N-1}\exp\left(\frac{2\pi ijk}{N}\right) |k\rangle\langle j |$$ and $$F^\dagger=\frac{1}{\sqrt{N}}\sum_{j,k=0}^{N-1}\exp\left(\frac{-2\pi ijk}{N}\right)|j\rangle\langle k |.$$

Together they give : $$F^{\dagger}F=\frac{1}{N}\sum_{j',k'j,k=0}^{N-1}\exp\left[\frac{2\pi i(j'k'-jk)}{N}\right]|j\rangle\langle k| k'\rangle\langle j' |.$$

Using $\langle k |k'\rangle = \delta_{k',k}$ and $\exp\left[\frac{2\pi i(j'-j)}{N}\right]=\delta_{j',j}$, The expression reduces to

$$F^{\dagger}F=\frac{1}{N}\sum_{j=0}^{N-1}|j\rangle\langle j|=\frac{1}{N} \mathbb I.$$

My question is: Shouldn't the factor of $\frac{1}{N}$ vanish somewhere? Or is the definition of a unitary operator $U^\dagger U \propto \mathbb{1}$ rather than $=\mathbb{1}$ ?

## 2 Answers

The error in the OP's question comes from the second Kronecker delta, which is not correct (furthermore, the sum over $k$ is not dealt with...). After using the first Kronecker delta $\delta_{k\,k'}$, one has to use the identity $$\frac{1}{N}\sum_{k=0}^{N-1}\exp{[\frac{2\pi i k(j'-j)}{N}]}=\delta_{j'\,j},$$ which directly gives that $F^\dagger F =1$.

One can easily check that the $1/N$ has to be included in the identity, since one is summing complex numbers of modulus one. Or equivalently, one trivialy sees that for $j=j'$, $$\frac{1}{N}\sum_{k=0}^{N-1} 1 = 1.$$

I don't believe it's true that $\langle k | k' \rangle = \delta_{k',k}$. If I recall correctly, the whole point of the $\frac{1}{\sqrt{N}}$ factor is to normalize the momentum eigenstates, so we should have $\langle k | k' \rangle = N\delta_{k',k}$.

• I'm sorry, in my efford to edit my question I edit yours instead. I apologise for my mistake, I reverted it back to your original answer. – PhotonBoom Dec 14 '14 at 18:05
• @PhotonicBoom No worries. – Alessandro Power Dec 14 '14 at 18:10