Thermodynamics of computations with absolute irreversibility, unidirectional transitions, and stochastic computation times
arXiv:2307.05713 · doi:10.1103/PhysRevX.14.021026
Abstract
Developing a thermodynamic theory of computation is a challenging task at the interface of non-equilibrium thermodynamics and computer science. In particular, this task requires dealing with difficulties such as stochastic halting times, unidirectional (possibly deterministic) transitions, and restricted initial conditions, features common in real-world computers. Here, we present a framework which tackles all such difficulties by extending the martingale theory of non-equilibrium thermodynamics to generic non-stationary Markovian processes, including those with broken detailed balance and/or absolute irreversibility. We derive several universal fluctuation relations and second-law-like inequalities that provide both lower and upper bounds on the intrinsic dissipation (mismatch cost) associated with any periodic process -- in particular the periodic processes underlying all current digital computation. Crucially, these bounds apply even if the process has stochastic stopping times, as it does in many computational machines. We illustrate our results with exhaustive numerical simulations of deterministic finite automata (DFA) processing bit strings, one of the fundamental models of computation from theoretical computer science. We also provide universal equalities and inequalities for the acceptance probability of words of a given length by a deterministic finite automaton in terms of thermodynamic quantities, and outline connections between computer science and stochastic resetting. Our results, while motivated from the computational context, are applicable far more broadly.
arXiv comment24 + 8 pages, 10 figures; v2: minor changes, references added; v3: presentation improved, extra appendix added, footnotes and references added
References in corpus (71)
- Stochastic thermodynamics, fluctuation theorems, and molecular machines
- Thermodynamic uncertainty relation for biomolecular processes
- Steady State Thermodynamics of Langevin Systems
- Dissipation bounds all steady-state current fluctuations
- How far from equilibrium is active matter?
- Stochastic Resetting and Applications
- Dissipation: The phase-space perspective
- Entropy production as correlation between system and reservoir
- High-precision test of Landauer's principle in a feedback trap
- Three detailed fluctuation theorems
- The Three Faces of the Second Law: I. Master Equation Formulation
- Nonequilibrium Markov processes conditioned on large deviations
- Experimental realization of diffusion with stochastic resetting
- Estimating dissipation from single stationary trajectories
- Speed Limit for Classical Stochastic Processes
- Irreversibility in active matter systems: Fluctuation theorem and mutual information
- Path-integral analysis of fluctuation theorems for general Langevin processes
- Stochastic resetting in backtrack recovery by RNA polymerases
- Thermodynamic Unification of Optimal Transport: Thermodynamic Uncertainty Relation, Minimum Dissipation, and Thermodynamic Speed Limits
- Stochastic thermodynamics of computation
- Stochastic resetting: A (very) brief review
- Information-to-work conversion by Maxwell's demon in a superconducting circuit-QED system
- Finite-time Landauer principle
- Lower bounds on dissipation upon coarse graining
- Large work extraction and the Landauer limit in a continuous Maxwell demon
- Kinetic uncertainty relation
- Frenesy: time-symmetric dynamical activity in nonequilibria
- Thermodynamic and Logical Reversibilities Revisited
- Quantum fluctuation theorems for arbitrary environments: adiabatic and non-adiabatic entropy production
- Unified Approach to Classical Speed Limit and Thermodynamic Uncertainty Relation
- Nonequilibrium potential and fluctuation theorems for quantum maps
- Statistics of Infima and Stopping Times of Entropy Production and Applications to Active Molecular Processes
- Stochastic thermodynamics in the strong coupling regime: An unambiguous approach based on coarse-graining
- Integral Fluctuation Theorems for Stochastic Resetting Systems
- Stochastic thermodynamics with information reservoirs
- Information and thermodynamics: fast and precise approach to Landauer's bound in an underdamped micro-mechanical oscillator
- Thermodynamics of Gambling Demons
- Entropy Production in Open Systems: The Predominant Role of Intra-Environment Correlations
- Minimal Model of Stochastic Athermal Systems: Origin of Non-Gaussian Noise
- Variance Sum Rule for Entropy Production
- Integral Fluctuation Relations for Entropy Production at Stopping Times
- How dissipation constrains fluctuations in nonequilibrium liquids: Diffusion, structure and biased interactions
- Level 2 large deviation functionals for systems with and without detailed balance
- Minimum dissipation principle in stationary non equilibrium states
- Fluctuation theorems from Bayesian retrodiction
- Entropy production in systems with unidirectional transitions
- Non-Markovian quantum thermodynamics: laws and fluctuation theorems
- Quantum nonequilibrium equalities with absolute irreversibility
- Maxwell's Demon Based on a Single Qubit
- Dynamics of information erasure and extension of Landauer's bound to fast processes
- Kinetic uncertainty relation on first passage time for accumulated current
- Dependence of dissipation on the initial distribution over states
- Quantum Martingale Theory and Entropy Production
- Thermodynamic costs of Turing Machines
- Thermodynamics of stochastic Turing machines
- Initial-State Dependence of Thermodynamic Dissipation for any Quantum Process
- Martingale theory for housekeeping heat
- A Nernst heat theorem for nonequilibrium jump processes
- Number of hidden states needed to physically implement a given conditional distribution
- Calorimetry for active systems
- Inflow rate, a time-symmetric observable obeying fluctuation relations
- A space-time tradeoff for implementing a function with master equation dynamics
- Inequalities generalizing the second law of thermodynamics for transitions between non-stationary states
- State retrieval beyond Bayes' retrodiction
- Extreme value statistics of edge currents in Markov jump processes and their use for entropy production estimation
- An integral fluctuation theorem for systems with unidirectional transitions
- Dissipation reduction and information-to-measurement conversion in DNA pulling experiments with feedback protocols
- Martingale-induced local invariance in Progressive Quenching
- Survival and extreme statistics of work, heat, and entropy production in steady-state heat engines
- Stochastic thermodynamics and modes of operation of a ribosome: a network theoretic perspective
- Upper bound for quantum entropy production from entropy flux
Cited by in corpus (15)
- Is stochastic thermodynamics the key to understanding the energy costs of computation?
- Martingales for physicists: A treatise on stochastic thermodynamics and beyond
- Thermodynamic Bounds on Symmetry Breaking in Linear and Catalytic Biochemical Systems
- Broken detailed balance and entropy production in directed networks
- Landauer Principle and Thermodynamics of Computation
- Maximizing free energy gain
- Gambling Carnot Engine
- Thermodynamic bounds and symmetries in first-passage problems of fluctuating currents
- Autonomous Quantum Processing Unit: An Autonomous Thermal Computing Machine & its Physical Limitations
- Thermodynamic inference in molecular motors: a Martingale approach
- Thermodynamic characterization of message-passing: Framework and initial study
- Coarse-grained quantum thermodynamics: Observation-dependent quantities, observation-independent laws
- Thermodynamic Cost of Random-Time Protocols
- Join gate with memory in token-conserving Brownian circuits and the thermodynamic cost
- Improving the efficiency of finite-time memory erasure with potential barrier shaping