4 ms·

Quantum annealing could "potentially" provide a speedup for any optimization problem that can be reduced to a spin Ising form, particularly quadratic unconstrai

by efangs 11y ago

Quantum annealing could "potentially" provide a speedup for any optimization problem that can be reduced to a spin Ising form, particularly quadratic unconstrained binary optimization (QUBO). Notice the emphasis on potentially, though. This paper only shows that 1) for a particular class of problems the quantum annealer has constant speedup over one current classical algorithms, and 2) the quantum annealer scales better for number partitioning than a few current classical algorithms.

eveningcoffee 11y ago
for a particular class of problems the quantum annealer has constant speedup over one current classical algorithms on single core CPU. 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).
- ddp 11y ago
  10^8 is a lot.
  - eveningcoffee 11y ago
    If we compare single core CPU performance against heavily motivated special solution, then it is not (it does not follow that the same method can be applied in this case, but then again, a better classical algorithm on single core beats the reported quantum result according to the paper (PS. this is in the paper, not on the graph)). Here is comparison http://bitcoin.stackexchange.com/questions/36412/what-is-the-difference-in-speed-between-a-gpu-and-an-asic-per-dollar-of-cost 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_comparison 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 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.
- throwaway2048 11y ago
  they are more concerned with the fundamental computational complexity nature of the speedup (is it superlinear/exponential?) not the actual realworld hardware results. All throwing more hardware at a problem does is (at best) is a linear increase.
- efangs 11y ago
  People above are right about parallelization not being a useful benchmark. On the other hand, benchmarking against other special purpose hardware (like an FPGA, ASIC, RQL, etc.) is definitely of interest.
  - eveningcoffee 11y ago
    Why it is not? It would show how easily this problem is actually parallelizable in practice.
    - efangs 11y ago
      Because both D-wave and the classical algorithms will benefit linearly with parallelization. If they want to make a claim about the scaling ratio between D-wave and classical algorithms, then this linear term would cancel.
      - eveningcoffee 11y ago
        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.
        efangs 11y ago
        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.
        db48x 11y ago
        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.
- tagrun 11y ago
  It doesn't matter in this context. 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.
  - eveningcoffee 11y ago
    Parallelization would get you a factor 1/k (k being the number of cores) in favor of the classical algorithm at best. 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.
    - efangs 11y ago
      If you give classical k cores, then to be fair you should give quantum k D-waves. If you are only making a scaling argument, then no need to include terms that cancel. 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.
      - apsec112 11y ago
        That isn't a fair equivalence. A core costs about $100, while a D-Wave machine costs about $20 million.

by efangs 11y ago

eveningcoffee 11y ago

for a particular class of problems the quantum annealer has constant speedup over one current classical algorithms on single core CPU. 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).

ddp 11y ago
10^8 is a lot.
- eveningcoffee 11y ago
  If we compare single core CPU performance against heavily motivated special solution, then it is not (it does not follow that the same method can be applied in this case, but then again, a better classical algorithm on single core beats the reported quantum result according to the paper (PS. this is in the paper, not on the graph)). Here is comparison http://bitcoin.stackexchange.com/questions/36412/what-is-the-difference-in-speed-between-a-gpu-and-an-asic-per-dollar-of-cost 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_comparison 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 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.
throwaway2048 11y ago
they are more concerned with the fundamental computational complexity nature of the speedup (is it superlinear/exponential?) not the actual realworld hardware results. All throwing more hardware at a problem does is (at best) is a linear increase.
efangs 11y ago
People above are right about parallelization not being a useful benchmark. On the other hand, benchmarking against other special purpose hardware (like an FPGA, ASIC, RQL, etc.) is definitely of interest.
- eveningcoffee 11y ago
  Why it is not? It would show how easily this problem is actually parallelizable in practice.
  - efangs 11y ago
    Because both D-wave and the classical algorithms will benefit linearly with parallelization. If they want to make a claim about the scaling ratio between D-wave and classical algorithms, then this linear term would cancel.
    - eveningcoffee 11y ago
      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.
      - efangs 11y ago
        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.
      - db48x 11y ago
        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.
tagrun 11y ago
It doesn't matter in this context. 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.
- eveningcoffee 11y ago
  Parallelization would get you a factor 1/k (k being the number of cores) in favor of the classical algorithm at best. 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.
  - efangs 11y ago
    If you give classical k cores, then to be fair you should give quantum k D-waves. If you are only making a scaling argument, then no need to include terms that cancel. 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.
    - apsec112 11y ago
      That isn't a fair equivalence. A core costs about $100, while a D-Wave machine costs about $20 million.