Linear thermodynamic algebra (solving linear systems in O(n))

Abstract: Linear algebraic primitives are central to many modern algorithms in engineering, science, and machine learning. Therefore, accelerating these primitives with new computer hardware would have a huge economic impact. Quantum computing has been proposed for this purpose, although the resource requirements are far beyond current technological capabilities, so this approach remains long term in the time scale. Here, we consider an alternative physics-based computing paradigm based on classical thermodynamics, to provide a short-term approach to accelerating linear algebra. At first glance, thermodynamics and linear algebra appear to be unrelated fields. In this work, we relate the solving of linear algebra problems to the sampling of the thermodynamic equilibrium distribution of a system of coupled harmonic oscillators. We present simple thermodynamic algorithms for (1) solving linear systems of equations, (2) computing matrix inverses, (3) computing matrix determinants, and (4) solving Lyapunov equations. Under reasonable assumptions, we rigorously establish asymptotic speedups for our algorithms, relative to numerical methods, which scale linearly in the matrix dimension. Our algorithms exploit thermodynamic principles such as ergodicity, entropy, and equilibration, highlighting the deep connection between these two seemingly distinct domains and opening up algebraic applications for thermodynamic computing hardware.