We consider the problem of constructing a physical system that evolves according to some specified conditional distribution . We restrict attention to physical systems that can be modeled as a time-inhomogeneous continuous-time Markov chain (CTMC) over a finite state space, which includes many of the systems considered in stochastic thermodynamics. Examples range from constructing a logical gate to be used in a digital circuit to constructing an entire digital computer. It is known that many conditional distributions over a space X cannot be implemented by any CTMC , even approximately. This raises the question of how they can arise in the real world. Here we focus on the case where the conditional distribution is a (single-valued) function f. Any f over a set of "visible" states X can be implemented --- if the system has access to some additional "hidden" states not in X. Motivated by engineering considerations, we  consider a natural decomposition of any such CTMC into a sequence of "hidden" timesteps, demarcated by changes in the set of allowed transitions between states. We demonstrate a  tradeoff between the number of hidden states and the number of hidden timesteps needed to implement any given f using a CTMC, analogous to space / time tradeoffs in theoretical computer science  .
We consider the problem of constructing a physical system whose evolution implements some specified stochastic matrix . We restrict attention to physical systems whose 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 .
R
that evolves according to some specified conditional distribution
whose evolution implements some specified stochastic matrix
R
that
whose dynamics
R
as
with
R
continuous-time Markov chain (CTMC)
master equation
D
Examples range from constructing a logical gate to be used in a digital circuit to constructing an entire digital computer.
R
conditional distributions over a space X
stochastic matrices
R
CTMC
master equation
R
focus on the
investigate this question for the special
R
conditional distribution
stochastic matrix being implemented
R
Any
Examples range from logical gates in digital circuits to the (partial) function evaluated by an entire digital computer. As we show, any function
R
implemented --- if the system
implemented--if the master equation implementing f
A
then
R
such CTMC
master equation that implements a given function
A
fundamental
R
a CTMC,
master equation dynamics. These tradeoffs are
A
. They can also be viewed as a type of resource theory, applying to master equation models of physical systems rather than quantum computation