Let $U$ be an $(n+1)$-gate. Assume that $U = \big(a_{ij}\big)$ is the matrix representation of $U$ with respect to the computational basis.
The goal of this post is to prove that $U$ can be designed using only Toffoli gates and gates of the form $(I_{n} \otimes A)$, for various 1-gates $A$. By this post, we only need to show that $U$ can be designed using Toffoli gates and controlled gates c$_n$-$A$, for various 1-gates $A$.
Lemma 1
Assume that $a_{21} \ne 0$, and set $$V:= \frac1{\sqrt{a_{11}\bar{a_{11}} + a_{21}\bar{a_{21}}}} \begin{pmatrix}
\bar{a_{11}} & \bar{a_{21}} \\ a_{21} & -a_{11}
\end{pmatrix}.$$
Then:
- $V$ is a 1-gate (i.e., a unitary 1-qubit operator).
- There are complex numbers $b_{12}, \dots, b_{1,2^{n+1}}, b_{22}, \dots, b_{2,2^{n+1}}$ such that $$(\text{c}_n\text{-}V)U = \begin{pmatrix} \sqrt{a_{11}\bar{a_{11}} + a_{21}\bar{a_{21}}} & b_{12} & \cdots \\ 0 & b_{22} & \cdots \\ a_{31} & a_{32} & \cdots \\ \vdots \end{pmatrix}.$$
Proof. Part 1 is left as an exercise. Part 2 follows from the observation that $$\text{c}_n\text{-}V = \begin{pmatrix} V & 0 \\ 0 & I_{2^{n+1}-2} \end{pmatrix}$$ in block form. $\qed$
Lemma 2
Assume that $a_{31} \ne 0$, and set $$V:= \frac1{\sqrt{a_{11}\bar{a_{11}} + a_{31}\bar{a_{31}}}} \begin{pmatrix}
\bar{a_{11}} & \bar{a_{31}} \\ a_{31} & -a_{11}
\end{pmatrix}.$$
Then:
- $V$ is a 1-gate (i.e., a unitary 1-qubit operator).
- There are complex numbers $b_{12}, \dots, b_{1,2^{n+1}}, b_{32}, \dots, b_{3,2^{n+1}}$ such that $$T^{|1\rangle}_{|2\rangle}(\text{c}_n\text{-}V)T^{|1\rangle}_{|2\rangle}U = \begin{pmatrix} \sqrt{a_{11}\bar{a_{11}} + a_{31}\bar{a_{31}}} & b_{12} & \cdots \\ a_{21} & a_{22} & \cdots \\ 0 & b_{32} & \cdots \\ a_{41} & a_{42} & \cdots \\ \vdots \end{pmatrix}.$$
Proof. Multiplying c$_n$-$V$ on the right by $T^{|1\rangle}_{|2\rangle}$ exchanges the 2nd and 3rd columns of c$_n$-$V$, while multiplying it on the left by the same matrix exchanges the 2nd and 3rd rows of c$_n$-$V$. So $$T^{|1\rangle}_{|2\rangle}(\text{c}_n\text{-}V)T^{|1\rangle}_{|2\rangle} = \begin{pmatrix} \frac{\bar{a_{11}}}{\sqrt{a_{11}\bar{a_{11}} + a_{31}\bar{a_{31}}}} & 0 & \frac{\bar{a_{31}}}{\sqrt{a_{11}\bar{a_{11}} + a_{31}\bar{a_{31}}}} & 0 & \cdots \\ 0 & 1 & 0 & 0 & \cdots \\ \frac{a_{31}}{\sqrt{a_{11}\bar{a_{11}} + a_{31}\bar{a_{31}}}} & 0 & \frac{-a_{11}}{\sqrt{a_{11}\bar{a_{11}} + a_{31}\bar{a_{31}}}} & 0 & \cdots \\ \\ 0 & 0 & 0 && I_{2^{n+1}-3} \end{pmatrix};$$ Lemma 2 now follows arguing as in the proof of Lemma 1. $\qed$
Replacing 3 in the previous lemma by any $k \in \{2, \dots, 2^{n+1}\}$ and arguing along the same lines, we obtain the following:
Lemma 3
Assume that $a_{k1} \ne 0$, and set $$V:= \frac1{\sqrt{a_{11}\bar{a_{11}} + a_{k1}\bar{a_{k1}}}} \begin{pmatrix}
\bar{a_{11}} & \bar{a_{k1}} \\ a_{k1} & -a_{11}
\end{pmatrix}.$$
Then:
- $V$ is a 1-gate (i.e., a unitary 1-qubit operator).
- There are complex numbers $b_{12}, \dots, b_{1,2^{n+1}}, b_{k2}, \dots, b_{k,2^{n+1}}$ such that $$T^{|1\rangle}_{|k-1\rangle}(\text{c}_n\text{-}V)T^{|1\rangle}_{|k-1\rangle}U = \begin{pmatrix} \sqrt{a_{11}\bar{a_{11}} + a_{k1}\bar{a_{k1}}} & b_{12} & \cdots \\ a_{21} & a_{22} & \cdots \\ \vdots \\ a_{k-1,1} & a_{k-1,2} & \cdots \\ 0 & b_{k2} & \cdots \\ a_{k+1,1} & a_{k+1,2} & \cdots \\ \vdots \end{pmatrix}. \quad\qed$$
To simplify phrasing, we call an $(n+1)$-gate simple if it is the product of Toffoli gates and controlled 1-gates c$_n$-$A$, for various $A$. (So we are trying to show that every $(n+1)$-gate is simple.)
Proposition 1
There are a simple $(n+1)$-gate $U_1$ and a unitary $((2^n-1) \times (2^n-1))$-matrix $V$ such that $$U_1 U = \begin{pmatrix} 1 & 0 \\ 0 & V \end{pmatrix}$$ in block form.
Proof. For each $k \in \{2, \dots, 2^{n+1}\}$, we choose a simple $(n+1)$-gate $U_{1,k}$ by induction on $k$ as follows:
- if the coefficient in row $k$ and column 1 of the matrix $U_{1,k-1} \cdots U_{1,2} \cdot U$ is nonzero, we let $U_{k,1}$ be the gate $T^{|1\rangle}_{|k-1\rangle}(\text{c}_n\text{-}V)T^{|1\rangle}_{|k-1\rangle}$ obtained by applying Lemma 3 to the gate $U_{1,k-1} \cdots U_{1,2} \cdot U$;
- otherwise, we let $U_{1,k}$ be the identity gate.
Our choice of each $U_{1,k}$ and Lemma 3 imply that there are a positive real number $b_{11} > 0$ and complex numbers $b_{12}, \dots, b_{1,2^n}$ and a $((2^n-1) \times (2^n-1))$-matrix $V$ such that $$U_{1,2^n} \cdots U_{1,2} \cdot U = \begin{pmatrix} b_{11} & b_{12} & \cdots & b_{1,2^n} \\ 0 \\ \vdots && V \\ 0 \end{pmatrix}.$$ However, each $U_{1,k}$ is unitary, and since products of unitary operators are again unitary, the gate $U_{1,2^n} \cdots U_{1,2} \cdot U$ is unitary; in particular, its first column is a unit vector. Since the only nonzero entry in the first column is the positive real number $b_{11}$, it follows that $b_{11} = 1$. Since the first row is also a unit vector, we then have $$1+ b_{12}\bar{b_{12}} + \cdots + b_{1,2^n}\bar{b_{1,2^n}} = 1;$$ since $b_{1k}\bar{b_{1k}} \ge 0$ for each $k$, it follows that $b_{1k}\bar{b_{1k}} = 0$, that is, $b_{1k} = 0$, for each $k$. This, in turn, implies that $V$ is also unitary, so the proposition is proved. $\qed$
Our proof of Proposition 1 and Lemma 3 also shows the following: if $k \ge 2$ is such that $a_{1k} = 0$, then the matrices $U$ and $U_1U$ have the same entries in the $k$-th row. This observation suggests how we can replace the second row and column in $U_1U$ by $\begin{pmatrix} 0 & 1 & 0 & \cdots & 0\end{pmatrix}$ and its transpose:
- exchange the first and second rows of $U_1U$, then the first and second columns of the resulting matrix;
- apply Proposition 1 to the matrix obtained in 1;
- exchange the first and second columns, then the first and second rows, of the matrix obtained in 2.
In other words, there is a simple gate $U_2’$ such that the matrix $T^{|1\rangle}_{|0\rangle}U_2’T^{|1\rangle}_{|0\rangle} U_1 U T^{|1\rangle}_{|0\rangle}T^{|1\rangle}_{|0\rangle}$ has block form $\begin{pmatrix} I_2 & 0 \\ 0 & V \end{pmatrix}$, for some unitary $((2^{n+1}-2) \times (2^{n+1}-2))$-matrix $V$. Since $T^{|1\rangle}_{|0\rangle}$ is its own inverse, it follows that there are a simple gate $U_2$ (namely, the gate $T^{|1\rangle}_{|0\rangle}U_2’T^{|1\rangle}_{|0\rangle}$ above) and a unitary $((2^{n+1}-2) \times (2^{n+1}-2))$-matrix $V$ such that $$U_2U_1U = \begin{pmatrix} I_2 & 0 \\ 0 & V \end{pmatrix}$$ in block form.
Iterating this last procedure for each $k \in \{2, \dots, 2^{n+1}\}$, using the respective Toffoli gate $T^{|k-1\rangle}_{|0\rangle}$, we obtain the following:
Proposition 2
There are simple $(n+1)$-gates $U_1, \dots, U_{2^{n+1}-1}$ such that $\ U_{2^{n+1}-1} \cdots U_1 \cdot U = I_{2^{n+1}}$. $\qed$
Exercise: Show that a product of simple gates is a simple gate, and that the multiplicative inverse of a simple gate is a simple gate. [Hint question: what is the multiplicative inverse of a c$_n$-$A$ gate?]
Combining Proposition 2 with the previous exercise, we achieve our goal:
Corollary
The gate $\ U$ is simple. $\qed$