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.

The entire question

  • $\begingroup$ Welcome on Physics SE :) Please edit your question to include the reference in a form accessible to any reader. $\endgroup$ – Sanya Oct 30 '16 at 8:54
  • $\begingroup$ $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. $\endgroup$ – Peter Shor Oct 30 '16 at 17:42
  • $\begingroup$ @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. $\endgroup$ – Shahab Nov 3 '16 at 15:24

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:

double-control from single-control sqrt

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:

Stashed combination

  • $\begingroup$ 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) $\endgroup$ – Shahab Nov 3 '16 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.