Hacker News Reader

Comment by cperciva | Hacker News Reader

A 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).

Impressive work! You give me hope that we'll be able to continue scaling computing in domains which require it.

Also makes me wonder if Google's DWave could be more similar to this method rather than true quantum computing.

The time-energy trade off is of particular interest to me. I’m a roboticist, but I’ve been looking at adapting similar thermodynamic results to research problems in my field (Crooks’ work has been quite inspirational). I’m looking forward to reading this paper in greater detail in a few days when I have time (I’m in the middle of a move) and might want to get in touch about research ideas if that’s of interest.

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.

You can come close to that time complexity on a single CPU by using multigrid methods.

https://en.wikipedia.org/wiki/Multigrid_method

Unless of course your matrix has a prohibitively complicated structure.

Reply on news.ycombinator.com