How to reduce circuit elements of a decomposed $C^2(U)$ operation?

Question

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.

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)$

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.

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. Note that we have a lot of freedom to move the phase gates around, so I'll move them like this: 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. 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:

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$$