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

We consider the problem of constructing 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 the thermodynamics of computation and nonequilibrium statistical physics (e.g., when designing processes to implement some desired computation, feedback-control protocol, etc.). It is known that there are conditional distributions that cannot be implemented using any master equation involving just the states in X. Here we show that any conditional distribution P can be implemented if additional “hidden” states are available, and provide an upper bound on how many such states are required to implement any P in a thermodynamically reversible manner. Our results 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 a novel type of cost of the physical resources needed to perform information processing—the size of a system’s hidden state space.