= Solution
Use the <quantum Fourier transform> convention $F_N|k\rangle=N^{-1/2}\sum_{j=0}^{N-1}\omega^{jk}|j\rangle$, where $\omega=e^{2\pi i/N}$. Reindexing the shifted sum gives
$$
S F_N|k\rangle=\frac1{\sqrt N}\sum_j\omega^{jk}|j+1\rangle=\omega^{-k}\frac1{\sqrt N}\sum_{\ell}\omega^{\ell k}|\ell\rangle.
$$
Thus the <cyclic shift operator> has these <eigenvectors>, with <eigenvalues> $e^{-2\pi i k/N}$. This is <cyclic shift diagonalization by the quantum Fourier transform>, and it implies $S=F_ND F_N^\dagger$ with $D|k\rangle=\omega^{-k}|k\rangle$.
For $N=4$, the binary encoding is $k=2x+y$, with $x$ the more significant <qubit>. The required diagonal phase is
$$
e^{-2\pi i(2x+y)/4}=(-1)^x(-i)^y,
$$
so $D=P_{-1}\otimes P_{-i}$. \b[The allowed-gate circuit is therefore]
$$
\boxed{S=\operatorname{QFT}_4(P_{-1}\otimes P_{-i})\operatorname{QFT}_4^{-1}.}
$$
In execution order, apply the inverse <QFT>, then the two <phase gates>, then the forward <QFT>. There is no extra global phase. Reversing the Fourier sign convention would conjugate both <phase gate> parameters.
Back to article page
