dorsal/arxiv
View SchemaReversibility and Adiabatic Computation: Trading Time and Space for Energy
| Authors | Ming Li, Paul Vitanyi |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9703022 |
| URL | https://arxiv.org/abs/quant-ph/9703022 |
| DOI | 10.1098/rspa.1996.0039 |
| Journal | Proc. Royal Society of London, Series A, 452(1996), 769-789 |
Abstract
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.
{
"annotation_id": "152d4c05-909c-4480-9f2b-d7e524073ec2",
"date_created": "2026-03-02T18:02:40.450000Z",
"date_modified": "2026-03-02T18:02:40.450000Z",
"file_hash": "2c6394315d83f5a4ecd53820f0a2ef41e56a2af7eb37acfc30777630c6ff27ad",
"private": false,
"record": {
"abstract": "Future miniaturization and mobilization of computing devices requires energy\nparsimonious `adiabatic\u0027 computation. This is contingent on logical\nreversibility of computation. An example is the idea of quantum computations\nwhich are reversible except for the irreversible observation steps. We propose\nto study quantitatively the exchange of computational resources like time and\nspace for irreversibility in computations. Reversible simulations of\nirreversible computations are memory intensive. Such (polynomial time)\nsimulations are analysed here in terms of `reversible\u0027 pebble games. We show\nthat Bennett\u0027s pebbling strategy uses least additional space for the greatest\nnumber of simulated steps. We derive a trade-off for storage space versus\nirreversible erasure. Next we consider reversible computation itself. An\nalternative proof is provided for the precise expression of the ultimate\nirreversibility cost of an otherwise reversible computation without\nrestrictions on time and space use. A time-irreversibility trade-off hierarchy\nin the exponential time region is exhibited. Finally, extreme\ntime-irreversibility trade-offs for reversible computations in the thoroughly\nunrealistic range of computable versus noncomputable time-bounds are given.",
"arxiv_id": "quant-ph/9703022",
"authors": [
"Ming Li",
"Paul Vitanyi"
],
"categories": [
"quant-ph",
"cs.CC",
"cs.CE",
"cs.DS"
],
"doi": "10.1098/rspa.1996.0039",
"journal_ref": "Proc. Royal Society of London, Series A, 452(1996), 769-789",
"title": "Reversibility and Adiabatic Computation: Trading Time and Space for Energy",
"url": "https://arxiv.org/abs/quant-ph/9703022"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "34ce0589-f4e0-46e7-9cc9-37382800f828",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}