A space-time tradeoff for implementing a function with master equation dynamics

Abstract

Master equations are commonly used to model the dynamics of physical systems, including systems that implement single-valued functions like a computer's update step. However, many such functions cannot be implemented by any master equation, even approximately, which raises the question of how they can occur in the real world. Here we show how any function over some "visible" states can be implemented with master equation dynamics--if the dynamics exploits additional, "hidden" states at intermediate times. We also show that any master equation implementing a function can be decomposed into a sequence of "hidden" timesteps, demarcated by changes in what state-to-state transitions have nonzero probability. In many real-world situations there is a cost both for more hidden states and for more hidden timesteps. Accordingly, we derive a "space-time" tradeoff between the number of hidden states and the number of hidden timesteps needed to implement any given function.

17 pages, 2 figures

References in corpus (4)

• High-precision test of Landauer's principle in a feedback trap
• Finite-time erasing of information stored in fermionic bits
• Minimum energetic cost to maintain a target nonequilibrium state
• Number of hidden states needed to physically implement a given conditional distribution

Cited by in corpus (12)

• Thermodynamics of computing with circuits
• Macroscopic Stochastic Thermodynamics
• Information engine in a nonequilibrium bath
• Quantum advantage in simulating stochastic processes
• Thermodynamic costs of Turing Machines
• Uncertainty relations and fluctuation theorems for Bayes nets
• Thermodynamics of computations with absolute irreversibility, unidirectional transitions, and stochastic computation times
• Probing the Theoretical and Computational Limits of Dissipative Design
• Landauer Principle and Thermodynamics of Computation
• Biochemical Szilard engines for memory-limited inference
• Entropy production given constraints on the energy functions
• Quantum-embeddable stochastic matrices