Exercise 5.1
Consider a transformation \(F\) defined as
(1)\[
F \equiv \sum_{j=0}^{N-1} \left[\sum_{k=0}^{N-1}\frac{1}{\sqrt{N}}\exp\left(2i\pi\frac{jk}{N}\right)|k\rangle\right]\langle j| = \sum_{j=0}^{N-1} |\tilde{j}\rangle\langle j|
\]
where basis \(\{|j\rangle\}\) and \(\{|k\rangle\}\) are different orthonormal basis set. Above transformation is the quantum Fourier transformation since for any basis vector \(|j\rangle\), it equivalently performs
(2)\[
|j\rangle \to|\tilde{j}\rangle = \sum_{k=0}^{N-1}\frac{1}{\sqrt{N}}\exp\left(2i\pi\frac{jk}{N}\right)|k\rangle
\]
To prove the transformation in eq. (1) is unitary, we have
(3)\[\begin{split}
\begin{align}
F^{\dagger}F &=\left[\sum_{j=0}^{N-1} |\tilde{j}\rangle\langle j|\right]^{\dagger}\left[\sum_{n=0}^{N-1} |\tilde{n}\rangle\langle n|\right] \\
&= \left[\sum_{j=0}^{N-1} |j\rangle\langle \tilde{j}|\right]^{\dagger}\left[\sum_{n=0}^{N-1} |\tilde{n}\rangle\langle n|\right] \\
&= \sum_{n,j} |j\rangle\langle \tilde{j}|\tilde{n}\rangle\langle n|
\end{align}
\end{split}\]
where \(|j\rangle\) and \(|n\rangle\) are different notation for same orthonormal basis. Then the inner product \(\langle \tilde{j}|\tilde{n}\rangle\) becomes
(4)\[\begin{split}
\begin{align}
\langle \tilde{j}|\tilde{n}\rangle &= \left[\sum_{k=0}^{N-1}\frac{1}{\sqrt{N}}\exp\left(-2i\pi\frac{jk}{N}\right)\langle k|\right]\left[\sum_{m=0}^{N-1}\frac{1}{\sqrt{N}}\exp\left(2i\pi\frac{nm}{N}\right)|m\rangle\right] \\
&= \frac{1}{N}\sum_{m,k} \exp\left(-2i\pi\frac{jk}{N}\right)\exp\left(2i\pi\frac{nm}{N}\right)\langle k|m\rangle \\
&= \frac{1}{N}\sum_{k=0}^{N-1} \exp\left(-2i\pi\frac{jk}{N}\right)\exp\left(2i\pi\frac{nk}{N}\right)\\
&= \frac{1}{N}\sum_{k=0}^{N-1} \exp\left[2i\pi\frac{(n-j)k}{N}\right]
\end{align}
\end{split}\]
where \(|k\rangle\) and \(|m\rangle\) are different notations for same orthonormal basis. Note that
(5)\[\begin{split}
\begin{align}
\exp\left[2i\pi\frac{(n-j)(k+1)}{N}\right] &= \exp\left[2i\pi\frac{(n-j)k}{N}+2i\pi\frac{(n-j)}{N}\right] \\
&= \exp\left[2i\pi\frac{(n-j)k}{N}\right]\exp\left[2i\pi\frac{(n-j)}{N}\right]
\end{align}
\end{split}\]
so we can use geometry series to compute the sum in eq. (4) with common ratio \(r=\exp[2i\pi(n-j)/N]\), then
(6)\[\begin{split}
\begin{align}
\langle \tilde{j}|\tilde{n}\rangle &= \frac{1}{N}\sum_{k=0}^{N-1} \exp\left[2i\pi\frac{(n-j)k}{N}\right]\\
&= \frac{1}{N} \frac{1-r^{N}}{1-r} \\
&= \frac{1}{N} \frac{1-\exp[2i\pi(n-j)]}{1-\exp[2i\pi(n-j)/N]} \\
\end{align}
\end{split}\]
Then from above calculation,
for \(r = 1\), we have \(n = j\) and \(\langle \tilde{j}|\tilde{n}\rangle = 1\),
for any \(r\neq 1\) we have \(n\neq j\) but \(n - j\) is a integer. Since
(7)\[
\exp[2i\pi(n-j)] = \cos[2\pi(n-j)] + i\sin[2\pi(n-j)]
\]
For any \(n - j\) as integer, \(\cos[2\pi(n-j)]\) is always \(1\) and \(\sin[2\pi(n-j)]\) is always \(0\), so \(\exp[2i\pi(n-j)] = 1\) for \(\forall n, j\). Meanwhile, \((n-j)/N \neq\) so \(\exp[2i\pi(n-j)/N] \neq 1\) and the denominator will not be \(1\). In this case, \(\langle \tilde{j}|\tilde{n}\rangle = 0\).
In conclusion, we have \(\langle \tilde{j}|\tilde{n}\rangle = \delta_{jn}\) so \(F^{\dagger}F = \sum_{n,j} \delta_{jn}|j\rangle\langle n|\) which is an identity under the matrix representation of \(\{|j\rangle\}\), the basis before transformation. Then we can conclude that the Fourier transformation is unitary.
**Question: **Is above result basis dependent?