3 ms·
Wait, aren't linear equation systems solvable in N^3 where N is number of equations/variables? Why do they claim exponential improvement?
by lostmsu 9y ago
Wait, aren't linear equation systems solvable in N^3 where N is number of equations/variables? Why do they claim exponential improvement?
- cvoss 9y agoExponentially better than a polynomial in N is a polynomial in log N. See the abstract of [1] for the precise complexity claim about the algorithm mentioned in the article. As good as N^3 sounds, it's still not great on enormous systems. [1] https://arxiv.org/abs/0811.3171 https://arxiv.org/abs/0811.3171
- bradleyjg 9y agoIt's funny you put it that way. O(N^3) sounds horrific to me. Only practical for small problems and for anything else I'd need to look for approximations instead. O(2^N) meanwhile translates in my mind to completely impracticable. But I guess it all depends on what kind of Ns you are looking at.
- reacweb 9y agoI use perfect matching in go tournaments. I have tested it with 1000 players, it was less than 2 minutes -> perfectly acceptable.
- bradleyjg 9y agoOne thousand cubed is one billion. Of course it depends on what the Big-O notion is hiding, but one billion 'steps' is generally okay. But if you had tested it with ten thousand players it would go from one billion to one trillion -- which we'd expect to take more than a day on the same machine. That scaling is pretty brutal. Whereas something like sorting a list with O(N log N) would only have gone from about ten thousand to about one hundred fifty thousand. In order to hit one trillion steps we'd need to be sorting a list of nearly thirty billion items. I sometimes find myself working with ten thousand 'things', but very rarely with thirty billion.
- cozzyd 9y agoI thought technically you can do it in less than N^3 (with a huge constant factor). See e.g. https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...
- thomasahle 9y agoFrom the abstract if the algorithm they are implementing > We consider the case where one doesn't need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x, e.g., x'Mx for some matrix M. In this case, when A is sparse, N by N and has condition number kappa, classical algorithms can find x and estimate x'Mx in O(N sqrt(kappa)) time. Here, we exhibit a quantum algorithm for this task that runs in poly(log N, kappa) time, an exponential improvement over the best classical algorithm.