Harvesting Brownian Motion: Zero Energy Computational Sampling

High Energy Consumption

The key factor currently limiting the advancement of computational power of electronic computation is no longer the manufacturing density and speed of components, but rather their high energy consumption. While it has been widely argued that reversible computation can escape the fundamental Landauer limit of kBTln(2) Joules per irreversible computational step, there is disagreement around whether indefinitely reusable computation can be achieved without energy dissipation.

Simpler context of sampling problems

Here we focus on the relatively simpler context of sampling problems, which take no input, so avoids modelling the energy costs of the observer perturbing the machine to change its input. Given an algorithm A for generating samples from a distribution, we desire a device that can perpetually generate samples from that distribution driven entirely by Brownian motion. We show that such a device can efficiently execute algorithm A in the sense that we must wait only O(time(A)2) between samples.

We consider two output models: Las Vegas, which samples from the exact probability distribution every 4 tries in expectation, and Monte Carlo, in which every try succeeds but the distribution is only approximated. We base our model on continuous-time random walks over the state space graph of a general computational machine, with a space-bounded Turing machine as one instantiation. The problem of sampling a computationally complex probability distribution with no energy dissipation informs our understanding of the energy requirements of computation and may lead to more energy-efficient randomized algorithms.

FOOTNOTES

  1. [^1]: Reynolds, L.D., and N.G. Wilson. “Scribes and Scholars: A Guide to the Transmission of Greek and Latin Literature.” Oxford University Press, 2013.
  1. [^2]: Booth, Wayne C., et al. “The Craft of Research.” University of Chicago Press, 2016.

Share This Post

Software Innovation

Discover our pioneering data storage software aiding in the process of storing, organising, and accessing data. 

0 Comments

Submit a Comment

Your email address will not be published. Required fields are marked *

Related Papers

#DigNA Portfolio Meeting

#DigNA Portfolio Meeting

We were delighted to attend the first DNA-based digital data storage (#DigNA) portfolio meeting which took place in Munich last week. DISCO is one of 9 #EUeic funded projects from the 2022 #EUeic...

read more

Maynooth University

Hamilton Institute
Maynooth
Co. Kildare
Ireland

Funding

Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or European Innovation Council and SMEs Executive Agency (EISMEA). Neither the European Union nor the granting authority can be held responsible for them.

Funded by the EU