## Quantum logic gates

To define quantum gates, we first need to specify the quantum replacement of an *n*-bit datum. The *quantized version* of classical *n*-bit space {0,1}^{n} is the Hilbert space

- H QB ( n ) = ℓ 2 ( { 0 , 1 } n ) . {\displaystyle H_{\operatorname {QB} (n)}=\ell ^{2}(\{0,1\}^{n}).}

This is by definition the space of complex-valued functions on {0,1}^{n} and is naturally an inner product space. This space can also be regarded as consisting of linear superpositions of classical bit strings. Note that *H*_{QB(n)} is a vector space over the complex numbers of dimension 2^{n}. The elements of this space are called *n*-qubits.

Using Dirac ket notation, if *x*_{1},*x*_{2}, …,*x*_{n} is a classical bit string, then

- | x 1 , x 2 , ⋯ , x n ⟩ {\displaystyle |x_{1},x_{2},\cdots ,x_{n}\rangle \quad }

is a special *n*-qubit corresponding to the function which maps this classical bit string to 1 and maps all other bit strings to 0; these 2^{n} special *n*-qubits are called *computational basis states*. All *n*-qubits are complex linear combinations of these computational basis states.

Quantum logic gates, in contrast to classical logic gates, are always reversible. One requires a special kind of reversible function, namely a unitary mapping, that is, a linear transformation of a complex inner product space that preserves the Hermitian inner product. An *n*-qubit (reversible) quantum gate is a unitary mapping *U* from the space *H*_{QB(n)} of *n*-qubits onto itself.

Typically, we are only interested in gates for small values of *n*.

A reversible *n*-bit classical logic gate gives rise to a reversible *n*-bit quantum gate as follows: to each reversible *n*-bit logic gate *f* corresponds a quantum gate *W*_{f} defined as follows:

- W f ( | x 1 , x 2 , ⋯ , x n ⟩ ) = | f ( x 1 , x 2 , ⋯ , x n ) ⟩ . {\displaystyle W_{f}(|x_{1},x_{2},\cdots ,x_{n}\rangle )=|f(x_{1},x_{2},\cdots ,x_{n})\rangle .}

Note that *W*_{f} permutes the computational basis states.

Of particular importance is the controlled NOT gate (also called CNOT gate) *W*_{CNOT} defined on a quantized 2 qubit. Other examples of quantum logic gates derived from classical ones are the Toffoli gate and the Fredkin gate.

However, the Hilbert-space structure of the qubits permits many quantum gates that are not induced by classical ones. For example, a relative phase shift is a 1 qubit gate given by multiplication by the unitary matrix:

- U θ = [ e i θ 0 0 1 ] , {\displaystyle U_{\theta }={\begin{bmatrix}e^{i\theta }&0\\0&1\end{bmatrix}},}

so

- U θ | 0 ⟩ = e i θ | 0 ⟩ U θ | 1 ⟩ = | 1 ⟩ . {\displaystyle U_{\theta }|0\rangle =e^{i\theta }|0\rangle \quad U_{\theta }|1\rangle =|1\rangle .}

## Reversible logic circuits

Again, we consider first *reversible* classical computation. Conceptually, there is no difference between a reversible *n*-bit circuit and a reversible *n*-bit logic gate: either one is just an invertible function on the space of *n* bit data. However, as mentioned in the previous section, for engineering reasons we would like to have a small number of simple reversible gates, that can be put together to assemble any reversible circuit.

To explain this assembly process, suppose we have a reversible *n*-bit gate *f* and a reversible *m*-bit gate *g*. Putting them together means producing a new circuit by connecting some set of *k* outputs of *f* to some set of *k* inputs of *g* as in the figure below. In that figure, *n*=5, *k*=3 and *m*=7. The resulting circuit is also reversible and operates on *n*+*m*−*k* bits.

We will refer to this scheme as a *classical assemblage* (This concept corresponds to a technical definition in Kitaev’s pioneering paper cited below). In composing these reversible machines, it is important to ensure that the intermediate machines are also reversible. This condition assures that *intermediate* “garbage” is not created (the net physical effect would be to increase entropy, which is one of the motivations for going through this exercise).

Now it is possible to show that the Toffoli gate is a universal gate. This means that given any reversible classical *n*-bit circuit *h*, we can construct a classical assemblage of Toffoli gates in the above manner to produce an (*n*+*m*)-bit circuit *f* such that

- f ( x 1 , … , x n , 0 , … , 0 ⏟ ) = ( y 1 , … , y n , 0 , … , 0 ⏟ ) {\displaystyle f(x_{1},\ldots ,x_{n},\underbrace {0,\dots ,0} )=(y_{1},\ldots ,y_{n},\underbrace {0,\ldots ,0} )}

where there are *m* underbraced zeroed inputs and

- ( y 1 , … , y n ) = h ( x 1 , … , x n ) {\displaystyle (y_{1},\ldots ,y_{n})=h(x_{1},\ldots ,x_{n})} .

Notice that the end result always has a string of *m* zeros as the ancilla bits. No “rubbish” is ever produced, and so this computation is indeed one that, in a physical sense, generates no entropy. This issue is carefully discussed in Kitaev’s article.

More generally, any function *f* (bijective or not) can be simulated by a circuit of Toffoli gates. Obviously, if the mapping fails to be injective, at some point in the simulation (for example as the last step) some “garbage” has to be produced.

For quantum circuits a similar composition of qubit gates can be defined. That is, associated to any *classical assemblage* as above, we can produce a reversible quantum circuit when in place of *f* we have an *n*-qubit gate *U* and in place of *g* we have an *m*-qubit gate *W*. See illustration below:

The fact that connecting gates this way gives rise to a unitary mapping on *n*+*m*−*k* qubit space is easy to check. In a real quantum computer the physical connection between the gates is a major engineering challenge, since it is one of the places where decoherence may occur.

There are also universality theorems for certain sets of well-known gates; such a universality theorem exists, for instance, for the pair consisting of the single qubit phase gate *U*_{θ} mentioned above (for a suitable value of θ), together with the 2-qubit CNOT gate *W*_{CNOT}. However, the universality theorem for the quantum case is somewhat weaker than the one for the classical case; it asserts only that any reversible *n*-qubit circuit can be *approximated* arbitrarily well by circuits assembled from these two elementary gates. Note that there are uncountably many possible single qubit phase gates, one for every possible angle θ, so they cannot all be represented by a finite circuit constructed from {*U*_{θ}, *W*_{CNOT})}.