3 ms·

I've heard complaints about other alternative computing approaches in that they rely on the assumption of arbitrarily precise measurements, which ends up being

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?

aifer4 3y ago
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 3y ago
https://arxiv.org/abs/quant-ph/0502072 https://arxiv.org/abs/quant-ph/0502072 Your comment reminded me of this classic of the genre. An extremely approachable read.
thomasahle 3y ago
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 3y ago
  Great explanation!

aifer4 3y ago

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 3y ago

https://arxiv.org/abs/quant-ph/0502072 https://arxiv.org/abs/quant-ph/0502072 Your comment reminded me of this classic of the genre. An extremely approachable read.

thomasahle 3y ago

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 3y ago
Great explanation!