[jeremysalwen]

I'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?

[thomasahle]

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.

[farissbahi]

Great explanation!

[aifer4]

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.

[hiddencost]

https://arxiv.org/abs/quant-ph/0502072

Your comment reminded me of this classic of the genre.

An extremely approachable read.