Time and space bounds for reversible simulation

DOI10.1088/0305-4470/34/35/308MaRDI QIDQ2766195zbMATH OpenOpenAlexFDO

Authors Harry Buhrman, John Tromp, Paul M. B. Vitányi

Publication date 27 January 2002

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0101133

zbMATH Keywords

irreversible computationLange-McKenzie-Tapp methodsubexponential timesubquadratic spacetrade-off between time and space

Mathematics Subject Classification ID

Quantum computation (81P68)

Abstract: We prove a general upper bound on the tradeoff between time and space that suffices for the reversible simulation of irreversible computation. Previously, only simulations using exponential time or quadratic space were known. The tradeoff shows for the first time that we can simultaneously achieve subexponential time and subquadratic space. The boundary values are the exponential time with hardly any extra space required by the Lange-McKenzie-Tapp method and the ($log3$)th power time with square space required by the Bennett method. We also give the first general lower bound on the extra storage space required by general reversible simulation. This lower bound is optimal in that it is achieved by some reversible simulations.

Recommendations

• scientific article; zbMATH DE number 1754652
• Time/Space Trade-Offs for Reversible Computation
• A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
• Reversible simulation of space-bounded computations
• Reversible space equals deterministic space

Cited in

(14)

• Nullstellensatz size-degree trade-offs from reversible pebbling
• Reversibility of computations in graph-walking automata
• Real-time methods in reversible computation
• Ricercar: a language for describing and rewriting reversible circuits with ancillae and its permutation semantics
• Reversibility in space-bounded computation
• Toward an energy efficient language and compiler for (partially) reversible algorithms
• A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
• Time/Space Trade-Offs for Reversible Computation
• scientific article; zbMATH DE number 1754652 (Why is no real title available?)
• Time and space complexity of reversible pebbling
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Deriving global virtual time algorithms from conservative simulation protocols
• Reversible simulation of space-bounded computations
• Design of 1-tape 2-symbol reversible Turing machines based on reversible logic elements

This page was built for publication: Time and space bounds for reversible simulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2766195)