Reversible Computation

Reversible computation is a model of computation in which every computational step can be undone — where the mapping from inputs to outputs is a bijection, preserving all information about intermediate states. Unlike conventional computation, which routinely destroys information by overwriting registers and erasing bits, reversible computation retains a complete history of state transitions. This matters for thermodynamics: Rolf Landauer established that information erasure generates heat, so computation that never erases information could in principle approach zero energy dissipation. Charles Bennett demonstrated in 1973 that any computation can be made reversible by retaining a scratch record of intermediate states. The practical cost is memory: reversibility trades heat for storage.

Reversible logic gates — the Toffoli Gate and Fredkin Gate are canonical examples — are functionally complete: any classical computation can be expressed using them. Reversible computation is also a prerequisite for quantum computation, since quantum evolution is unitary and therefore inherently reversible; irreversibility enters only at measurement. The challenge for practical implementation is that the memory required to store intermediate states often exceeds the savings from eliminating erasure, and the overhead of uncomputation (running the reverse computation to clean scratch space) adds its own costs. Whether reversible computation will matter at practical scales depends on how close future hardware comes to the Landauer limit — and on whether the memory cost of reversibility becomes cheaper than its thermodynamic alternative.