Excerpt

Introduction

In this chapter, I give a quick overview of some of the theoretical background necessary for using modern nonequilibrium statistical physics to investigate the thermodynamics of computation. I begin by presenting some general terminology, and then I review some of the most directly relevant concepts from information theory. Next I introduce several of the most important kinds of computational machines studied in computer science theory. After this I summarize the parts of nonequilibrium statistical physics (more precisely, stochastic thermodynamics; see Seifert (2012), Van den Broeck and Esposito (2015), and Esposito and Van den Broeck (2010b)) that are necessary for analyzing the thermodynamics of such computational machines. The interested reader is directed to Wolpert (2019) for a more detailed overview.

The key tool provided by stochastic thermodynamics is a decomposition of the entropy flow out of any open physical system that implements some desired map π on some initial distribution p0, into the sum of three terms (Wolpert and Kolchinsky 2018):

1. The Landauer cost of π. This is an information-theoretic quantity: the drop in Shannon entropy of the actual distribution over the states of the system as the system evolves. The Landauer cost depends only on π and p0, being independent of the precise details of the physical system implementing π.

2. The mismatch cost of implementing π with a particular physical system. This is also an information-theoretic quantity: a drop in Kullback–Leibler distance, between p0 and a counterfactual “prior” distribution q0, as those distributions both get transformed by π. The mismatch cost depends only on π, p0, and q0, being independent of any details of the physical system implementing π that are not captured in q0.

3. The residual entropy production due to using a particular physical system. This is a linear term that depends on the graph-theoretic nature of π, on p0, and on the precise details of the physical system implementing π.

This decomposition allows us to analyze how the thermodynamic costs of a fixed computational device vary if we change the physical environment of that device, that is, change the distribution of inputs to the device. This decomposition also plays a key role in analyzing the thermodynamics of systems with multiple components that are interconnected, since the physical environments of each of those components will depend on the logical maps performed by the “upstream” components (Wolpert and Kolchinsky 2018; Wolpert 2019; Grochow and Wolpert 2018).

Bibliography

Aaronson, S. 2005. “NP-Complete Problems and Physical Reality.” Quant-ph/0502072.

————. 2013. “Why Philosophers Should Care About Computational Complexity.” Computability: Turing, Gödel, Church, and Beyond: 261–327.

Arora, S., and B. Barak. 2009. Computational Complexity: A Modern Approach. Cambridge University Press.

Baez, J., and M. Stay. 2012. “Algorithmic Thermodynamics.” Mathematical Structures in Computer Science 22 (05): 771–787.

Barnett, N., and J. P. Crutchfield. 2015. “Computational Mechanics of Input–Output Processes: Structured Transformations and the ϵ-Transducer.” Journal of Statistical Physics 161 (2): 404–451.

Barrow, J. D. 2011. “Gödel and Physics.” In Kurt Gödel and the Foundations of Mathematics: Horizons of Truth, edited by M. Baaz, C. H. Papadimitriou, H. W. Putnam, D. S. Scott, and C. L. Harper Jr., 255. Cambridge University Press.

Bennett, C. H. 1973. IBM Journal of Research and Development 17:525–532.

————. 1982. “The Thermodynamics of Computation—A Review.” International Journal of Theoretical Physics 21 (12): 905–940.

Boyd, A. B. 2018. “Thermodynamics of Modularity: Structural Costs Beyond the Landauer Bound.” Physical Review X 8 (3).

Caves, C. M. 1990. “Entropy and Information: How Much Information is Needed to Assign a Probability.” Complexity, Entropy and the Physics of Information: 91–115.

————. 1993. “Information and Entropy.” Physical Review E 47 (6): 4010.

Cover, T. M., and J. A. Thomas. 2012. Elements of Information Theory. John Wiley & Sons. Accessed January 11, 2014.

Deffner, S., and C. Jarzynski. 2013. “Information Processing and the Second Law of Thermodynamics: An Inclusive, Hamiltonian Approach.” Physical Review X 3 (4): 041003.

Drechsler, R., and R. Wille. 2012. “Reversible Circuits: Recent Accomplishments and Future Challenges for an Emerging Technology.” In Progress in VLSI Design and Test, 383–392. Springer.

Esposito, M., R. Kawai, K. Lindenberg, and C. Van den Broeck. 2010. “Finite-Time Thermodynamics for a Single-Level Quantum Dot.” EPL (Europhysics Letters) 89 (2): 20003.

Esposito, M., K. Lindenberg, and C. Van den Broeck. 2009. “Thermoelectric Efficiency at Maximum Power in a Quantum Dot.” EPL (Europhysics Letters) 85 (6): 60010.

————. 2010. “Entropy Production as Correlation between System and Reservoir.” New Journal of Physics 12 (1): 013013.

Esposito, M., and C. Van den Broeck. 2010a. “Three Detailed Fluctuation Theorems.” ArXiv: 0911.2666, Physical Review Letters 104, no. 9 (March). Accessed January 23, 2018. http://arxiv.org/abs/0911.2666.

————. 2010b. “Three Faces of the Second Law. I. Master Equation Formulation.” Physical Review E 82 (1): 011143.

————. 2011. “Second Law and Landauer Principle Far from Equilibrium.” EPL (Europhysics Letters) 95 (4): 40004.

Frank, M. P. 2005. “Introduction to Reversible Computing: Motivation, Progress, and Challenges.” In Proceedings of the 2nd Conference on Computing Frontiers, 385–390. ACM.

Fredkin, E., and T. Toffoli. 1982. “Conservative Logic.” Internat. J. Theoret. Phys. 21 (3): 219–253.

Grochow, J., and D. H. Wolpert. 2018. “Beyond Number of Bit Erasures: New Complexity Questions Raised by Recently Discovered Thermodynamic Costs of Computation.” ACM SIGACT News.

Hasegawa, H.-H., J. Ishikawa, K. Takara, and D. J. Driebe. 2010. “Generalization of the Second Law for a Nonequilibrium Initial State.” Physics Letters A 374 (8): 1001–1004.

Hopcroft, J. E., R. Motwani, and U. Rotwani. 2000. JD: Introduction to Automata Theory, Languages and Computability.

Ito, S., and T. Sagawa. 2013. “Information Thermodynamics on Causal Networks.” Physical Review Letters 111 (18): 180603.

————2015. “Information Flow and Entropy Production on Bayesian Networks.” ArXiv: 1506.08519, arXiv:1506.08519 [cond-mat] (June). Accessed July 19,2017.

Jarzynski, C. 2011. “Equalities and Inequalities: Irreversibility and the Second Law of Thermodynamics at the Nanoscale.” Annu. Rev. Condens. Matter Phys. 2 (1): 329–351. Accessed January 13, 2016.

Kolchinsky, A., and D. H. Wolpert. 2017. “Dependence of Dissipation on the Initial Distribution over States.” Journal of Statistical Mechanics: Theory and Experiment: 083202.

Koller, D., and N. Friedman. 2009. Probabilistic Graphical Models. MIT Press.

Landauer, R. 1961. “Irreversibility and Heat Generation in the Computing Process.” IBM Journal of Research and Development 5 (3): 183–191.

Li, M., and P. Vitanyi. 2008. An Introduction to Kolmogorov Complexity and Its Applications. Springer.

Mandal, D., and C. Jarzynski. 2012. “Work and Information Processing in a Solvable Model of Maxwell's Demon.” Proceedings of the National Academy of Sciences 109 (29): 11641–11645.

Maroney, O. J. E. 2005. “The (Absence of a) Relationship between Thermodynamic and Logical Reversibility.” Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 36, no. 2 (June): 355–374.

Moore, C., and S. Mertens. 2011. The Nature of Computation. Oxford University Press.

Nekrashevych, V. 2005. Self-Similar Groups. Vol. 117. Mathematical Surveys and Monographs. American Mathematical Society.

Ouldridge, T., R. Brittain, and P. R. ten Wolde. 2019. “The Power of Being Explicit: Demystifying Work, Heat, and Free Energy in the Physics of Computation.” In The Energetics of Computing in Life and Machines, edited by D. H. Wolpert, C. P. Kempes, P. Stadler, and J. Grochow. SFI Press.

Owen, J. A., A. Kolchinsky, and D. H. Wolpert. 2018. “Number of Hidden States Needed to Physically Implement a Given Conditional Distribution.” New Journal of Modern Physics.

Parrondo, J. M. R., J. M. Horowitz, and T. Sagawa. 2015. “Thermodynamics of Information.” Nature Physics 11 (2): 131–139.

Perumalla, K. S. 2013. Introduction to Reversible Computing. CRC Press.

Pietzonka, P., and U. Seifert. 2018. “Universal Trade-Off between Power, Efficiency, and Constancy in Steady-State Heat Engines.” Physical Review Letters 120 (19): 190602.

Riechers, P. 2019. “Transforming Metastable Memories: The Nonequilibrium Thermodynamics of Computation.” In The Energetics of Computing in Life and Machines, edited by D. H. Wolpert, C. P. Kempes, P. Stadler, and J. Grochow. SFI Press.

Sagawa, T. 2014. “Thermodynamic and Logical Reversibilities Revisited.” Journal of Statistical Mechanics: Theory and Experiment 2014 (3): P03025.

Savage, J. E. 1998. Models of Computation. Vol. 136. Addison-Wesley.

Seifert, U. 2012. “Stochastic Thermodynamics, Fluctuation Theorems and Molecular Machines.” Rep. Progress Phys. 75 (12): 126001.

Van den Broeck, C., and M. Esposito. 2015. “Ensemble and Trajectory Thermodynamics: A Brief Introduction.” Physica A: Statistical Mechanics and its Applications 418:6–16.

Van den Broeck, C., and R. Toral. 2015. “Stochastic Thermodynamics for Linear Kinetic Equations.” Physical Review E 92 (1): 012127.

Wolpert, D. H. 2015. “Extending Landauer's Bound from Bit Erasure to Arbitrary Computation.” ArXiv:1508.05319 [cond-mat.stat-mech].

————. 2016a. “Correction: Wolpert, D. H. The Free Energy Requirements of Biological Organisms; Implications for Evolution. Entropy 2016, 18, 138.” Entropy 18 (6): 219.

————. 2016b. “The Free Energy Requirements of Biological Organisms: Implications for Evolution.” Entropy 18 (4): 138.

————. 2019. “The Stochastic Thermodynamics of Computation.” Journal of Physics A: Mathematical and Theoretical.

Wolpert, D. H., and A. Kolchinsky. 2018. “The Entropic Costs of Straight-Line Circuits.” arXiv preprint arXiv:1806.04103.

Zurek, W. H. 1989. “Algorithmic Randomness and Physical Entropy.” Phys. Rev. A 40 (8): 4731–4751.

BACK TO The Energetics of Computing in Life & Machines