Quantum Circuit - Reversible Logic Gates

Reversible Logic Gates

Ordinarily, in a classical computer, the logic gates other than the NOT gate are not reversible. Thus, for instance, for an AND gate one cannot recover the two input bits from the output bit; for example, if the output bit is 0, we cannot tell from this whether the input bits are 0,1 or 1,0 or 0,0. However, it is instructive to observe that reversible gates in classical computers are theoretically possible for input strings of any length; moreover, these are actually of practical interest, since they do not increase entropy. A reversible gate is a reversible function on n-bit data that returns n-bit data, where an n-bit datum is a string of bits x₁,x₂, ...,x_n of length n. The set of n-bit data is the space {0,1}n, which consists of 2n strings of 0's and 1's. More precisely,

• An n-bit reversible gate is a bijective mapping f from the set {0,1}n of n-bit data onto itself.

An example of such a reversible gate f is a mapping that changes the first digit of each string.

We are only interested in maps f which are different from the identity, and for reasons of practical engineering we are only interested in gates for small values of n, e.g. n=1, n=2 or n=3. These gates can be easily described by tables. Examples of these logic gates which have been studied are the controlled NOT gate (also called CNOT gate), the Toffoli gate and the Fredkin gate.

To consider 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

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 2n. The elements of this space are called n-qubits.

Using Dirac ket notation, if x₁,x₂, ...,x_n is a classical bit string, then

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 2n special n-qubits are called computational basis states. All n-qubits are complex linear combinations of these computational basis states.

For a quantum computer gate, we require a very special kind of reversible function, namely a unitary mapping, that is, a mapping on H_QB(n) that preserves the inner product.

• An n-qubit (reversible) quantum gate is a unitary mapping U from the space H_QB(n) of n-qubits onto itself.

Again we are only interested in unitary operators U which are different from the identity and we are only interested in gates for small values of n. In fact, reversible classical n-bit logic gates give rise to reversible n-bit quantum gates as follows: to each reversible n-bit logic gate f corresponds a quantum gate W_f defined as follows:

Note that W_f permutes the computational basis states. Of particular importance is the quantized 2 qubit CNOT gate W_CNOT. Of course there are many other properly quantum gates. For example, a relative phase shift is a 1 qubit gate given by multiplication by the unitary matrix:

so