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?

  • 1
    $\begingroup$ arxiv.org/abs/quant-ph/0002039 gives a method to recursively get at the controlled rotations for qft $\endgroup$
    – raeth
    Commented Aug 22, 2023 at 19:59
  • $\begingroup$ How many qubits are you using? this is important to know as it will determine the difficulty of doing QFT with the gates you provide. Approximating rotation gates with {H, S, T} etc is a difficult problem that has been dicussed previously. Maybe this will be helpful? quantumcomputing.stackexchange.com/questions/11861/… $\endgroup$
    – Callum
    Commented Aug 22, 2023 at 20:02

1 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: enter image description here 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)!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.