Thermodynamic Linear Algebra
arxiv.org
Thermodynamic Linear Algebra
1–10 of 60 posts
Re: Thermodynamic Linear Algebra
#2Latest research from https://normalcomputing.ai/. Feedback welcome!
Re: Thermodynamic Linear Algebra
#3I've heard complaints about other alternative computing approaches in that they rely on the assumption of arbitrarily precise measurements, which ends up being impossible or taking an extreme amount of time due to the way the physics of measurement works. Could you explain a bit why this is different?
Re: Thermodynamic Linear Algebra
#4I've heard complaints about other alternative computing approaches in that they rely on the assumption of arbitrarily precise measurements, which ends up being impossible or taking an extreme amount of time due to the way the physics of measurement works. Could you explain a bit why this is different?
Good question. There are different ways that errors come into analog computations, including thermal noise, measurement imprecision, and imprecision of the device's physical parameters. This work addresses thermal noise (which is always present at finite temperature), and provides algorithms which are indifferent to thermal noise, or even benefit from it. The other sources of error can, in principle, be made arbitrarily small (at least down to the quantum limit), but in practice are also limiting factors. Progress has been made on error mitigation methods to deal with these other sources of error, so stay tuned.
Re: Thermodynamic Linear Algebra
#5I've heard complaints about other alternative computing approaches in that they rely on the assumption of arbitrarily precise measurements, which ends up being impossible or taking an extreme amount of time due to the way the physics of measurement works. Could you explain a bit why this is different?
https://arxiv.org/abs/quant-ph/0502072
Your comment reminded me of this classic of the genre.
An extremely approachable read.
Re: Thermodynamic Linear Algebra
#6I've heard complaints about other alternative computing approaches in that they rely on the assumption of arbitrarily precise measurements, which ends up being impossible or taking an extreme amount of time due to the way the physics of measurement works. Could you explain a bit why this is different?
Notice that the complexity depends on the error as eps^(-2), since the method is based on integrating a stochastic differential equation (SDE) over time. So this is an approximation algorithm, and not something that requires "arbitrarily precise measurements".
You could simulate the SDE digitally, but you would probably need d^2 time per iteration, where this approach just initializes the systems and waits for it to converge to a sufficient precision. Turns out the convergence time depends on sqrt(condition number) similar to the best iterative linear solvers, conjugate gradient (CG).
You can debate whether it's fair to assume a fully connected d^2 chip, since a similar size cpu or gpu could perhaps do each iteration of CG in constant time, and so would have the same (or better) complexity as the thermodynamic method. However, each cell the the proposed chip is way simpler than a cpu cell, so it should be cheaper/more energy efficient.
Re: Thermodynamic Linear Algebra
#7A classical computer can solve a linear system in O(N) time on O(N^2) processors, too.
Re: Thermodynamic Linear Algebra
#8A classical computer can solve a linear system in O(N) time on O(N^2) processors, too.
[deleted]
Re: Thermodynamic Linear Algebra
#9I've heard complaints about other alternative computing approaches in that they rely on the assumption of arbitrarily precise measurements, which ends up being impossible or taking an extreme amount of time due to the way the physics of measurement works. Could you explain a bit why this is different?
Notice that the complexity depends on the error as eps^(-2), since the method is based on integrating a stochastic differential equation (SDE) over time. So this is an approximation algorithm, and not something that requires "arbitrarily precise measurements". You could simulate the SDE digitally, but you would probably need d^2 time per iteration, where this approach just initializes the systems and waits for it to…
Great explanation!
Re: Thermodynamic Linear Algebra
#10A classical computer can solve a linear system in O(N) time on O(N^2) processors, too.
This is an important observation, and is one of the reasons we included an energy-time tradeoff analysis in the paper. To our knowledge, this is the first result where the product energy * time has been shown to scale with dimension for solving linear systems of equations (in any computational paradigm).