We consider the problem of implementing a given conditional distribution relating the states of a physical system at two separate times using a physical process with (potentially time-inhomogeneous) master equation dynamics . This problem arises implicitly in many nonequilibrium statistical physics scenarios, e.g., when designing processes to implement some desired computations , feedback-control protocols, and Maxwellian demons. However it is known that many such conditional distributions P over a state space X cannot be implemented using  master equation dynamics over just the states in X. Here we show that any conditional distribution P can be implemented---if the process has access to additional "hidden" states, not in X. In particular, we show that any conditional distribution can be implemented in a thermodynamically reversible manner (achieving zero entropy production) if there are enough hidden states available. We investigate how the minimal number of such  states needed to implement any P in a thermodynamically reversible manner depends on P. We provide exact results in the special case of conditional distributions that reduce to single-valued functions. For the fully general case, we provide an upper bound  in terms of the nonnegative rank of P. In particular, we show that  having access to one extra binary degree of freedom (doubling the  number of states) is sufficient to carry out any P  . Our results provide a novel type of bound on the physical resources needed to perform information processing---the size of a system's  state space.
We consider the problem of how to construct a physical process over a state space X that applies some desired conditional distribution P to initial states to produce final states . This problem arises in various scenarios in thermodynamics of computation and nonequilibrium statistical physics ( e.g., when designing processes to implement some desired computation , feedback-control protocol, or Maxwellian demon). It is known that there are classes of conditional distributions that cannot be implemented using any time-inhomogeneous master equation dynamics involving just the states in X. Here we show that any conditional distribution P can however be implemented if the master equation dynamics has access to additional "hidden" states, not in X. We investigate how the minimal number of such hidden states needed to implement some P in a thermodynamically reversible manner depends on P. We provide exact results in the special case of conditional distributions that represent single-valued functions. In the general case, we provide an upper bound on the needed number of hidden states in terms of the nonnegative rank of P. In particular, we show that if there are no constraints on what master equation we can construct, then having access to one extra binary degree of freedom (doubling the total number of states) is sufficient to carry out any P with zero entropy production . Our results also imply that for certain P that can be implemented without hidden states, having additional states available permits an implementation that generates less heat. These results can be seen as uncovering and investigating a novel type of cost of the physical resources needed to perform information processing---the size of a system's hidden state space.
R
implementing a given conditional distribution relating the states of a physical system at two separate times using a physical process with (potentially time-inhomogeneous) master equation dynamics
how to construct a physical process over a state space X that applies some desired conditional distribution P to initial states to produce final states
R
implicitly in many
in various scenarios in thermodynamics of computation and
R
scenarios,
(
R
computations
computation
R
protocols, and Maxwellian demons. However it
protocol, or Maxwellian demon). It
R
many such conditional distributions P over a state space X
there are classes of conditional distributions that
A
any time-inhomogeneous
R
over
involving
R
be implemented---if the process
however be implemented if the master equation dynamics
D
In particular, we show that any conditional distribution can be implemented in a thermodynamically reversible manner (achieving zero entropy production) if there are enough hidden states available.
A
hidden
R
any
some
R
reduce to
represent
R
For the fully
In the
A
on the needed number of hidden states
A
if there are no constraints on what master equation we can construct, then
A
total
A
with zero entropy production
R
provide
also imply that for certain P that can be implemented without hidden states, having additional states available permits an implementation that generates less heat. These results can be seen as uncovering and investigating
R
bound on
cost of
A
hidden