Thermodynamic costs reveal energy limits of logic circuits
The Thermodynamic Complexity of Circuits
Computational Complexity
Summary
This paper studies the extra heat produced when computers do irreversible calculations, which wastes energy beyond the fundamental minimum. The authors model logic circuits to measure this heat and find it very hard to minimize or approximate. They also discover that certain circuit designs use more or less energy, revealing a tradeoff between circuit depth and energy waste. They propose ways to sort data with minimal or even zero extra heat under specific conditions, improving understanding of the energy efficiency limits of computation.
What this means in practice
- •For hardware designers: Assess energy efficiency limits of different logic circuit designs to optimize heat generation in chips under real input distributions.
- •For systems engineers: Develop low-energy sorting algorithms by incorporating fault-tolerant network designs that minimize entropy production beyond classical limits.
A theory result. No direct application yet.
Authors
Anne Condon, David Doty, Niels Kornerup, David Soloveichik, David Wolpert
Abstract
When any physical system executes a logically irreversible (non-injective) step of a computation, the excess heat released over the Landauer limit is an energetic cost that cannot be recovered. In modern computers this cost vastly dwarfs the Landauer cost. Modern stochastic thermodynamics refers to this cost as the ``entropy production'' and has derived fundamental lower bounds on its value. Here we introduce a thermodynamic model of circuits using heat functions and investigate its entropy production, deriving new results on the thermodynamic complexity of circuits. We first show that computing the optimal heat functions for gates in a given circuit (minimizing the entropy production) is PP-complete and multiplicative approximation of those heat functions is NP-hard, but additive approximation admits a polynomial-time randomized algorithm. We give tight bounds for entropy production for certain specific families of circuits (on uniformly distributed inputs): an $n$-ary AND tree of depth $O(\log n)$ requires $Ω(n)$ entropy production, while a serial chain achieves $O(1)$ in an idealized model, showing an energy-depth tradeoff. The Batcher odd-even mergesort network on $n$ bits has $Θ(n)$ entropy production, asymptotically less than its $Θ(n \log^2 n)$ gate count. On random permutations of distinct integers its entropy production is $Θ(n \log^2 n)$, asymptotically exceeding the Landauer cost of sorting; but preceding it with Leighton and Plaxton's almost-sorting network reduces the total heat released to $O(n \log n)$. Finally, we show how to sort $n$ values with zero circuit entropy production over any exchangeable input distribution. Our framework also yields streamlined proofs of known results in stochastic thermodynamics on mismatch cost and modularity cost.