# Constructing 2-qubit controlled-U op with 3n 3-qubit gates

I am struggling with how to go about applying the outline of controlled operations in N&C Quantum Computation and Quantum Information (pg 177-185, 10th ed) to construct a generalized-control-U gate.

The question I am trying to solve is how to compute the square root of a quantum circuit, where in the question it mentions using a clever trick involving phase estimation algorithm to do this efficiently. Specifically, the part I am confused with is where it is asking to construct a 2-qubit controlled-U operation using 3n 3-qubit gates, where n is an arbitrary number.

For the longest time, I assumed that this controlled-U gate was a single-qubit U gate with two control gates. But I am unsure if this is the case, rather U might be an n-qubit gate with 2 control-qubits.

Long story short, I am very confused on how to interpret the question and how to go about solving it, if anyone has seen something similar to this or can shed some light, I would be very grateful. Let me know if my question requires more details.

• Welcome on Physics SE :) Please edit your question to include the reference in a form accessible to any reader. – Sanya Oct 30 '16 at 8:54
• $U$ is a unitary operation implemented by $s$ 2-qubit gates. For part (a), you just want to take each 2-qubit gate in the original circuit for $U$ and make a controlled version of it using three 3-qubit gates. – Peter Shor Oct 30 '16 at 17:42
• @PeterShor, thank you for the clarification. I got lost in the description of applying the trick, outlined in the problem, and following along with taking the square root of U. – Shahab Nov 3 '16 at 15:24

You'd have to apply this to every individual 2-qubit gate, so it would use $3s$ three-qubit gates (plus 2s CNOTs).
Alternatively, if you have an ancilla available, you can just stash the AND of the controls then singly-control based on that. This only requires $s+2$ three-qubit gates: