We consider the problem of constructing a physical system whose evolution implements some specified stochastic matrix. We restrict attention to physical systemswhose dynamics can be modeled with a time-inhomogeneous master equation over a finite state space, which includes many of the systems considered in stochastic thermodynamics. It is known that many stochastic matrices cannot be implemented by any master equation, even approximately. This raises the question of how they can arise in the real world. Here we investigate this question for the special case where the stochastic matrix being implemented is a (single-valued) function f. Examples range from logical gates in digital circuits to the (partial) function evaluated by an entire digital computer. As we show , any function f over a set of "visible" states X can be implemented--if the master equation implementing f has access to some additional "hidden" states not in X. Motivated by engineering considerations, we then consider a natural decomposition of any master equation that implements a given function into a sequence of "hidden" timesteps, demarcated by changes in the set of allowed transitions between states. We demonstrate a fundamental tradeoff between the number of hidden states and the number of hidden timesteps needed to implement any given f using master equation dynamics. These tradeoffs are analogous to space / time tradeoffs in theoretical computer science. They can also be viewed as a type of resource theory, applying to master equation models of physical systems rather than quantum computation .
Master equations are commonly used to model the dynamics of physical systems. Surprisingly, many deterministic maps x \rightarrow f(x) cannot be implemented by any master equation, even approximately. This raises the question of how they arise in real-world systems like digital computers. We show that any deterministic map over some "visible" states can be implemented with a master equation--but only if additional "hidden" states are dynamically coupled to those visible states. We also show that any master equation implementing a given map can be decomposed into a sequence of "hidden" timesteps, demarcated by changes in what transitions are allowed under the rate matrix. Often there is a real-world cost for each additional hidden state, and for each additional hidden timestep. We derive the associated "space/time" tradeoff between the numbers of hidden states and of hidden timesteps needed to implement any given f (x) .
R
We consider the problem of constructing a physical system whose evolution implements some specified stochastic matrix. We restrict attention to physical systemswhose dynamics can be modeled with a time-inhomogeneous master equation over a finite state space, which includes many of the systems considered in stochastic thermodynamics. It is known that many stochastic matrices
Master equations are commonly used to model the dynamics of physical systems. Surprisingly, many deterministic maps x \rightarrow f(x)
R
can arise in the real world. Here we investigate this question for the special case where the stochastic matrix being implemented is a (single-valued) function f. Examples range from logical gates in digital circuits to the (partial) function evaluated by an entire digital computer. As we show , any function f over a set of
arise in real-world systems like digital computers. We show that any deterministic map over some
R
X can be implemented--if the master equation implementing f has access to some
can be implemented with a master equation--but only if
R
not in X. Motivated by engineering considerations, we then consider a natural decomposition of
are dynamically coupled to those visible states. We also show that
R
that implements a given function
implementing a given map can be decomposed
R
the set of allowed transitions between states. We demonstrate a fundamental
what transitions are allowed under the rate matrix. Often there is a real-world cost for each additional hidden state, and for each additional hidden timestep. We derive the associated "space/time"
R
number
numbers
D
the number
R
using master equation dynamics. These tradeoffs are analogous to space / time tradeoffs in theoretical computer science. They can also be viewed as a type of resource theory, applying to master equation models of physical systems rather than quantum computation
(x)