Reversible simulation of irreversible computation

Reversible simulation of irreversible algorithms is analysed in the stylized form of a “reversible” pebble game. While such simulations incur little overhead in additional computation time, they use a large amount of additional memory space during the computation. We show that among all simulations which can be modelled by the pebble game, Bennett´s simulation is optimal in that it uses the least auxiliary space for the greatest number of simulated steps. We give a trade-off of storage space versus irreversible erasure. Examples of reversible algorithms are algorithms for quantum computers