# 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

## 1 Answer

I think you're just supposed to use a construction from earlier in the book, that built a doubly-controlled single-qubit gate out of three singly-controlled square roots of that gate. But now it's applied to 2-qubit gates: 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: • Ya, the construction of the question is poor and misleading. But I agree that because U is constructed with s 2-qubit gates (but keeping U as an n-qubit system, for the sake of generality) that the added ancilla's allow us to construct the 3s 3-qubit gate. But my prof has said we would not need the CNOTs. Rather, if we draw out the Truth Table, such that |00> results in nothing happening to the system, and |11> applying U^3 |11>, then we have the construction. At least for me, this was not apparent in the question and leads to a very different conclusion (similar to what you have written) – Shahab Nov 3 '16 at 15:22