Thermodynamic Linear Algebra

• URL: http://arxiv.org/abs/2308.05660v2
• Date: Mon, 10 Jun 2024 16:49:10 GMT
• Title: Thermodynamic Linear Algebra
• Authors: Maxwell Aifer, Kaelan Donatella, Max Hunter Gordon, Samuel Duffield, Thomas Ahle, Daniel Simpson, Gavin E. Crooks, Patrick J. Coles,
• Abstract summary: We consider an alternative physics-based computing paradigm based on classical thermodynamics to accelerate linear algebra. We present simple thermodynamic algorithms for solving linear systems of equations, computing matrix inverses, (3) computing matrix determinants, and (4) solving Lyapunov equations. Our algorithms exploit thermodynamic principles like ergodicity, entropy, and equilibration, highlighting the deep connection between these two seemingly distinct fields.
• Score: 0.7377893131680263
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Linear algebraic primitives are at the core of many modern algorithms in engineering, science, and machine learning. Hence, accelerating these primitives with novel computing hardware would have tremendous 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 timescale. Here we consider an alternative physics-based computing paradigm based on classical thermodynamics, to provide a near-term approach to accelerating linear algebra. At first sight, thermodynamics and linear algebra seem to be unrelated fields. In this work, we connect solving linear algebra problems to sampling from 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 digital methods, that scale linearly in matrix dimension. Our algorithms exploit thermodynamic principles like ergodicity, entropy, and equilibration, highlighting the deep connection between these two seemingly distinct fields, and opening up algebraic applications for thermodynamic computing hardware.

Related papers

• Quantum algorithms to simulate quadratic classical Hamiltonians and optimal control [0.0]
  We develop quantum algorithms to estimate quantities of interest in a given classical mechanical system. We consider the problem of designing optimal control of classical systems, which can be cast as the second variation of the Lagrangian. We give an efficient quantum algorithm to solve the Riccati differential equation well into the nonlinear regime.
  arXiv  Detail & Related papers  (2024-04-10T18:53:22Z)
• Thermodynamic Computing System for AI Applications [0.0]
  Physics-based hardware, such as thermodynamic computing, has the potential to provide a fast, low-power means to accelerate AI primitives. We present the first continuous-variable thermodynamic computer, which we call the processing unit (SPU)
  arXiv  Detail & Related papers  (2023-12-08T05:22:04Z)
• Thermodynamic Matrix Exponentials and Thermodynamic Parallelism [0.0]
  We show that certain linear algebra problems can be solved thermodynamically, leading to an speedup scaling with the matrix dimension. The origin of this "thermodynamic advantage" has not yet been fully explained, and it is not clear what other problems might benefit from it.
  arXiv  Detail & Related papers  (2023-11-21T18:10:33Z)
• CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra [62.37017125812101]
  We propose a simple but general framework for large-scale linear algebra problems in machine learning, named CoLA. By combining a linear operator abstraction with compositional dispatch rules, CoLA automatically constructs memory and runtime efficient numerical algorithms. We showcase its efficacy across a broad range of applications, including partial differential equations, Gaussian processes, equivariant model construction, and unsupervised learning.
  arXiv  Detail & Related papers  (2023-09-06T14:59:38Z)
• Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
  We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations. We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix. A quantum algorithm to simulate the dynamics of the density matrix is proposed.
  arXiv  Detail & Related papers  (2023-06-14T23:08:51Z)
• Temporal Entanglement in Chaotic Quantum Circuits [62.997667081978825]
  The concept of space-evolution (or space-time duality) has emerged as a promising approach for studying quantum dynamics. We show that temporal entanglement always follows a volume law in time. This unexpected structure in the temporal entanglement spectrum might be the key to an efficient computational implementation of the space evolution.
  arXiv  Detail & Related papers  (2023-02-16T18:56:05Z)
• Thermodynamic AI and the fluctuation frontier [0.0]
  Many Artificial Intelligence (AI) algorithms are inspired by physics and employ fluctuations. We propose a novel computing paradigm, where software and hardware become inseparable. We identify bits (s-bits) and modes (s-modes) as the respective building blocks for discrete and continuous Thermodynamic AI hardware.
  arXiv  Detail & Related papers  (2023-02-09T17:18:36Z)
• A near-term quantum algorithm for solving linear systems of equations based on the Woodbury identity [0.602276990341246]
  We describe a quantum algorithm for solving linear systems of equations that avoids problems such as barren plateaus and local optima. Our algorithm is based on the Woodbury identity, which analytically describes the inverse of a matrix that is a low-rank modification of another (easily-invertible) matrix. We estimate the inner product involving the solution of a system of more than 16 million equations with 2% error using IBM's Auckland quantum computer.
  arXiv  Detail & Related papers  (2022-05-02T04:32:01Z)
• Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
  We propose quantum algorithms for matrix operations using the "Sender-Receiver" model. These quantum protocols can be used as subroutines in other quantum schemes.
  arXiv  Detail & Related papers  (2022-02-10T08:12:20Z)
• Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms [74.17312533172291]
  We describe a method for mapping any finite nonlinear dynamical system to an infinite linear dynamical system (embedding) We then explore an approach for approximating the resulting infinite linear system with finite linear systems (truncation)
  arXiv  Detail & Related papers  (2020-12-12T00:01:10Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.