7 ms·

People above are right about parallelization not being a useful benchmark. On the other hand, benchmarking against other special purpose hardware (like an FPGA

by 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.
      - eveningcoffee 11y ago
        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-nasa-our-quantum-computer-is-100-million-times-faster-than-normal-pc/ 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.
  - skew 11y ago
    Why do you think D-wave machines can be clustered at all? Unless you say it's operation is not essentially quantum, that would mean demonstrating coherence between a bunch of machines and a scalable quantum network!
deleted 11y ago
[deleted]

by efangs 11y ago

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.
    - eveningcoffee 11y ago
      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-nasa-our-quantum-computer-is-100-million-times-faster-than-normal-pc/ 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.
- skew 11y ago
  Why do you think D-wave machines can be clustered at all? Unless you say it's operation is not essentially quantum, that would mean demonstrating coherence between a bunch of machines and a scalable quantum network!

deleted 11y ago

[deleted]