## How do we express the efficiency of an algorithm involving random events?

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…

## Building Toffoli gates from 1-gates and CNOT

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…

## 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…

## Toffoli gates

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…