Suppose we have a circuit decomposition of a unitary $U$ using some universal gate set (for example CNOT-gates and single qubit unitaries). Is there a direct way to write down the circuit of the corresponding controlled unitary $C_U$ using the same universal gate set?

For example take $U=i Y = H X H X$, as a circuit:
circuit for U

We can replace the $X$ gates by $C_X$ (CNOT) gates to obtain $C_U$:
circuit for CU

This works because if the control qubit is in state $|0\rangle$ the action on the target is $H^2=\mathbb{I}$, while for $|1\rangle$ it applies the circuit for $U$. For different $U$, in particular if it acts on several qubits, coming up with such a circuit might be cumbersome. Is there a recipe to obtain the circuit of $C_U$ given that you know how to build $U$?

  • $\begingroup$ are you asking how to build a C-U out of an arbitrary one-qubit U? A method to do that can be found in chapter 4 of N&C (see e.g. figure 4.6 in the last edition), which is basically the generalisation of the decomposition you showed $\endgroup$
    – glS
    Mar 26 '18 at 17:05
  • $\begingroup$ @glS oh wow, I was not aware of that. Looks exactly like my example. Good to see how it implements the phase $\alpha$. But they don't seem to discuss the generalization to more target qubits? $\endgroup$
    – M. Stern
    Mar 26 '18 at 18:47

The question may not be entirely well-defined, in the sense that to ask for a way to compute $C(U)$ from a decomposition of $U$ you need to specify the set of gates that you are willing to use. Indeed, it is a known result that any $n$-qubit gate can be exactly decomposed using $\text{CNOT}$ and single-qubit operations, so that a naive answer to the question would be: just decompose $C(U)$ using single-qubit and $\text{CNOT}$s.

A different interpretation of the question is the following: given $U$, can I compute $C(U)$ using a set of single-qubit operations and $\text{CNOT}$s not on the control qubit, and $\text{CNOT}$s with the control being the first qubit? This can be done generalising a result found in chapter four of Nielsen & Chuang.

Let $U$ be a single-qubit gate. It can then be proved that $U$ can always be written as $U = e^{i\alpha} AXBXC$, where $X$ is the Pauli X gate, and $A, B$ and $C$ are single-qubit operations such that $ABC=I$ (see N&C for a proof). It follows that $$C(U)=\Phi_1(\alpha)A_2C(X)B_2C(X) C_2,$$ where $\Phi_1(\alpha)\equiv\begin{pmatrix}1&0\\0&e^{i\alpha}\end{pmatrix}\otimes I$ is a phase gate applied to the first qubit, and $A_2, B_2, C_2$ are $A, B, C$ applied to the second qubit. This is immediate once you realise that, if that first qubit is $|0\rangle$, then $C(X)$ becomes an identity, and on the second qubit you have the operations $ABC$, which give the identity. On the other hand, if the first qubit is $|1\rangle$, then on the second rail you have $AXBXC$, which (together with the phase) equals $U$ by definition.

The above decomposition can be used to find a naive way to compute $C(U)$ for a general $n$-qubit unitary gate. The main observation is that if $U=A_1 A_2\cdots A_m$ for any set of gates $\{A_1,..,A_m\}$, then $$C(U)=C(A_1)C(A_2)\cdots C(A_m).$$ But we also know that any $n$-qubit $U$ can be decomposed in terms of CNOTs and single-qubit operations. It follows that $C(U)$ is a sequence of CCNOT and $C(V)$ operations, where CCNOT is here an $X$ gate applied to some qubit conditioned to two other qubits being $|1\rangle$, and $V$ is a single-qubit operation on some qubit. But again, any CCNOT operation (also called Toffoli), can be decomposed as shown in Figure 4.9 in N&C, and the $C(V)$ are decomposed as shown in the first part of the answer.

This method allows decomposing a general $n$-qubit unitary gate $U$ using only $\text{CNOT}$ and single-qubit gates. You may then go further and generalise this to find a decomposition for the case of multiple control qubits. For this you only now need a way to decompose the Toffoli gates, which is again found in Figure 4.9 of N&C.

  • $\begingroup$ I think that's what I was looking for. Just to make sure: Lets say the known decomposition $U=A_1 A_2 \dots A_m$ contains $C(X)$ and single qubit gates. Then for single-qubit gates we replace $A_i$ by $C(A_i)$, which is constructed following the description in N&C. And the $C(X)$ are replaced by Toffoli gates (which might also be decomposed). Right? $\endgroup$
    – M. Stern
    Mar 26 '18 at 22:12
  • $\begingroup$ @M.Stern well almost. If $U$ contains a $C(X)$ (which more precisely would be a $C(X)_{ij}$, acting between $i$-th and $j$-th qubit, with $i, j>1$), then the equivalent gate in $C(U)$ is already a Toffoli gate, with first and $i$-th qubits as control and $j$-th qubit as target. You can therefore go and replace the Toffolis using the known decompositions $\endgroup$
    – glS
    Mar 26 '18 at 23:50

Although this might not answer your question completely, I think it might provide some direction of thinking. Here are two important facts:

  • Any unitary $2^{n}\times 2^{n}$ matrix $M$, can be realized on a quantum computer with $n$-quantum bits by a finite sequence of controlled-not and single qubit gates1.

  • Suppose $U$ is a unitary $2\times 2$ matrix satisfying $\text{tr } U \neq 0$, $\text{tr} (UX) \neq 0$, and $\text{det } U \neq 1$. Then six elementary gates are necessary and sufficient to implement a controlled $U$-gate2.

It should be possible to extend the second case to the general $n\times n$ case, given the first point, although I haven't found any paper which does that explicitly.

1 Elementary gates for quantum computation-A. Barenco (Oxford), C. H. Bennett (IBM), R. Cleve (Calgary), D. P. DiVincenzo (IBM), N. Margolus (MIT), P. Shor (AT&T), T. Sleator (NYU), J. Smolin (UCLA), H. Weinfurter (Innsbruck)

2 Optimal Realizations of Controlled Unitary Gates - Guang Song, Andreas Klappenecker (Texas A&M University)


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.