The Thermodynamic Complexity of Circuits
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 log2 n) gate count. On random permutations of distinct integers its entropy production is Θ(n log2 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.
Related
- One Gate at a Time: Complexity Growth in Random Quantum Circuits
- Complexity of tensor network simulation for noisy quantum circuits
- Bounded decoding complexity in transversal circuits with magic state injection
- Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?
- Thermodynamic speed limits in isolated quantum systems
BibTeX
@misc{condon2026thermodynamic,
title = {{The Thermodynamic Complexity of Circuits}},
author = {Anne Condon and David Doty and Niels Kornerup and David Soloveichik and David Wolpert},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33193},
eprint = {2610.33193},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33193},
}
RIS
TY - UNPB
TI - The Thermodynamic Complexity of Circuits
AU - Anne Condon
AU - David Doty
AU - Niels Kornerup
AU - David Soloveichik
AU - David Wolpert
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.33193
UR - https://arxiv.org/abs/2610.33193
AB - 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.
ER -