# In quantum Fourier transform, why can any controlled $R_{k}$ gate be formed by two controlled-Not gate?

Controlled $$R_{k}$$ gates are implemented in the quantum Fourier transform as shown here:

Each of the $$R_{k}$$ on a qubit is in this matrix form: $$\begin{pmatrix}1 & 0 \\ 0 & e^{2\pi i/2^k}\end{pmatrix}$$

My question is: Why can each of these controlled $$R_{k}$$ gates, no matter what $$k$$ is, be produced by two controlled-Not gates? (I think the global phase can be ignored)

Let $|0_m\rangle$, $|1_m\rangle$ be the computational basis for qubit $m$. Also, denote $R_k^{(m)}$ the $R_k$ gate acting on qubit $m$ and $CR_k^{(m,n)}$ the controlled-$R_k$ gate acting on $m$ and using $n$ as ancilla.

Things are easier to see if you write down explicitly the action of $CR_k^{(m,n)}$ on qubits $m$ and $n$, using the action of $R_k^{(m)}$. We have: $$R_k^{(m)}|0_m\rangle = |0_m\rangle \\ R_k^{(m)}|1_m\rangle = e^{\frac{2\pi i}{2^k}}|1_m\rangle$$ and, for an arbitrary state $|\psi_{mn}\rangle = a_{00}|0_m 0_n\rangle + a_{10}|1_m 0_n\rangle + a_{01}|0_m 1_n\rangle + a_{11}|1_m 1_n\rangle$, $$CR_k^{(m,n)}|\psi_{mn}\rangle = a_{00}|0_m 0_n\rangle + a_{10}|1_m 0_n\rangle + a_{01}|0_m 1_n\rangle + a_{11}e^{\frac{2\pi i}{2^k}}|1_m 1_n\rangle$$ We want to construct $CR_k^{(m,n)}$ using the $CNOT^{(m,n)}$ gate that targets $m$ and has $n$ as ancilla. Let's write down the action of $CNOT^{(m,n)}$ on $|\psi_{mn}\rangle$: $$CNOT^{(m,n)}|\psi_{mn}\rangle = a_{00}|0_m 0_n\rangle + a_{10}|1_m 0_n\rangle + a_{11}|0_m 1_n\rangle + a_{01}|1_m 1_n\rangle$$ If we assume that there does exist some sequence of gates involving $CNOT^{(m,n)}$ that reproduces $CR_k^{(m,n)}$, it is pretty obvious that applying $CNOT^{(m,n)}$ only once will redistribute the $a_{10}$ and $a_{11}$ coefficients to the wrong basis states. This means that any equivalent gate sequence must apply $CNOT^{(m,n)}$ at least twice or, in general, an even number of times. Fortunately there is at least one sequence that reproduces $CR_k^{(m,n)}$ using $CNOT^{(m,n)}$ only twice.

However, by itself $CNOT^{(m,n)}$ does not help much, since it cannot produce the needed phase factor in the last term of $|\psi_{mn}\rangle$. The only way to get the phase is to apply $R_k^{(m)}$ before $CNOT^{(m,n)}$ because we need to attach said phase to the correct $a_{11}$ coefficient. In other words, the sequence for $CR_k^{(m,n)}$ must also contain at least one factor $R_k^{(m)}$, not only the two factors of $CNOT^{(m,n)}$. It turns out that the minimal sequence uses not $R_k$, but $R_{k+1}$, and does so three times: twice on $m$ and once on $n$.

The reason is that the action of $R_k^{(m)}$ on $|\psi_{mn}\rangle$ reads $$R_k^{(m)}|\psi_{mn}\rangle = a_{00}|0_m 0_n\rangle + a_{10}e^{\frac{2\pi i}{2^k}}|1_m 0_n\rangle + a_{01}|0_m 1_n\rangle + a_{11}e^{\frac{2\pi i}{2^k}}|1_m 1_n\rangle$$ and we must find a way to get rid of the extra phase attached to $a_{10}$. One way to do this is to take $$CR_k^{(m,n)} = CNOT^{(m,n)} \left( R_{k+1}^{(m)} \right)^\dagger CNOT^{(m,n)} R_{k+1}^{(n)} R_{k+1}^{(m)}$$

Let's check that it works: $$CNOT^{(m,n)} \left( R_{k+1}^{(m)} \right)^\dagger CNOT^{(m,n)} R_{k+1}^{(n)} R_{k+1}^{(m)}|\psi_{mn}\rangle = \\ = CNOT^{(m,n)} \left( R_{k+1}^{(m)} \right)^\dagger CNOT^{(m,n)} R_{k+1}^{(n)}\left[ a_{00}|0_m 0_n\rangle + a_{10}e^{\frac{2\pi i}{2^{k+1}}}|1_m 0_n\rangle + a_{01}|0_m 1_n\rangle + a_{11}e^{\frac{2\pi i}{2^{k+1}}}|1_m 1_n\rangle \right] =\\ = CNOT^{(m,n)} \left( R_{k+1}^{(m)} \right)^\dagger CNOT^{(m,n)} \left[ a_{00}|0_m 0_n\rangle + a_{10}e^{\frac{2\pi i}{2^{k+1}}}|1_m 0_n\rangle + e^{\frac{2\pi i}{2^{k+1}}}a_{01}|0_m 1_n\rangle + a_{11}e^{\frac{2\pi i}{2^{k+1}}+\frac{2\pi i}{2^{k+1}}}|1_m 1_n\rangle \right] = \\ = CNOT^{(m,n)} \left( R_{k+1}^{(m)} \right)^\dagger \left[ a_{00}|0_m 0_n\rangle + a_{10}e^{\frac{2\pi i}{2^{k+1}}}|1_m 0_n\rangle + e^{\frac{2\pi i}{2^k}}a_{11}|0_m 1_n\rangle + a_{01}e^{\frac{2\pi i}{2^{k+1}}}|1_m 1_n\rangle \right] = \\ = CNOT^{(m,n)} \left[ a_{00}|0_m 0_n\rangle + a_{10}e^{-\frac{2\pi i}{2^{k+1}}} e^{\frac{2\pi i}{2^{k+1}}}|1_m 0_n\rangle + e^{\frac{2\pi i}{2^k}}a_{11}|0_m 1_n\rangle + a_{01}e^{-\frac{2\pi i}{2^{k+1}}} e^{\frac{2\pi i}{2^{k+1}}}|1_m 1_n\rangle \right] = \\ = CNOT^{(m,n)} \left[ a_{00}|0_m 0_n\rangle + a_{10}|1_m 0_n\rangle + e^{\frac{2\pi i}{2^k}}a_{11}|0_m 1_n\rangle + a_{01}|1_m 1_n\rangle \right] =\\ = a_{00}|0_m 0_n\rangle + a_{10}|1_m 0_n\rangle + a_{01}|0_m 1_n\rangle + e^{\frac{2\pi i}{2^k}}a_{11}|1_m 1_n\rangle = CR_k^{(m,n)}|\psi_{mn}\rangle$$

Q.e.d.

• Thanks. But it still needs unitary gate $R_{k+1}$. Is there any way to use just two CNOT to produce controlled-$R_{k}$ (ignoring global phase)? – Ka-Wa Yip Oct 18 '15 at 7:48
• Using 2 CNOT means using them in succession, which in terms of matrices means through multiplication. But as I pointed out, with just 2 CNOT there is no way to introduce the controlled & state-specific phase shift. Are you following Nielsen & Chuang's book? If so, what I provided in the answer is what they actually mean. You may want to check pg.3 in web.mit.edu/2.111/www/2010/ps5_2010Sol.pdf. The reason they focus only the CNOT is because they want to compare with classical algorithms formulated in terms of classical CNOT. Besides, phase shifts have no classical equivalent to boot. – udrv Oct 18 '15 at 8:03
• @kww What is meant by "using 2 CNOT gates" is that these are the only two-qubit gates required. You will still need additional 1-qubit gates. – Norbert Schuch Oct 18 '15 at 8:52
• Ok that's why I asked this question. I also feel that it is kind of impossible. – Ka-Wa Yip Oct 22 '15 at 9:20
• this question has been referenced on quantumcomputing.SE here – glS Oct 24 '19 at 9:57