Let $U$ be a quantum $n$-gate. Recall that c-$U$, called the controlled-$U$ gate, is the quantum $(n+1)$-gate such that $$(\text{c-}U) |i_{n+1} i_n \dots i_1\rangle = \begin{cases} |0\rangle \otimes |i_n \dots i_1\rangle &\text{if } i_{n+1} = 0, \\ |1\rangle \otimes U|i_n \dots i_1\rangle &\text{if } i_{n+1} = 1. \end{cases}$$
Assume from now on that $U$ is a $1$-gate. We define the $(n+1)$-gate c$_n$-$U$ by induction on $n$ as follows:
- if $n=1$, then c$_1$-$U :=$ c-$U$;
- if $n > 1$, then c$_n$-$U :=$ c-(c$_{n-1}$-$U$).
Here is the c$_3$-$U$ gate:
Example: from the figure above with $X = U$, we get that c$_n$-$X = T^{(n+1)}_1$.
The goal of this post is to show that every c$_n$-$U$ gate can be designed using only c$_n$-$X$ and gates of the form $I_n \otimes A$, where $A$ is a 1-gate.
For a matrix $A$ and nonzero $k \in \NN$, we define $A^{\otimes k}$ by induction on $k$ as follows:
- if $k=1$, then $A^{\otimes 1} := A$;
- if $k > 1$, then $A^{\otimes k} := A \otimes A^{\otimes (k-1)}$.
Lemma 1
$$\text{c}_n\text{-}U = |0\rangle\langle0| \otimes I_n + |1\rangle\langle 1| \otimes |0\rangle\langle 0| \otimes I_{n-1} + \cdots + |1\rangle\langle 1|^{\otimes (n-1)} \otimes |0\rangle\langle 0| \otimes I_1 + |1\rangle\langle 1|^{\otimes n} \otimes U.$$
Proof. By induction on $n$; the case $n=1$ is the lemma in Lesson 12. So assume that $n>1$ and Lemma 1 holds with $n-1$ in place of $n$ (inductive hypothesis). Then
$$\text{c}_n\text{-}U = \text{c-(c}_{n-1}\text{-}U) = |0\rangle\langle 0| \otimes I_n + |1\rangle\langle 1| \otimes (\text{c}_{n-1}\text{-}U)$$ by the lemma in Lesson 12, so by the inductive hypothesis,
$$\text{c}_n\text{-}U = |0\rangle\langle0| \otimes I_n + |1\rangle\langle1| \otimes \left(|0\rangle\langle0| \otimes I_{n-1} + \cdots + |1\rangle\langle 1|^{\otimes (n-2)} \otimes |0\rangle\langle 0| \otimes I_1 + |1\rangle\langle 1|^{\otimes n} \otimes U\right)$$
$$= |0\rangle\langle0| \otimes I_n + |1\rangle\langle 1| \otimes |0\rangle\langle 0| \otimes I_{n-1} + \cdots + |1\rangle\langle 1|^{\otimes (n-1)} \otimes |0\rangle\langle 0| \otimes I_1 + |1\rangle\langle 1|^{\otimes n} \otimes U,$$ as claimed. $\qed$
Next, let $A$, $B$ and $C$ be 1-gates obtained for $U$ from the corollary in Lesson 12, that is, such that $$U = AXBXC \quad\text{and}\quad ABC = I_1.$$
Lemma 2
$$\text{c}_n\text{-}U = (I_n \otimes A)(\text{c}_n\text{-}X)(I_n \otimes B)(\text{c}_n\text{-}X)(I_n \otimes C).$$
Proof. Using Lemma 1 with $X$ in place of $U$, we get $$(I_n \otimes A)(\text{c}_n\text{-}X) = (I_n \otimes A)\big(|0\rangle\langle0| \otimes I_{n-1} \otimes I_1 + \cdots + |1\rangle\langle 1|^{\otimes (n-1)} \otimes |0\rangle\langle 0| \otimes I_1 + |1\rangle\langle 1|^{\otimes n} \otimes X\big)$$ $$=|0\rangle\langle0| \otimes I_{n-1} \otimes A + \cdots + |1\rangle\langle1|^{\otimes (n-1)} \otimes |0\rangle\langle0| \otimes A + |1\rangle\langle 1|^{\otimes n} \otimes AX.$$ Multiplying by $(I_n \otimes B)$ on the right gives $$|0\rangle\langle0| \otimes I_{n-1} \otimes AB + \cdots + |1\rangle\langle1|^{\otimes (n-1)} \otimes |0\rangle\langle0| \otimes AB + |1\rangle\langle 1|^{\otimes n} \otimes AXB.$$ Multiplying this on the right by c$_n$-$X$ and using Lemma 1, we obtain $$|0\rangle\langle0| \otimes I_{n-1} \otimes AB + \cdots + |1\rangle\langle1|^{\otimes (n-1)} \otimes |0\rangle\langle0| \otimes AB + |1\rangle\langle 1|^{\otimes n} \otimes AXBX,$$ because $|0\rangle\langle0||1\rangle\langle1|$ is the zero operator, and any tensor product with the zero operator is also a zero operator. Finally, multiplying this on the right by $(I_n \otimes C)$ then gives $$|0\rangle\langle0| \otimes I_{n-1} \otimes ABC + \cdots + |1\rangle\langle1|^{\otimes (n-1)} \otimes |0\rangle\langle0| \otimes ABC + |1\rangle\langle 1|^{\otimes n} \otimes AXBXC;$$ since $ABC = I_1$ and $AXBXC = U$, it follows from Lemma 1 that this is equal to c$_n$-$U$, and the lemma is proved. $\qed$
Exercise: if the matrix representing $U$ is $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$, then what does the matrix representing c$_n$-$U$ look like?
Lemma 2 achieves the goal of this post:
Corollary
The $(n+1)$-gate c$_n$-$U$ can be designed using the Toffoli gate c$_n$-$X$ as well as gates of the form $I_n \otimes A$, for various 1-gates $A$. $\qed$