I think it would have been at least have been meaningful if they had compared these algorithms against known parallel solutions on both CPU and GPU (and perhaps on FPGA too, such we could see how it would potentially compare against specialized ASIC solution).
Their conclusion is that in big O notation, quantum annealing and best classical algorithms are the same.
Parallelization would get you a factor 1/k (k being the number of cores) in favor of the classical algorithm at best, which specialized hardware would give you a constant factor boost without affecting the big O characteristics.
The problem is not "which is faster given a fixed n". Quantum computers are interesting for certain problems when n becomes larger and larger.
The real issue is whether if there is an exponential difference between quantum annealing and classical algorithms or not, in big O notation. Remember, that is the reason why people are so interested in quantum computation. Not some constant speed up.
O(f(n)) vs O(log(f(n))) and O(f(n)/k) vs O(log(f(n))) are essentially the same in terms of their capabilities of solving NP problems.
Exactly. 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 these algorithms, but name of QMC would suggest that this is an embarrassingly parallelizable problem, so my interest might be just from my ignorance.
The real issue is whether if there is an exponential difference between quantum annealing and classical algorithms
Yes, I know and that was not the focus of my comment. Sorry.
If you want to make a comparison between currently available hardware, then the metric should be some combination of speed, power usage, space, cost, etc.
On the other hand, benchmarking against other special purpose hardware (like an FPGA, ASIC, RQL, etc.) is definitely of interest.
If they want to make a claim about the scaling ratio between D-wave and classical algorithms, then this linear term would cancel.
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.
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.
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.
Is a cluster of Dwaves faster than a cluster of CPUs? Maybe at the two problems Google looked at.
All throwing more hardware at a problem does is (at best) is a linear increase.
Here is comparison http://bitcoin.stackexchange.com/questions/36412/what-is-the... between GPU and ASIC bitcoin mining and here is https://en.bitcoin.it/wiki/Non-specialized_hardware_comparis... GPU and CPU comparison.
From this the difference between between GPU and ASIC solution is about 10^4.
Google tested against Intel(R) Xeon(R) CPU E5-1650 single core, so it would be roughly 10^2 slower than GPU.
So one could say that ASIC solution for bitcoin mining is about 10^6 times faster than single core CPU solution.
Million times difference is of course not 100 million times difference, but it is still a lot and then again, alternative classical algorithms would beat current result: Based on the results presented here, one cannot claim a quantum speedup for D-Wave 2X, as this would require that the quantum processor in question outperforms the best known classical algorithm. ... This is because a va- riety of heuristic classical algorithms can solve most in- stances of Chimera structured problems much faster than SA, QMC, and the D-Wave 2X (from http://arxiv.org/abs/1512.02206).
I think that this is an important and an interesting result, but it is in my opinion not that impressive that it may appear to look.