Designing $(n+1)$-gates using 1-gates and Toffoli gates

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…

Controlled 1-gates

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…