Time and space bounds for reversible simulation

DOI10.1088/0305-4470/34/35/308zbMath0988.81021arXivquant-ph/0101133OpenAlexW3101299045MaRDI QIDQ2766195

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

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

subexponential timeirreversible computationLange-McKenzie-Tapp methodsubquadratic spacetrade-off between time and space

Mathematics Subject Classification ID

Quantum computation (81P68)

Related Items (6)

Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms ⋮ Reversibility of computations in graph-walking automata ⋮ Design of 1-tape 2-symbol reversible Turing machines based on reversible logic elements ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Ricercar: A Language for Describing and Rewriting Reversible Circuits with Ancillae and Its Permutation Semantics ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling

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