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 .
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 .
A
finite
R
in various scenarios in
often in the
A
more generally
R
feedback-control protocol, or Maxwellian
feedback controller, or Maxwell
R
is known that there are classes of conditional distributions that
was previously known that some conditional distributions
R
time-inhomogeneous master equation dynamics involving
master equation that involves
R
Here
However, here
R
however be implemented if the master equation dynamics has access to
in fact be implemented---if
D
,
R
. We investigate how the
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
D
such
R
implement some P in a thermodynamically reversible manner depends on P. We provide exact results in
do so. We calculate this cost exactly for
R
of conditional distributions that represent
where P represents a
R
functions. In the general case, we
function, and
R
on the needed number of hidden states
for the general case,
R
In particular, we show that if there are no constraints on what master equation we can construct, then
These results show that
R
(
, thus
R
)
,
R
carry out
implement
R
zero entropy production.
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.)
R
additional states available
hidden states
D
. 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