Hacker News Reader

Comment by eveningcoffee | Hacker News Reader

The question is what would be the actual real life speedup. If it is not easily parallelizable then it becomes much more interesting finding.

I am not familiar with the algorithms used, but name of QMC would suggest that this is an embarrassingly parallelizable problem, so my interest might be just from my ignorance i.e. I am looking for assurance that my assumption actually holds.

But if a quantum computer is demonstrated to have a huge constant speedup against a problem that could not be easily parallelized (i.e. not this case I assume) then cluster of classical computers could not catch up the difference.

View on HN

The amount of time taken to solve a given problem in "real life" is irrelevant.

This is for problems where a brute-force solution on a classical machine needs O(2^n) computational steps. This is an exponential relationship; as the problem size (measured by n) becomes large, the number of steps required becomes vast. If each step takes a nanosecond, and n=30, then finding a solution will only take about a second. Double the problem size to n=60, however, and now it will take 36 years.

A quantum algorithm for the same problem might be able to run in subexponential time. It might still be something horrible like O(n^7) and it would still scale better than O(2^n): at n=30 it would take 22 seconds, but at n=60 it would only take about 45 minutes.

This is why computer scientists use Big-O notation; the clock speed of the computer is irrelevant if the algorithm scales badly. You never use bubble sort because it scales badly; almost anything else you can come up with will be better. Likewise, if you had a real quantum computer that could run Grover's algorithm then you'd never factor numbers using any other method; Grover's algorithm would always win.

The amount of time taken to solve a given problem in "real life" is irrelevant.

I thank you for your thorough answer.

I am not discussing the importance of the quantum speedup (that was not demonstrated) rather than the constant speedup compared to the single core CPU (and we know that in real life this difference does not even exist, but we can pretend that it does, ok?).

Google "google 100 million times faster than" and you can see already headlines poping up (for example this from Arstechica http://arstechnica.com/information-technology/2015/12/google... They even do not mention that actually the same problem can be solved on the single core CPU faster than on D-WAVE by using a different algorithm).

So I am dealing with a hypothetical situation where in fact some sort of quantum annealing computer could have a huge constant speedup compared to the single core CPU in solving of one very important problem.

Imagine that we live in a national state that does not have access to the quantum annealing technology (within reasonable time frame) but has state of the art silicon fab lab.

Could we build a classical cluster of the same speed? How many CPU cores we would need? What if we use GPUs? What if we build a problem specific chip (ASIC)?

What if there is no easily parallelizable solution? Could we then even find a match in problem solving speed?

I hope that it was clear that even without an asymptotic speedup there are specific cases where a huge constant speedup would matter.

There's no way to answer that question without going into the details of every specific problem you might want to solve, but since they've only demonstrated a constant speedup then yes, you can always build a normal computer which has comparable speed. Or you can improve your software; that's happened often enough already.

A single Dwave is not faster than a cluster of CPUs.

Is a cluster of Dwaves faster than a cluster of CPUs? Maybe at the two problems Google looked at.

Reply on news.ycombinator.com