What is the cost of turning a $U$ circuit into a $CU$ circuit? (add a control to it)

  • The circuit operates on a register of length $q$
  • Suppose the number of quantum gates is $l(U)$
  • Suppose the depth of the circuit is $d(U)$
  • Suppose the classical cost of the circuit construction is $T(U)$

So basically my question is - given such a $U$ what are the

$T(CU)$, $l(CU)$, $d(CU)$?

and for $C^kU$?

$T(C^kU)$, $l(C^kU)$, $d(C^kU)$?

O notation is also good)

  • $\begingroup$ Welcome to QCSE. I always think asymptotically about such problems as they are all polynomially related, but it’s interesting to put it to brass tacks, and ask for specific implementation details. Do you have a specific target gate set in mind? Like Clifford + T? Have you studied how much more difficult $X$ is versus $CX$, or $CCX$? Only the last one is not Clifford, and likely much harder to implement. $\endgroup$
    – Mark S
    Jul 31 at 18:40
  • $\begingroup$ For CU, the naive implementaion is to decompose U to 2 by 2 elemntery gates and add control to each one, and from CU to C^kU one can use k-1 auxilary qubits with 2(k-1) toffoli gates. Do you know a cheaper why? (i want to implement the state of the are method via qiskit and compare it to the default implementaion) $\endgroup$ Aug 1 at 6:13

1 Answer 1


Mottonen and Vartiainen discuss a method for decomposing a general unitary U into around $O(4^n/2)$ CNOTs (compared to a known lower bound of $O(4^n/4)$) using a recursive cosine-sine decomposition (the method was originally used here but I found the first link to have a better explanation). This method recursively makes the following decomposition

Mottonen and Vartiainen, Fig. 14

where the half-filled circles indicate that a different unitary is applied on each state of the control bits. You could decompose a controlled unitary by starting this algorithm "one iteration in" (by replacing $U_1$ in this diagram with your unitary, and everything else with identity gates) and get a close-to-optimal decomposition. This should also work with multi-controlled unitaries. I'm not sure exactly how the optimal decomposition for the controlled version of the gate would be related to the optimal decomposition of the unitary alone, but it's an interesting question.


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.