# 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?

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)? 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}$$.