Is there a way to prove that the number of gates in Exercise 4.22 of Nielsen and Chuang's book is the smallest possible number?

Question

I've been going over Nielsen and Chuang's Quantum Computation and Quantum Information and I ran into Exercise 4.22, which says,

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-NOTs.

Given $U\in\text{U}(2)$, the operator $C^{2}(U)\in\text{U}(2^{3})$ is a controlled-$U$ gate with two control qubits and one target qubit. The exercise asks us to construct this purely out of one-qubit gates and CNOTs with the specified number of components. The intricate solution to this is given in this post.

This made me wonder a few questions:

• Is there a circuit that improves on the number of one-qubit gates or number of CNOTs in any way? To be more specific, is there an equivalent circuit made of only one-qubit gates and CNOTs that has strictly less than $14$ components?
• If the answer is no, is there a proof that $14$ components is the least number of components possible for this problem (assuming $U\in\text{U}(2)$ is arbitrary)?

Answer 1

It's not the smallest possible number. At least, not without making several additional restrictions.

You can do it in an expected cost of 4.5 two qubit gates and 8 single qubit gates if you use an ancilla, allow feedback, and count arbitrary-basis measurement and arbitrary-basis preparation as single qubit operations.

Here's the circuit that does it:

Note that I'm assuming all adjacent single qubit operations are fused together, and that includes the classically controlled X being conditionally fused with the final $U^{-1}$.

Note that I'm not counting classical controls towards the qubit count of an operation. Also, the measurement is 50/50 random so all the classically controlled gates are only present half of the time.