A classical computer can solve a linear system in O(N) time on O(N^2) processors, too.
Here there are N cells with N^2 couplings. So as you say, a normal computer with this many processors could also solve a linear system in O(N sqrt(kappa)) time. (Using conjugate gradient, since matrix-vector-mult on the system would be O(N) time.)
However, (1) these thermodynamic cells are much simpler than processors, and (2) it seems the overall energy required to simulate the SDE, once the couplings are initialized, only scales with O(N), not O(N^2) as in your digital case.
Thanks. Do you have somewhere a demo of the hardware performing these computations?
We do not (yet?). Here is a simulation I made of similar hardware demonstrating the equilibration step of the algorithm https://app.normalcomputing.ai/composer/playground
The RC circuit looks familiar. Is it related to neuromorphic computing hardware? Can it be implemented with existing hardware?
An interesting feature of this approach is that the proposed hardware doesn't rely on non-linear elements, memristors, or even active elements (besides an optional noise source). It is simply a passive network of oscillators with a DC bias on each cell. That said, the hardware to implement this at scale does not currently seem to exist. To my knowledge, the state of the art is https://app.normalcomputing.ai/composer
From what I see, it's like mimicking the annealing process and the "derivative" automatically drives you to the solution. If that's the case, implementing such hardware should be not that hard except for the programmable coupling part. A bit off-topic, this reminds me of the duality between any deep forward network and a modern Hopfield network with some special energy functions, in which the duality is based on the fact that the forward running process can be seen as an energy minimization process.
This is very interesting, especially considering the energy-time tradeoff. I wonder how it compares to optical computing [1], where FFT can be done efficiently [2], or to analog computing for linear algebra [3].
This is very interesting, especially considering the energy-time tradeoff. I wonder how it compares to optical computing [1], where FFT can be done efficiently [2], or to analog computing for linear algebra [3]. [1]: https://en.wikipedia.org/wiki/Optical_computing#Optical_Four... [2]: https://doi.org/10.1038/s41598-017-13733-1 [3]: https://doi.org/10.1109/MM.2017.55
Had a quick read of [3]. This work comments on three contributions to the error in an analog scheme to solve linear systems via an ODE that is encoded in the circuit dynamics, although the specific ODE being solved is not given in the paper. The three sources addressed are: gain error, offset error, and nonlinearity. It is mentioned that the first two can be corrected by calibration, while the nonlinearity error can be mitigated by scaling down the inputs to the problem (the matrix A and vector b in the equation Ax = b). It says that scaling down the problem results in lower accuracy, which I suspect can be captured by the tradeoff we show analytically between time, energy, and accuracy. It is also mentioned that “when the analog accelerator outputs are steady, we can sample the solutions once with higher-precision ADCs. However, the method here does not involve time-averaging the output of the circuit. A core result of our paper is that the accuracy converges with the length of time over which the output is averaged, so I suspect that taking a single sample is a drawback of the method presented here.
An interesting feature of this approach is that the proposed hardware doesn't rely on non-linear elements, memristors, or even active elements (besides an optional noise source). It is simply a passive network of oscillators with a DC bias on each cell. That said, the hardware to implement this at scale does not currently seem to exist. To my knowledge, the state of the art is https://app.normalcomputing.ai/composer
From what I see, it's like mimicking the annealing process and the "derivative" automatically drives you to the solution. If that's the case, implementing such hardware should be not that hard except for the programmable coupling part. A bit off-topic, this reminds me of the duality between any deep forward network and a modern Hopfield network with some special energy functions, in which the duality is based on the…
The relationship with Hopfield networks sounds fascinating, would love to discuss further. As you mentioned, there is a connection to annealing in that we are encoding the solution to our problem in the minimization of a physical system's energy. Indeed, the all-to-all coupling is the hard part!
Isn't there a relation between entropy and computation? It would be interesting to see how these are related.
Definitely. Landauer's principle gives a lower bound on the amount of energy a computation requires, which is k_B T ln(2) times the number of bits erased in the process, the decrease in Shannon entropy. Our energy cost analysis is not based on the Landauer limit, but simply on the energy difference between equilibrium states. But our algorithm for estimating the determinant is based on effectively measuring the entro…
I always have trouble thinking of computation in terms of “bits erased”. How many bits are erased when I sort an array? Or invert a matrix? Or compute a function like f(x)=1, which seems to maximally erase information, but doesn’t intuitively seem like it should cost a lot of energy.
Thanks. Do you have somewhere a demo of the hardware performing these computations?
We do not (yet?). Here is a simulation I made of similar hardware demonstrating the equilibration step of the algorithm https://app.normalcomputing.ai/composer/playground