Patrick Speissegger
Fix a number $n$ of qubits. In this post, we show how to build the Toffoli gates $T^{|k\rangle}_{|l\rangle}$ out of 1-gates and the CNOT gate. When combined with this post, we conclude that the set of 1-gates together with CNOT form a universal set of quantum gates. Since $T^{|k\rangle}_{|l\rangle}$ is built from the Pauli gate…
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…
For $n > 1$, the classic Toffoli $n$-gate is the gate that computes the function from $(\ZZ_2)^n$ into $(\ZZ_2)^n$ given by $$(x_1, \dots, x_n) \mapsto (x_1, \dots, x_{n-1}, x_n \oplus (x_1\cdots x_{n-1})).$$ Note that the classic Toffoli 2-gate is CNOT. The quantum Toffoli $n$-gate is the unique $n$-qubit gate that maps the computational basis state…