Entropy and computational complexity

Question

There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, computational complexity $F(n) $ is correlated to the average consumption of energy, hope I can get some answer here.

Answer 1

Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there is an important difference between energy needed to make a computation run, and entropy generated by the computation and put out into the environment, typically in the form of heat.)

Based on Landauer and Bennett's original analysis that erasing a bit "must" generate $kT \ln(2)$ entropy (see below for why there are scare-quotes), several researchers have pursued various questions along these lines. One line of research was to simulate irreversible Turing machines by reversible ones, which, it was suggested, would generate no entropy. There are several works showing space-time tradeoffs for how to simulate irreversible TMs by reversible ones, e.g.:

• Bennett, Time/Space Trade-Offs for Reversible Computation. SICOMP 1989

• Levine & Sherman. A Note on Bennett’s Time-Space Tradeoff for Reversible Computation. SICOMP 1990.

• Li & Vitanyi. Reversible simulation of irreversible computation. CCC 1996

• Lange, McKenzie, and Tapp. Reversible Space Equals Deterministic Space. JCSS 2000.

More recently,

Demaine, Lynch, Mirano, and Tyagi. Energy-Efficient Algorithms, 2016.

studied partially reversible algorithms - that is, if you are willing to pay some entropy, for standard algorithmic tasks can one improve upon the general irreversible-to-reversible simulations mentioned above. Reversible computing has a whole community of researchers devoted to it, viz. the Reversible Computing conference, now in its 10th year.

It has actually been known for a long time, going all the way back to Landauer and Bennett, that the relationship between computational irreversibility and entropy generation is more subtle than is suggested by the tagline "erasing a bit generates $\ln(2)$ entropy." However, in the past 20 years or so nonequilibrium statistical mechanics has advanced to the point that this more subtle relationship can be captured by precise numerical equations involving not just entropy difference, but also a difference of KL divergences, see

Kolchinsky & Wolpert, Dependence of dissipation on the initial distribution over states. J. Stat. Mech. 2017 (arXiv link)

(and references therein).

We hosted a workshop on this at the Santa Fe Institute in August 2017 (where you can see the names of some researchers and talk titles of relevance), and it raises a whole new set of questions in both physics and thermodynamic computational complexity.