13 ms·

Google, D-Wave, and the case of the factor-10^8 speedup

312 points by apsec112 11y ago

touchofevil 11y ago
I'm wondering if this will allow for a huge speed up in 3D rendering? Specifically, unbiased Monte Carlo ray-tracing / path-traching renderers like Maxwell Render. Does anyone know of any work being done in this area of Quantum computing?
- 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.
- jerf 11y ago
  "Does anyone know of any work being done in this area of Quantum computing?" Work in this area is still primarily focused on making it work at all. For instance, it isn't called out in the linked blog since by now Scott probably considers it basic background information, but D-Wave only solves a very particular problem, and it is both not entirely clear that it has a superior solution to that problem than a classical algorithm can obtain and it is not clear that encoding real problems into that problem will not end up costing you all of the gains itself. Really pragmatic applications are still a ways into the future. It's hard to imagine what they might be when we're still so early in the process, and still have no good idea what either the practical or theoretical limits are.
- lmm 11y ago
  The popular perception of quantum computers as "doing things in parallel" is very misleading. A quantum computer lets you perform computation on a superposed state while maintaining that superposition. But that only helps if the structure of the problem lets you somehow "cancel out" the incorrect results leaving you with the single correct one. You can't actually run a bunch of calculations in parallel and measure all of the results; it's more like you can, in some limited cases, make it as though you'd "magically" made the right choice to start with.
calhoun137 11y ago
I found this remark from the linked pdf[1] very interesting: "...it has also been shown that for the class of problems used in initial benchmarks,the performance of the devices also correlates well with a classical(meanfield) approximation of quantum annealing [4],which raises questions about whether the devices can outperform classical optimizers." In other words, if you ran a simulation of this device on a normal computer and gave it the same problem to solve, you will get basically the same efficiency. [1] http://www.scottaaronson.com/troyer.pdf http://www.scottaaronson.com/troyer.pdf
- SilasX 11y ago
  So ... more proof that D-Wave is fluff.
  - oh_sigh 11y ago
    Or proof that classical computers and algorithms have decades of optimizations behind them and quantum computers and algorithms only have years.
    - colanderman 11y ago
      They're measuring asymptotic performance (scale), not wall clock time, and testing quantum algorithms with known better asymptotic performance than the equivalent classical ones. They could run the classical algorithms a factor of 1,000,000× slower and reach the same conclusion, that the D-Wave's quantum annealing process is asymptotically equivalent (scales equivalently) to classical algorithms.
      - oh_sigh 11y ago
        I understand the difference between the two(yay, CS degree! and/or wikipedia), but from what I could read of the two posts, there is no indication that the asymptotic performance was being measured to any significant extent.
    - letstryagain 11y ago
arthurcolle 11y ago
TL;DR "Finally, on the special Chimera instances with the tall, thin energy barriers, the authors find that the D-Wave 2X reaches the global optimum about 108 times faster than Quantum Monte Carlo running on a single-core classical computer. But, extremely interestingly, they also find that this speedup does not grow with problem size; instead it simply saturates at ~108. In other words, this is a constant-factor speedup rather than an asymptotic one."
- selimthegrim 11y ago
  10^8, not 108!
  - randyrand 11y ago
    Just for clarification (for anyone), 10^8 or 100,000,000 is still a constant factor =)
    - selimthegrim 11y ago
      Well yes but Google spending some obscene amount of money for a 108x speedup is beyond farcical even if it's not asymptotic :)
      - DannyBee 11y ago
        Google isn't spending money for even a 10^8 speedup at this point, Google is spending money to figure out what will be possible in the future
coldcode 11y ago
Can someone explain this to those of use who have no clue what these calculations are good for? If this machine is faster to do something, what would you use that something for?
- deleted 11y ago
  [deleted]
- cjmoran 11y ago
  The YouTube channel "In a Nutshell" released a good summary on this recently: https://www.youtube.com/watch?v=JhHMJCUmq28 https://www.youtube.com/watch?v=JhHMJCUmq28
  - archgoon 11y ago
    That video is about Gate Quantum Computers; DWave machines are NOT gate quantum computers; they call their machine quantum annealing machines. It is not known the complexity class of problems that can be solved efficiently by quantum annealing machines, or if that class is equivalent to classical machines. The result shows that the DWave machine is asymptotically faster than the Simulated Annealing algorithm (yay!), which suggests that it is executing the Quantum Annealing algorithm. However, the the paper also explicitly states that this does not mean that the Dwave machine is exhibiting a 'quantum speedup'. To do this, they would need to show it to outperform the best known classical algorithm, which as the paper acknowledges, it does not. What the paper does seem to be showing is that the machine in question is actually fundamentally quantum in nature; it's just not clear yet that that the type of quantum computer it is is an improvement over classical ones.
- mcguire 11y ago
  "If this machine is faster to do something..." That's the point; is the machine faster? If the machine is actually doing quantum computing, it won't slow down as much for larger problems (for some problems). But they haven't been able to prove that it's doing quantum magic.
- deleted 11y ago
  [deleted]
biot 11y ago
The phrasing of "factor-10^8 speedup" threw me for a bit. Is that a negative speedup, meaning it's significantly slower? No, it's actually "10^8 faster".
- tzakrajs 11y ago
  (-10)^8 :P
- HappyTypist 11y ago
  They probably mean the - like "Factor-100 speedup".
adrianbg 11y ago
D-Wave's computers work as intended and exhibit "computationally relevant quantum effects" but we still don't know whether the strategy they are using will ever yield practical advantages. Other groups (Google, University of Maryland) seem likely to achieve genuine quantum speedups over best-known classical algorithms within the next few years.
- raverbashing 11y ago
  Yes But that's the evolution of technology. First cars were not a significant advantage over horses Sometimes it is much more efficient from the start (like transistors) but this is rare.
  - adrianbg 11y ago
    Not efficient at the start is a little different than "we have no reason to think it will ever be more efficient".
bhouston 11y ago
It isn't that clear but Scott Aaronson did make an admission in this article that I do not believe he has made before -- he admitted the D-Wave compute exhibited quantum effects: "As far as I’m concerned, this completely nails down the case for computationally-relevant collective quantum tunneling in the D-Wave machine" I believe many of his previous blog posts had argued strongly that there was no proof of any quantum effects in D-Wave computers, but I could be misremembering.
- dvanduzer 11y ago
  Scott Aaronson's entire professional life is essentially to distinguish what could and couldn't be a quantum effect in computation. So yes, your memory is accurate that his previous blog posts argue strongly that nothing D-Wave computers had done proved any quantum effects. His acknowledgement that they've achieved quantum computation is a compliment to their engineering prowess. But he is complimenting new engineering results.
- shoyer 11y ago
  It's been clear that the D-Wave machine is exhibiting quantum effects for several years now. See Aaronson's blog (http://www.scottaaronson.com/blog/?p=1400 http://www.scottaaronson.com/blog/?p=1400) and this Nature Communications paper (http://www.nature.com/ncomms/journal/v4/n5/abs/ncomms2920.html http://www.nature.com/ncomms/journal/v4/n5/abs/ncomms2920.ht...). On the other hand, it's still not clear that this results in computationally relevant speedups. In my mind, this is not much of a shift in the status quo.
- lmm 11y ago
  It's not an "admission" - there wasn't proof before (Aaronson never claimed that the effects weren't computationally relevant, only that they hadn't been proven to be) and now there is.
lovelearning 11y ago
Any book that gives an overview of quantum computing to a programmer? A sort of "thing explainer" for quantum computing?
- gohrt 11y ago
  http://www.amazon.com/Quantum-Computing-since-Democritus-ebook/dp/B00B4V6IZK http://www.amazon.com/Quantum-Computing-since-Democritus-ebo... also free online
  - chubot 11y ago
    I have this book and it's great, though it's not quantum computing "for a programmer" -- I don't think such a thing really exists. It was based on a series of quantum computing lectures he did for CS grad students. If you have a solid undergraduate education in computer science theory (computability, computational complexity, etc.) and probability, you can get pretty far through the book and take away useful things. But simply being a programmer doesn't mean you'll get very far. I got pretty far but got lost toward the end. He states a LOT of results and they become hard to remember without working through them more deeply. It's all theory -- there's absolutely nothing like "programming" in the book.
    - lovelearning 11y ago
      Thank you for that review. I should have phrased my question better, because I actually meant a book for CS grads that focuses on the computational side more than the physics theory. Programming was the wrong word.
    - tgb 11y ago
      I, too, loved the book but think it's not what the asker was looking for. In particular, it assumes a lot of knowledge about quantum computing (it doesn't cover, say, Shor's algorithm or quantum Fourier transforms). It's aim is to present information about complexity theory, not "Learn to Program Quantum Computers in 24 Days". There was a good course on Coursera some years back that I found quite enjoyable and was my first introduction to quantum computing. It serves as an OK intro to quantum mechanics, too, from the abstract point of view where we just assume we have qubits versus the physics point of view where we start by looking at atoms. Maybe the course is still available.
Fede_V 11y ago
Scott Aaronson is fucking awesome. Whenever there's a new paper claiming breakthroughs about quantum computing or P=NP, I go to his blog and wait for him to clearly explain it. He is the very rare case of a top notch scientist with a gift for explaining things well.
sytelus 11y ago
While Scott Aaronson is highly respected, I think we are rushing in to put down D-Wave guys. They seem very conservative in their claims. We should celebrate that we have come even this far that we are actually constructing these machines that were just research fantasies few decades ago and are at a point where we can even think about doing comparison with best we have built. I don't think anyone in their right mind thinks D-Wave or other QC will replace classical machines in next 5-10 years period. It's the progress that we need to be positive about and build on each other's work.
- Strilanc 11y ago
  > They seem very conservative in their claims. Hahaha! D-Wave's reputation is one of exaggeration and putting marketing before science. That's how Scott ended up as de-facto "chief D-Wave skeptic": he kept complaining about their exaggerations and the exaggerations of journalists covering them. (The paper being discussed now does actually seem conservative in its claims, but it's by a team at Google; not D-Wave.)

312 points by apsec112 11y ago

I'm wondering if this will allow for a huge speed up in 3D rendering? Specifically, unbiased Monte Carlo ray-tracing / path-traching renderers like Maxwell Render. Does anyone know of any work being done in this area of Quantum computing?

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.
jerf 11y ago
"Does anyone know of any work being done in this area of Quantum computing?" Work in this area is still primarily focused on making it work at all. For instance, it isn't called out in the linked blog since by now Scott probably considers it basic background information, but D-Wave only solves a very particular problem, and it is both not entirely clear that it has a superior solution to that problem than a classical algorithm can obtain and it is not clear that encoding real problems into that problem will not end up costing you all of the gains itself. Really pragmatic applications are still a ways into the future. It's hard to imagine what they might be when we're still so early in the process, and still have no good idea what either the practical or theoretical limits are.
lmm 11y ago
The popular perception of quantum computers as "doing things in parallel" is very misleading. A quantum computer lets you perform computation on a superposed state while maintaining that superposition. But that only helps if the structure of the problem lets you somehow "cancel out" the incorrect results leaving you with the single correct one. You can't actually run a bunch of calculations in parallel and measure all of the results; it's more like you can, in some limited cases, make it as though you'd "magically" made the right choice to start with.

calhoun137 11y ago

I found this remark from the linked pdf[1] very interesting: "...it has also been shown that for the class of problems used in initial benchmarks,the performance of the devices also correlates well with a classical(meanfield) approximation of quantum annealing [4],which raises questions about whether the devices can outperform classical optimizers." In other words, if you ran a simulation of this device on a normal computer and gave it the same problem to solve, you will get basically the same efficiency. [1] http://www.scottaaronson.com/troyer.pdf http://www.scottaaronson.com/troyer.pdf

SilasX 11y ago
So ... more proof that D-Wave is fluff.
- oh_sigh 11y ago
  Or proof that classical computers and algorithms have decades of optimizations behind them and quantum computers and algorithms only have years.
  - colanderman 11y ago
    They're measuring asymptotic performance (scale), not wall clock time, and testing quantum algorithms with known better asymptotic performance than the equivalent classical ones. They could run the classical algorithms a factor of 1,000,000× slower and reach the same conclusion, that the D-Wave's quantum annealing process is asymptotically equivalent (scales equivalently) to classical algorithms.
    - oh_sigh 11y ago
      I understand the difference between the two(yay, CS degree! and/or wikipedia), but from what I could read of the two posts, there is no indication that the asymptotic performance was being measured to any significant extent.
  - letstryagain 11y ago

arthurcolle 11y ago

TL;DR "Finally, on the special Chimera instances with the tall, thin energy barriers, the authors find that the D-Wave 2X reaches the global optimum about 108 times faster than Quantum Monte Carlo running on a single-core classical computer. But, extremely interestingly, they also find that this speedup does not grow with problem size; instead it simply saturates at ~108. In other words, this is a constant-factor speedup rather than an asymptotic one."

selimthegrim 11y ago
10^8, not 108!
- randyrand 11y ago
  Just for clarification (for anyone), 10^8 or 100,000,000 is still a constant factor =)
  - selimthegrim 11y ago
    Well yes but Google spending some obscene amount of money for a 108x speedup is beyond farcical even if it's not asymptotic :)
    - DannyBee 11y ago
      Google isn't spending money for even a 10^8 speedup at this point, Google is spending money to figure out what will be possible in the future

coldcode 11y ago

Can someone explain this to those of use who have no clue what these calculations are good for? If this machine is faster to do something, what would you use that something for?

deleted 11y ago
[deleted]
cjmoran 11y ago
The YouTube channel "In a Nutshell" released a good summary on this recently: https://www.youtube.com/watch?v=JhHMJCUmq28 https://www.youtube.com/watch?v=JhHMJCUmq28
- archgoon 11y ago
  That video is about Gate Quantum Computers; DWave machines are NOT gate quantum computers; they call their machine quantum annealing machines. It is not known the complexity class of problems that can be solved efficiently by quantum annealing machines, or if that class is equivalent to classical machines. The result shows that the DWave machine is asymptotically faster than the Simulated Annealing algorithm (yay!), which suggests that it is executing the Quantum Annealing algorithm. However, the the paper also explicitly states that this does not mean that the Dwave machine is exhibiting a 'quantum speedup'. To do this, they would need to show it to outperform the best known classical algorithm, which as the paper acknowledges, it does not. What the paper does seem to be showing is that the machine in question is actually fundamentally quantum in nature; it's just not clear yet that that the type of quantum computer it is is an improvement over classical ones.
mcguire 11y ago
"If this machine is faster to do something..." That's the point; is the machine faster? If the machine is actually doing quantum computing, it won't slow down as much for larger problems (for some problems). But they haven't been able to prove that it's doing quantum magic.
deleted 11y ago
[deleted]

biot 11y ago

The phrasing of "factor-10^8 speedup" threw me for a bit. Is that a negative speedup, meaning it's significantly slower? No, it's actually "10^8 faster".

tzakrajs 11y ago
(-10)^8 :P
HappyTypist 11y ago
They probably mean the - like "Factor-100 speedup".

adrianbg 11y ago

D-Wave's computers work as intended and exhibit "computationally relevant quantum effects" but we still don't know whether the strategy they are using will ever yield practical advantages. Other groups (Google, University of Maryland) seem likely to achieve genuine quantum speedups over best-known classical algorithms within the next few years.

raverbashing 11y ago
Yes But that's the evolution of technology. First cars were not a significant advantage over horses Sometimes it is much more efficient from the start (like transistors) but this is rare.
- adrianbg 11y ago
  Not efficient at the start is a little different than "we have no reason to think it will ever be more efficient".

bhouston 11y ago

It isn't that clear but Scott Aaronson did make an admission in this article that I do not believe he has made before -- he admitted the D-Wave compute exhibited quantum effects: "As far as I’m concerned, this completely nails down the case for computationally-relevant collective quantum tunneling in the D-Wave machine" I believe many of his previous blog posts had argued strongly that there was no proof of any quantum effects in D-Wave computers, but I could be misremembering.

dvanduzer 11y ago
Scott Aaronson's entire professional life is essentially to distinguish what could and couldn't be a quantum effect in computation. So yes, your memory is accurate that his previous blog posts argue strongly that nothing D-Wave computers had done proved any quantum effects. His acknowledgement that they've achieved quantum computation is a compliment to their engineering prowess. But he is complimenting new engineering results.
shoyer 11y ago
It's been clear that the D-Wave machine is exhibiting quantum effects for several years now. See Aaronson's blog (http://www.scottaaronson.com/blog/?p=1400 http://www.scottaaronson.com/blog/?p=1400) and this Nature Communications paper (http://www.nature.com/ncomms/journal/v4/n5/abs/ncomms2920.html http://www.nature.com/ncomms/journal/v4/n5/abs/ncomms2920.ht...). On the other hand, it's still not clear that this results in computationally relevant speedups. In my mind, this is not much of a shift in the status quo.
lmm 11y ago
It's not an "admission" - there wasn't proof before (Aaronson never claimed that the effects weren't computationally relevant, only that they hadn't been proven to be) and now there is.

lovelearning 11y ago

Any book that gives an overview of quantum computing to a programmer? A sort of "thing explainer" for quantum computing?

gohrt 11y ago
http://www.amazon.com/Quantum-Computing-since-Democritus-ebook/dp/B00B4V6IZK http://www.amazon.com/Quantum-Computing-since-Democritus-ebo... also free online
- chubot 11y ago
  I have this book and it's great, though it's not quantum computing "for a programmer" -- I don't think such a thing really exists. It was based on a series of quantum computing lectures he did for CS grad students. If you have a solid undergraduate education in computer science theory (computability, computational complexity, etc.) and probability, you can get pretty far through the book and take away useful things. But simply being a programmer doesn't mean you'll get very far. I got pretty far but got lost toward the end. He states a LOT of results and they become hard to remember without working through them more deeply. It's all theory -- there's absolutely nothing like "programming" in the book.
  - lovelearning 11y ago
    Thank you for that review. I should have phrased my question better, because I actually meant a book for CS grads that focuses on the computational side more than the physics theory. Programming was the wrong word.
  - tgb 11y ago
    I, too, loved the book but think it's not what the asker was looking for. In particular, it assumes a lot of knowledge about quantum computing (it doesn't cover, say, Shor's algorithm or quantum Fourier transforms). It's aim is to present information about complexity theory, not "Learn to Program Quantum Computers in 24 Days". There was a good course on Coursera some years back that I found quite enjoyable and was my first introduction to quantum computing. It serves as an OK intro to quantum mechanics, too, from the abstract point of view where we just assume we have qubits versus the physics point of view where we start by looking at atoms. Maybe the course is still available.

Fede_V 11y ago

Scott Aaronson is fucking awesome. Whenever there's a new paper claiming breakthroughs about quantum computing or P=NP, I go to his blog and wait for him to clearly explain it. He is the very rare case of a top notch scientist with a gift for explaining things well.

sytelus 11y ago

While Scott Aaronson is highly respected, I think we are rushing in to put down D-Wave guys. They seem very conservative in their claims. We should celebrate that we have come even this far that we are actually constructing these machines that were just research fantasies few decades ago and are at a point where we can even think about doing comparison with best we have built. I don't think anyone in their right mind thinks D-Wave or other QC will replace classical machines in next 5-10 years period. It's the progress that we need to be positive about and build on each other's work.

Strilanc 11y ago
> They seem very conservative in their claims. Hahaha! D-Wave's reputation is one of exaggeration and putting marketing before science. That's how Scott ended up as de-facto "chief D-Wave skeptic": he kept complaining about their exaggerations and the exaggerations of journalists covering them. (The paper being discussed now does actually seem conservative in its claims, but it's by a team at Google; not D-Wave.)