Constructing a controlled phase gate from given gates

Question

As part of a project in a quantum computing course we were asked to classically simulate the quantum phase estimation algorithm, which has inverse QFT as one of its components. On the Wikipedia page of QFT, the quantum circuit implementation presented uses a controlled version of the phase gate $$R_N = \begin{pmatrix}1 & 0\\ 0 & \omega_{N} \end{pmatrix}$$ with $\omega_N=e^{2\pi i/N}$. However, in the instructions of the project we are instructed to only use the single-qubit gates in the set $\{X,Z,S,T,H\}$, the 2-qubit gates $\{CNOT,SWAP\}$ and the 3-qubit Toffoli gate.

My question is - is there a way to construct a circuit that calculates controlled-$R_N$ using only the given gates?

Answer 1

What you're asking for cannot be done exactly. Instead, you will have to define a level of acceptable accuracy and find a sequence of gates that approximates the one you want within that accuracy.

A good starting point is the following circuit: If you work though it's action, you'll find that this is (almost) the controlled-phase that you want. (I think you also need a phase gate on the top qubit). So, then it's just a case of decomposing the phase rotations in terms of $H$ and $T$ to your desired accuracy (you'll want them each accurate to $\epsilon/2$ in order to ensure overall $\epsilon$ accuracy). This answer links to a paper and code that can do this for you. It's not something you want to do by hand!

However, before you make this too complicated, check the requirements of your project: if you are measuring the qubits immediately after the inverse Fourier transform, then you don't need the controlled-phase gate at all! You can perform the measurement of the control qubit first, and then, depending on the output, apply just the phase gate on the target. This reduces the complexity a bit because, for example, if you had to implement controlled-$T$ before (not in your gate set), then now you just have to implement $T$ (in your gate set)!