   Next: Computation without ERASE: Up: Quantum computation: a tutorial Previous: Classical universal machines

# FANOUT and ERASE:

Although the above gates are sufficient for the mathematics of logic, they are not sufficient to build a practical machine. A useful computer will also require the FANOUT and ERASE gates (Fig. 2). Fig. 2 Two non-standard gates that are required to build a computer, in addition to a universal set of logic gates, are: (a) the FANOUT gate which duplicates an input A and (b) the ERASE gate which deletes its input.

First consider the FANOUT gate: Is it reversible? Certainly no information has been destroyed so it is at least logically reversible. Landauer showed that it could also be physically reversible . Let us describe a simple model for FANOUT based on Bennett's scheme for a reversible measurement (Fig. 3) . Here a dark ball is used to determine the presence or absence of a second (light) ball inside a trap. The trap consists of a set of mirrors and may be thought of as a one-bit memory register. If the trap is occupied then the dark ball is reflected and leaves along direction M (with the light ball continuing along its original trajectory); otherwise it passes unhindered towards N. Upon leaving the trap, the dark ball's direction is used to populate, or not, another trap. Fig. 3 A reversible measurement of the existence of a (light) ball in a trap of mirrors (dark rectangles) . A (dark) ball enters the trap from Y. In the absence of a light ball in the trap the dark ball will follow the path HN. In presence of a light ball (timed to start at X) the dark ball will deflect the light one from its unhindered trajectory ABCDEF to ABGDEF and will follow the path HIJKLM itself. (Copyright 1988 by International Business Machines Corporation, reprinted with permission.)

Let us now consider the ERASE operation which is required to ``clean out'' the computer's memory periodically. One type of erasure can be performed reversibly: If we have a backup copy of some information, we can erase further copies by uncomputing the FANOUT gate. The difficulty arises when we wish to erase our last copy, referred to here as the primitive ERASE.

Consider a single bit represented by a pair of equally probable classical states of some particle. To erase the information about the particle's state we must irreversibly compress phase-space by a factor of two. If we allowed this compressed phase-space to adiabatically expand, at temperature T, to its original size, we could obtain an amount of work equal to (where is Boltzmann's constant). Landauer concluded, based on simple models and more general arguments about the compression of phase-space, that the erasure of a bit of information at temperature T requires the dissipation of at least heat (a result known as Landauer's principle) .   Next: Computation without ERASE: Up: Quantum computation: a tutorial Previous: Classical universal machines

Samuel L.~Braunstein
Wed Aug 23 11:54:31 IDT 1995