Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Entropy Production and Heat Functions: The thermodynamic complexity of circuit computation

Joint Math/CS Theory

Speaker: Dave Doty, UC Davis, Computer Science
Location: 1131 Kemper
Start time: Mon, Sep 28 2026, 4:10PM

Description

Modern stochastic thermodynamics identifies entropy production---excess of heat released over the so-called "Landauer cost" associated with executing logically irreversible (non-injective) steps---as the unrecoverable energetic cost of a computation.  We define a thermodynamic model of circuits based on thermodynamically valid heat functions, which assign to each gate the heat it releases on any given input.  We require our circuits to compute cleanly, erasing their inputs and all intermediate values.  This framework enables new results on the thermodynamic complexity of circuits.  We show that a clean sorting circuit (not a sorting network) can sort n values with zero circuit entropy production by exploiting correlations between the input and the sorted output during erasure.  Computing optimal heat functions for gates in a given circuit (minimizing total entropy production over the uniform input distribution) is PP-complete, multiplicative approximation is NP-hard, but additive approximation admits a polynomial-time randomized algorithm.

Results in the paper I probably won't have time to discuss:

We give tight bounds for entropy production for certain families of circuits (on uniformly distributed inputs): an n-ary AND tree of depth O(log n) requires Omega(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 Theta(n) entropy production, asymptotically less than its Theta(n log^2 n) gate count.  On random permutations of distinct integers its entropy production is Theta(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).  Our framework also yields streamlined proofs of known results in stochastic thermodynamics on mismatch cost and modularity cost.

Joint work with Anne Condon, Niels Kornerup, David Soloveichik, and David Wolpert.