4.4 Reversible computing

Recall that a classical computation is irreversible, so dissipative. If a computer operates reversibly, then at least in principle there need be no dissipation, so no power requirement. So, we may compute, in principle, for free. In what follows we will describe quantum realizations of sets of reversible gates which are universal for all Boolean circuits. Recall that a quantum circuit is composed of quantum wires and elementary quantum gates; each wire represents a path of a single qubit and is described by a state in the two dimensional Hilbert space .

First we start by observing that
the transformation


(12)
where and are unitary transformations acting on , is also unitary.
We are going to examine three interesting examples.
The controlled- gate _

where is the single-qubit identity and is another single-qubit gate which can be used in the particular case of

to obtain the controlled-NOT gate .

The gate cannot be used to “copy" a qubit in an unknown state. Indeed, if we assume that the qubit was in the state . We use as input and , that is, , and we apply to it. The result is . The two qubits are apparently in the same state, so we have contradicted the no cloning theorem!

The explanation is simple. When we measure one of the qubits we get 0 or 1 with probabilities and . But, once we measure one qubit, the state of the other qubit is completely determined, so no extra information can be obtained about , so the hidden information carried by is lost because it was not copied. Although the two qubits appear to be identical, they are not independent copies from : they are two entangled qubits carrying together only one qubit of information.
The controlled-controlled-NOT (Toffoli) gate can be obtained from (12 ) by taking and

and the Fredkin _gate FREDKIN can be defined by

where is the swap operation

Any quantum gate can also be represented as a truth table: for each input basis vector we give the output of the gate. In this way, truth tables for Toffoli and Fredkin _gates from Tables 1 and 2 re-appear in Table 4.
Universality is an important consequence of the above analysis:
The transformation given by (12) is universal for all Boolean circuits.
Toffoli quantum gate Fredkin quantum gate
Input Output Input Output
                                                                   
                                                                     Table 4: Toffoli/Fredkin quantum gates.

We already know that the gates AND and NOT form a universal set, hence it suffices to represent them in terms of the transformation given by (12). We have and , hence the third bit is changed, that is

On the other hand, for , if and only if , and otherwise. Consequently, the last bit of is ,

While the or quantum gates are universal for Boolean circuits, they cannot achieve any quantum state transformation. Universality for quantum transformation is defined differently as we are dealing with continuous, not discrete, transformations, and the maximum one can hope for is an arbitrarily good approximation. A matrix is -close to a unitary matrix if . ()Recall that is the norm.) A set of quantum gates is universal for quantum transformations if every unitary transformation can be performed with arbitrary precision by a quantum circuit consisting of gates from . Barenco and co-authors (see [4, 5 ]) have proved that
1. there is no one-qubit universal gate,
2. no classical gate can be universal for quantum computing,
3. together with all single-bit quantum gates form a universal set of gates for quantum computing.
Deutsch, Barenco and Ekert [51] and Lloyd [88] have proven that almost any non-trivial two-qubit gate is universal for quantum computing.