Circuit complexity theory for thermodynamic resource costs

Computational complexity theory explores the scaling with input size of the resources required by running a computation, such as the number of iterations or memory cost. In particular, circuit complexity theory explores this issue for Boolean circuits, for the resource costs of number of gates or depth of the circuit. This scaling behavior is crucial for understanding the efficiency of algorithms and the inherent difficulty of problems, defining the boundaries of what can be feasibly computed in practice. However, no work in circuit complexity has considered the scaling behavior of the thermodynamic resource costs incurred when running a Boolean circuit.

In this work, we show how to extend the theory of circuit complexity to account for such thermodynamic costs. In particular, we use Mismatch cost (MMC) to lower bound the entropy production generated by running a given circuit. We demonstrate our closed-form expression for MMC of circuits by calculating MMC on a few circuits and establish the scaling behavior of MMC with circuit size. We show how this relationship changes when changing our assumptions on the distribution and independence of input bits and / or the fan-out of the gates of the circuit and / or the "jumping layers" of the outputs of gates.