Patrick Speissegger
To illustrate how we do this, let us do this for the input search algorithm, both for the Classical Turing machine (CTM) and the Probabilistic Turing Machine (PTM). In both cases, it makes sense to express the number of steps needed to find the input as functions $t_{\textrm{CTM}}(d)$ and $t_{\textrm{PTM}}(d)$ of the distance $d$ of…
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…