By estimates discussed in previous chapters the difference between the amount of energy required to carry out a computation and the amount that today’s computers actually use, is about eight orders of magnitude. Clearly, there is room for improvement and a lot of people try to to find more efficient forms of computation. One way in this direction is the technology of reversible computing. By that term, computer scientists mean computation that takes place in steps that are time reversible. So if a reversible logic gate changes the input X into the output Y, then there must exists an inverse operation which reverses this step. Crucially, these must be one-to one mappings, meaning that a given input produces a single unique output.

The main motivation for the study of reversible computing is that they offer what is predicted to be the only potential way to improve the energy efficiency of computers beyond the Landauer limit of kT ln(2) energy dissipated per irreversible bit operation discussed in previous chapters.
Notice that the inverter logic gate (NOT) gate is reversible because it can be undone.
Next reversible gate is defined by the function \(g(x,y)=(x,x \otimes y)\), where \(\otimes\) is the standard XOR operation. Notice that \[ g(g(x,y))=g(x,x \otimes y)=(x,x \otimes (x \otimes y))=(x,(x \otimes x) \otimes y))=(x,0 \otimes y))=(x,y) \] so we see that the Faynman gate is reversible.

The pigeonhole principle impllies that any reversible gate must have the same number of input and output bits. The common AND gate is not reversible however. The inputs 00, 01 and 10 are all mapped to the output 0.

The Toffoli gate

Notice that \(T(T(a,b,c))=(a,b,c)\), so the Toffoli gate is reversible. Let also \[ T'(a, b, c) = \begin{cases} ¬c & \mbox{when }a=b=1 \\ c & \mbox{otherwise.}\end{cases} \] Notice that \(T′\) is the projection of \(T\) onto its last axis. Observe that \[ T'(a,b,c) = (a\land b \land \neg c) \lor ((\neg(a\land b)) \land c) \] Therefore \[ T'(a,b,1) = \neg(a\land b) \] so \(T′(a,b,1)\) is the universal NAND gate. Since the NAND gate is universal and the NAND gate may be defined as a Toffoli gate, then the Toffoli gate is universal. This means that for any Boolean function \(f(x_1, x_2, ..., x_m)\), there is a circuit consisting of Toffoli gates which takes \(x_1, x_2, … ,x_m\) and some extra bits set to 0 or 1 and outputs \(x_1, x_2, ... , x_m, f(x_1, x_2, ... , x_m)\), and some extra bits (called garbage).

This for of reversibility we we considered so far is called the logical reversability. And this is to week notion. For efficient computation we need a notion of physical reversability.

These circuits are also referred to as charge recovery logic, adiabatic circuits, or adiabatic computing. Although in practice no non-stationary physical process can be exactly physically reversible, there is no known limit to the closeness with which we can approach perfect reversibility, in systems that are sufficiently well-isolated from interactions with unknown external environments, when the laws of physics describing the system's evolution are precisely known.

More recent motivation comes from quantum computing. Quantum mechanics requires the transformations to be reversible but allows more general states of the computation (superpositions). Thus, the reversible gates form a subset of gates allowed by quantum mechanics and, if we can compute something reversibly, we can also compute it on a quantum computer.

The conventional method of error detection in computation simply involves doing the calculation twice and comparing the results. If they are the same, then the computation is considered error free. This method has an obvious limitation if the original computation and its duplication both make the same error.

Himanshu Thapliyal and Nagarajan Ranganathan, from the University of South Florida, proposed in 2011 a different approach which gets around this problem. If a reversible computation produces a series of outputs, then the inverse computation on these outputs should reproduce the original states. So their idea is to perform the inverse computation on the output states and if this reproduces the original states, then the computation is error free. And because this relies on reversible logic steps, it naturally minimises the amount of garbage states that are produced in between.

Reversible calculations are undoubtedly a fascinating challenge. We do not know so far that they are physically realizable. Perhaps there are deep physical limits of this technology: it is probably that general reversible computations do require some amount of overhead in either space or time complexity. Perhaps it will turn out that the zero-energy calculations are possible, but require virtually infinitely long time.

1. Show that the operation \(\otimes\) is associative.
2. Show that \(NOT(x) = T'(1, 1, x)\)
3. Show that \(AND(a, b) = T'(a, b, 0)\)
4. Define the operator AND from the gate \(T'\).