next up previous
Next: Classical universal machines Up: Quantum computation: a tutorial Previous: Computing at the

Reversible computation:

What are the difficulties in trying to build a classical computing machine on such a small scale? One of the biggest problems with the program of miniaturizing conventional computers is the difficulty of dissipated heat. As early as 1961 Landauer studied the physical limitations placed on computation from dissipation [8]. Surprisingly, he was able to show that almost all operations required in computation could be performed in a reversible manner, thus dissipating no heat! The first condition for any deterministic device to be reversible is that its input and output be uniquely retrievable from each other. This is called logical reversibility. If, in addition to being logically reversible, a device can actually run backwards then it is called physically reversible and the second law of thermodynamics guarantees that it dissipates no heat.

The work on classical, reversible computation has laid the foundation for the development of quantum mechanical computers. On a quantum computer, programs are executed by unitary evolution of an input that is given by the state of the system. Since all unitary operators U are invertible with , we can always ``uncompute'' (reverse the computation) on a quantum computer.

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