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…
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…
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…
Let $S$ be a stochastic $n$-bit matrix, that is, $S$ is a $(2^n \times 2^n)$-matrix $(a_{ij})$ such that each $a_{ij} \in [0,1]$ and $\sum_{j=0}^{2^n-1} a_{ij} = 1$, for each $i = 0, \dots, 2^n-1$. Writing $|i\rangle$ for the $2^n$-vector representing the binary state of the $n$ bits coding the number $i$, we have $$S|i\rangle =…