This question refers to Nielsen and Chuang's Exercise 4.22:

Prove that a $C^2(U)$ gate (for any single-qubit unitary U) can be constructed using at most eight one-qubit gates, and six controlled-not gates.

A relevant diagram

To prove this, I decomposed all $C(V)$ operations into $AXBXC$ form and ended up with 9 single-qubit gates and 8 C-NOT gates. So I need to now get rid of one single-qubit gate and 2 C-NOT gates. To do the former, I changed the order of $V's$ and got rid of 2 single-qubit gates with combining 2 pairs of single-qubit gates.

For example: as $C=R_z((\delta - \beta)/2)$ and $A=R_z(\beta)R_y(\gamma/2)$ became $CA=R_z((\delta - \beta)/2)R_z(\beta)R_y(\gamma/2)$ Reordering and combining gates picture

For the CNOT gates, I can't touch the 2 C-NOT operations on qubits 0 and qubit 1 because they are important for the functioning of $V^\dagger$. The only way then is to reduce the 4 CNOT gates that compose the 2 $C(V)$ gates. I am encountering some difficulty here. Any help/hint will be appreciated.

*This is not a homework question. I am self-studying from Nielsen and Chuang for an independent project.


1 Answer 1


This is a little bit fiddly and non-obvious. If you start with the given Figure 4.8, and apply the construction of Figure 4.6, with $AXBXC=V$ and $V^2=U$, then you'll have a circuit with 8 single-qubit unitaries and 8 controlled-nots, so you're almost there. enter image description here Note that we have a lot of freedom to move the phase gates around, so I'll move them like this: enter image description here Now, I'm going to move the 6th cNot forward, past cNots 4 and 5. To compensate, I'm going to have to add in extra cNots. This probably requires some further explanation. The third cNOT is computing the parity of the first two qubits (which is uncomputed by the 6th), so that cNots 4 and 5 are controlled off this parity. An alternative way of achieving this is using two cNots, with the same target, controlled off qubits 1 and 2 - if the two qubits are different, one $X$ is applied to the target. If the two are the same, an even number of $X$s are applied to the target, with the net effect being identity. enter image description here Now, notice that the dashed region is diagonal, and so we can commute it past any controls (i.e. anything else that acts on the top 2 qubits). I'll move it all the way to the end for simplicity. Then you should notice that there are two pairs of controlled-nots that cancel each other, leaving the final circuit: enter image description here

An essential set of identities in verifying the functioning of this circuit is $$AXBXB^\dagger XBXC=(VC^\dagger)B^\dagger(A^\dagger V)=V(ABC)^\dagger V=V^2=U$$

  • $\begingroup$ Thanks Sir That helped A lot $\endgroup$
    – Anish
    Commented Aug 7, 2019 at 3:51
  • $\begingroup$ Correct me If I am Wrong , While Revisiting the problem I found In all Circuits in the case |11x> i.e. first two qubits being one , the third qubit goes transformation AXBXB^*XBXC where as It should have gone AXBXC So for this to be true BXB^*X should be equal to I . Please Verify your answer @DaftWullie $\endgroup$
    – Anish
    Commented Aug 8, 2019 at 9:23
  • $\begingroup$ @user142924 I have verified it. $\endgroup$
    – DaftWullie
    Commented Aug 8, 2019 at 12:48
  • $\begingroup$ Thanks the last part was really interesting.. I now can see the construction on tofoli gate from hadamard n other gates.. Is quite similar to to this one @DaftWullie $\endgroup$
    – Anish
    Commented Aug 8, 2019 at 14:40
  • $\begingroup$ @DaftWullie May you please share some reference explaining the rules you applied? I'm referring to the one about the freedom of moving phase shifts, and the one about the commutation properties of the diagonal operators. $\endgroup$ Commented May 11, 2021 at 11:27

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.