Number of hidden states needed to physically implement a given conditional distribution

Abstract

We consider the problem of how to construct a physical process over a finite state space $X$ that applies some desired conditional distribution $P$ to initial states to produce final states. This problem arises often in the thermodynamics of computation and nonequilibrium statistical physics more generally (e.g., when designing processes to implement some desired computation, feedback controller, or Maxwell demon). It was previously known that some conditional distributions cannot be implemented using any master equation that involves just the states in $X$. However, here we show that any conditional distribution $P$ can in fact be implemented---if additional "hidden" states not in $X$ are available. Moreover, we show that it is always possible to implement $P$ in a thermodynamically reversible manner. We then investigate a novel cost of the physical resources needed to implement a given distribution $P$: the minimal number of hidden states needed to do so. We calculate this cost exactly for the special case where $P$ represents a single-valued function, and provide an upper bound for the general case, in terms of the nonnegative rank of $P$. These results show that having access to one extra binary degree of freedom, thus doubling the total number of states, is sufficient to implement any $P$ with a master equation in a thermodynamically reversible way, if there are no constraints on the allowed form of the master equation. (Such constraints can greatly increase the minimal needed number of hidden states.) Our results also imply that for certain $P$ that can be implemented without hidden states, having hidden states permits an implementation that generates less heat.

16 pages, 2 figures

References in corpus (6)

• Ensemble and Trajectory Thermodynamics: A Brief Introduction
• Speed Limit for Classical Stochastic Processes
• Cost and Precision of Brownian Clocks
• Finite-time erasing of information stored in fermionic bits
• Is there a Floquet Lindbladian?
• Relations between Entropies Produced in Nondeterministic Thermodynamic Processes

Cited by in corpus (11)

• Thermodynamics of computing with circuits
• Uncertainty relations and fluctuation theorems for Bayes nets
• Thermodynamics of computations with absolute irreversibility, unidirectional transitions, and stochastic computation times
• Biochemical Szilard engines for memory-limited inference
• Non-Markovian Momentum Computing: Universal and Efficient
• Physical Limitations of Work Extraction from Temporal Correlations
• Affinity-dependent bound on the spectrum of stochastic matrices
• Entropy production given constraints on the energy functions
• Fluctuation theorems for multiple co-evolving systems
• Information bounds production in replicator systems
• Energy-Efficient Pseudo-Ratchet for Brownian Computers through One-Dimensional Quantum Brownian Motion