= Solution
Use the convention
$$
\operatorname{QFT}_N|k\rangle
=\frac1{\sqrt N}\sum_{j=0}^{N-1}e^{2\pi ijk/N}|j\rangle.
$$
Changing the summation variable from $j$ to $j-1$ gives
$$
S\operatorname{QFT}_N|k\rangle
=e^{-2\pi ik/N}\operatorname{QFT}_N|k\rangle.
$$
Thus the Fourier-basis states are <eigenvector>[eigenvectors] of the cyclic shift, with respective <eigenvalue>[eigenvalues] $e^{-2\pi ik/N}$, and the <cyclic shift diagonalization by the quantum Fourier transform> is
$$
S=\operatorname{QFT}_N D\operatorname{QFT}_N^{-1},
\qquad
D|k\rangle=e^{-2\pi ik/N}|k\rangle.
$$
For $N=4$, write $k=2x+y$ with $x,y\in\{0,1\}$. Then
$$
e^{-2\pi ik/4}=e^{-i\pi x}e^{-i\pi y/2},
$$
so
$$
D=P(-\pi)\otimes P(-\pi/2),
\qquad
P(\theta)=\begin{pmatrix}1&0\\0&e^{i\theta}\end{pmatrix}.
$$
Hence the required <quantum circuit> applies, from input to output,
$$
\boxed{
\operatorname{QFT}_4^{-1}
\;\longrightarrow\;
P(-\pi)\otimes P(-\pi/2)
\;\longrightarrow\;
\operatorname{QFT}_4
}.
$$
The first phase gate acts on the most significant qubit $x$ and the second on the least significant qubit $y$.
Back to article page
