Physics – Quantum Physics
Scientific paper
1997-03-13
Proc. Royal Society of London, Series A, 452(1996), 769-789
Physics
Quantum Physics
30 pages, Latex. Lemma 2.3 should be replaced by the slightly better ``There is a winning strategy with $n+2$ pebbles and $m-1
Scientific paper
10.1098/rspa.1996.0039
Future miniaturization and mobilization of computing devices requires energy parsimonious `adiabatic' computation. This is contingent on logical reversibility of computation. An example is the idea of quantum computations which are reversible except for the irreversible observation steps. We propose to study quantitatively the exchange of computational resources like time and space for irreversibility in computations. Reversible simulations of irreversible computations are memory intensive. Such (polynomial time) simulations are analysed here in terms of `reversible' pebble games. We show that Bennett's pebbling strategy uses least additional space for the greatest number of simulated steps. We derive a trade-off for storage space versus irreversible erasure. Next we consider reversible computation itself. An alternative proof is provided for the precise expression of the ultimate irreversibility cost of an otherwise reversible computation without restrictions on time and space use. A time-irreversibility trade-off hierarchy in the exponential time region is exhibited. Finally, extreme time-irreversibility trade-offs for reversible computations in the thoroughly unrealistic range of computable versus noncomputable time-bounds are given.
Li Ming
Vitanyi Paul
No associations
LandOfFree
Reversibility and Adiabatic Computation: Trading Time and Space for Energy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Reversibility and Adiabatic Computation: Trading Time and Space for Energy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reversibility and Adiabatic Computation: Trading Time and Space for Energy will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-525610