Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 2980
Articles: 2'029'581
Articles rated: 2577

19 January 2021
 
  » » arxiv » 37588

 Article forum


Reversibility and Adiabatic Computation: Trading Time and Space for Energy
Ming Li ; Paul Vitanyi ;
Date 13 Mar 1997
Journal Proc. Royal Society of London, Series A, 452(1996), 769-789
Subject Quantum Physics; Computational Complexity; Computational Engineering, Finance, and Science; Data Structures and Algorithms | quant-ph cs.CC cs.CE cs.DS
AffiliationUniversity of Waterloo), Paul Vitanyi (CWI and University of Amsterdam
AbstractFuture 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.
Source arXiv, quant-ph/9703022
Services Forum | Review | PDF | Favorites   
 

No message found in this article forum.  You have a question or message about this article? Ask the community and write a message in the forum.
If you want to rate this article, please use the review section..

Subject of your forum message:
Write your forum message below (min 50, max 2000 characters)

2000 characters left.
Please, read carefully your message since you cannot modify it after submitting.

  To add a message in the forum, you need to login or register first. (free): registration page






ScienXe.org
» my Online CV
» Free


News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2021 - Scimetrica