In the vein of this question, say I have a 2-qubit unitary gate $U$ which can be represented as a finite sequence of (say) single qubit gates, CNOTs, SWAPs, cXs, cYs and cZs. Now I need to implement a controlled-$U$ gate and hence need its decomposition in terms of simple one- and two-qubit gates. Is there a standard method to get this decomposed circuit?

In Nielsen and Chuang they deal with the general recipe for decomposing $C^n(U)$ gates where $U$ is a single qubit unitary, but not where $U$ is a $k$-qubit unitary cf. glS's answer.


By giving U as that sequence you have reduced the problem to controlled SWAPs, cXs, cYs and cZs already. The single qubit gates you already know how to make controlled.

You can reduce further to controlled SWAPs and cXs by putting in the appropriate $U$ such that $UXU^\dagger=Y$ or $Z$. That gets rid of dealing with the controlled cYs and cZs separately.

So now just have to reduce Toffoli and Fredkin gates to 1 and 2 qubit gates. A Fredkin can be built with 3 Toffoli's just like how a SWAP is built from CNOTs, but with an extra control.

So now all that remains is decomposing a Toffoli gate into single qubit and 2-qubit gates. That is answered here.

  • $\begingroup$ Thanks. Any idea how to compute the $U$'s corresponding to $Y$ and $Z$? $\endgroup$ Jun 4 '19 at 2:06
  • 2
    $\begingroup$ @SanchayanDutta up to some phase factors, you basically want $\sqrt{Z}$ and $\sqrt{Y}$ respectively. This is because any rotation abou a axis that does not contain any $X$ satisfies (up to a phase) $XU^\dagger=UX$, so $UXU^\dagger$ becomes $U^2X$, and we know things like $YX=Z$ (again, up to a phase) $\endgroup$
    – DaftWullie
    Jun 4 '19 at 7:43
  • $\begingroup$ @DaftWullie That helps! glS showed another method here. $\endgroup$ Jun 4 '19 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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