First ever head to head win in speed for a quantum computer

Update 5/9/2013:

Update 5/15/2013:

  • An update from the conference from Cathy: “Computing Frontiers 2013 Best Paper Award: Experimental Evaluation of an Adiabatic Quantum Computation System for Combinatorial Optimization, by McGeoch and Wang.” Congratulations to Cathy and Carrie!

AMHERST, Mass.A computer science professor at Amherst College who recently devised and conducted experiments to test the speed of a quantum computing system against conventional computing methods will soon be presenting a paper with her verdict: quantum computing is, “in some cases, really, really fast.”

“Ours is the first paper to my knowledge that compares the quantum approach to conventional methods using the same set of problems,” says Catherine McGeoch, the Beitzel Professor in Technology and Society (Computer Science) at Amherst. “I’m not claiming that this is the last word, but it’s a first word, a start in trying to sort out what it can do and can’t do.”

The quantum computer system she was testing, produced by D-Wave just outside Vancouver, BC, has a thumbnail-sized chip that is stored in a dilution refrigerator within a shielded cabinet at near absolute zero, or .02 degrees Kelvin in order to perform its calculations. Whereas conventional computing is binary, 1s and 0s get mashed up in quantum computing, and within that super-cooled (and non-observable) state of flux, a lightning-quick logic takes place, capable of solving problems thousands of times faster than conventional computing methods can, according to her findings.

Read the whole article here!

60 thoughts on “First ever head to head win in speed for a quantum computer

  1. Interesting stuff. Saw this on reddit though:

    An independent researcher (Matthias Troyer) who recently gave a talk at my school has also done benchmarking on the DWave system. He and his students wrote software that runs on a GPU and is optimized to do exactly what the DWave system can, rather than a more general problem like the commercial software compared against in the linked article. There, the GPU is quite a bit faster than the DWave system for all problem sizes, and they both scale the same as a function of the size of the problem. That is, there’s no reason to expect from these tests that larger future DWave chips will ever beat a well-optimized classical algorithm on these problems.

    Scott Aaronson said he’ll blog about this pretty soon. Definitely keeping my eye on that. (http://www.scottaaronson.com/blog/)

    Personally, I’m very optimistic about your approach. The fact that there appears to be quantum behavior occurring means you’re doing something interesting. (http://arxiv.org/pdf/1304.4595v1.pdf)

    Hopefully it’s not a coincidence that your system is also great at solving these narrow optimization problems.

  2. The term ‘Chimera structured input’ is heavily used throughout the original paper. Although the section 2.3 of the paper explains it enough it is new to me. Is it a pretty common term in graph theory or other field?

  3. I did a quick review of the paper and was trying to build a superficial mental picture of what gave the D-Wave machine advantage. Probably each item in the series of the Ising Hamiltonian had dedicated processing element (magnetic field acting upon individual qubits in parallel) for the case of the D-Wave machine. On the other hand, the computations on the classical computers had to compete for resources (I assume the number of processors was way smaller than the number of unit computational blocks probably generated by divide and conquer strategy). On top of that if there were recursive approaches it might also have contributed to the computing time through stack overhead and combining time for the solutions of sub-problems.

      • Umm not sure I understand your question?? The tests themselves were designed by the customers in the NASA / Google engagement. The testing procedure was designed by one of the leading experts in the world in this sort of thing (Cathy McGeoch — see http://www.cs.amherst.edu/ccm/).

      • If I oversimplify it (according to my naive understanding) the bench marking looks like bench marking of a single or dual core classical system (in this case the classical system) against a classical cluster (in this case the D-Wave system). So, the speed up may not be because of quantum mechanics. It may be because of the architecture. I am afraid we will not be able to see the comparative speed up for the same problems with same inputs if we replace the classical machines with, say, a 30,000 core cluster (like the one mentioned in http://ars.to/10Ca533).

      • I agree that the results are interesting. But the speed up looks to me to be a architectural one instead of being a quantum one.

      • In the case where you only give a solver a short timeout (say 50-100ms) having many cores doesn’t help at all! What you need is the most efficient algorithm running in a fast processor.

        As to where the speed-up comes from, Cathy’s paper isn’t about that, it’s about directly comparing different strategies for solving the same computational problems.

        I don’t think your intuition is correct — D-Wave hardware is nothing like a classical cluster in any dimension I could imagine. Also making a distinction between an ‘architectural’ speed-up and a ‘quantum’ speed-up doesn’t make much sense in our case. The two are intimately tied together. You can’t have one without the other in this sort of design.

      • @Geordie

        Is a 50-100 ms timeout a standard way to benchmark these systems? Sounds awfully short to me.

      • Well it depends on what you are trying to do. For the sparse coding application I’ve been describing in the blog, you need to solve one optimization problem per “data object” you are learning over per iteration of the algorithm. The number of data objects in a real data set is typically in the million+ range. This places limits on the time you have per optimization to be able to churn through your data set.

  4. Geordie:

    What sort of real world problems are Lockheed / Google / NASA solving using their DWave machines? Can you comment? Or is it classified.

    Are these problems ones that were practically insoluble using conventional computers? Or does QC make it much faster to solve them?

    • Hi Rahul! The Lockheed engagement is about complex system validation & verification (extending some old ideas in hardware verification into software and systems with both hardware and software). Google is interested in machine learning (see their blog post about this http://googleresearch.blogspot.ca/2013/05/launching-quantum-artificial.html). NASA is interested in planning and scheduling, searching for exoplanets, and supporting operations in mission control centers.

      There are applications available in all of these areas today, but there is a desire to make them much better. The general idea is to create new algorithms where what these types of processors do well is harnessed effectively, in order to try to make transformative leaps in capability in these areas.

      • @Geordie

        Thanks! Can you elaborate a bit more on the process of how D-Wave’s machine helps searching for exoplanets? Has it identified any exoplanets in historical test data-sets? Or any examples of what type of complex-systems has D-Wave’s machine successfully validated in your in-house testing?

        I understand roughly the overall promise of QC but have trouble fleshing out the specific applications.

      • I’ve been describing one potential ‘workhorse’ application (unsupervised feature learning using hierarchical sparse coding) in some recent blog posts. Being able to do this type of thing very quickly allows you to tackle any problem where these types of approaches might do well.

  5. When did Harmut instead of Aaronson become an expert on Quantum Computing? It is great that you guys are trying to do this but please make sure to be scientifically responsible or you will bring yourself a QC winter (we all know how that ends).

  6. @Geordie

    I was reading the Nature articles about DWaves recent breakthroughs and it does sound impressive. But one point confused me: I read two quotes:

    (1) “In short: the D-Wave quantum computer is thousands of times faster than other commercial computers at the very specific problem it was designed to solve. ”

    (2) “Daniel Lidar, ( director of the USC centre ) says that he has seen faster solvers. “Every problem we have tested can still be solved faster on classical computers,” he says.”

    How can (1) and (2) both be true. As a layman, I’m trying to understand the nuance in this.

    http://www.nature.com/news/google-and-nasa-snap-up-quantum-computer-1.12999

    http://blogs.nature.com/news/2013/05/quantum-computer-passes-speed-test.html

    • Hi Rahul!

      They are both true because they refer to tests on different machines. The benchmarking work in (1) was performed on a 439 qubit subgraph of a 512 qubit Vesuvius processor in a D-Wave Two system, while the work in (2) was performed on a 108 qubit subgraph of a 128 qubit Rainier processor in a D-Wave One. The systems are quite different (not just in qubit count). On a standard benchmark we run internally (1) runs about 400,000 times faster than (2). The technology is evolving very quickly.

      • Is there a document that describes how the architecture of Vesuvius differs from Rainier (other than the obvious qubit scaling)? Especially curious what you guys did that could get you a 400,000 fold speedup! Or would you have to kill me if you told me.🙂

      • There were two significant changes that were made to speed up the Vesuvius design: (a) the system we use to program the devices on the chip was changed from an SFQ-based digital circuit, which generated heat during programming, to an XYZ addressable input system, which was dissipation-free. This removed the biggest part of the duty cycle, which was simply waiting for the chip to cool down after programming it! This waiting time was completely dominating the duty cycle, and it was removed entirely. (b) the readout system was completely redesigned in order to dramatically speed it up. The new readout system is called NDRO (non dissipative readout).

        There were also several changes made in the actual computing fabric itself. For example the qubits’ energy scales were significantly increased, which increases the precision to which parameters can be specified.

        Basically there were many major changes that make Vesuvius quite a different beast than Rainier.

        It’s important to realize that D-Wave is really an engine for evolving processors. There is no such thing as “the D-Wave processor”. Each month there’s something new and better!

      • Rahul,

        The answer to your question below Re: Vesuvius vs. Rainier is actually pretty easy, and no extraordinary measures would be required!🙂

        Rainier used “traditional” Single Flux Quantum (SFQ) digital superconducting logic to program all control devices on chip. While SFQ is orders of magnitude more power-efficient than, say, CMOS, it proved to be still too “hungry” when operating at mK temperatures. As a result, after programming a Rainier chip with a given problem, we had to wait ~1 second (!) for chip temperature to drop to mKs.

        Vesuvius, on the other hand, utilizes much simple control logic approach, which allowed us to move most of power dissipation off-chip (actually, its control elements can, probably, be operated adiabatically, or, in any case, close to thermodynamic limit of power dissipation), and no extra thermalization time is required!

        Since programming itself takes only about 100us or so, here are roughly 4 orders of magnitude improvement in speed.

        The rest, of course, is due to 4x larger qubit count…🙂

        Hope this helps,

        Paul B.

        P. S. Geordie, I do not seem to be able to reply to Rahul’s question directly, feel free to move this where it belongs!

    • You may be right. However, you cannot deny the scientific irresponsibility on behalf of the annealing experiments. However, that reflects not on the company but the scientists conducting the experiment. As far as computing capabilities are concerned, I think you guys may be too early in pitching a product … let alone for machine learning. But don’t get me wrong — I do seriously do hope something comes out. But as far as AI/Machine Learning is concerned, the key problem — regardless of whether or not for machine learning (classical or quantum)– is in the dynamics of inference/stochastic search/optimization (depending on your favorite recipe) — which even for any substantially simpler problem than AI, is poorly understood. I realize the fact that you guys are using ising models — which inherently do not have structure, especially in frustrated cases. One fundamental question is whether it even makes sense — purely from the perspective of ML/AI — to focus on such structureless models (one virtue of being intelligent is to do inferences with sparse data which is possible with structured representations). Secondly, I have no reason to believe that DWave or anyone has figured out the dynamics to ensure (by giving certifications of algorithmic asymptotic guarantees … or even empirically) escape from local minimas even in simple Ising models (which according to me is a key question). And of course simply enumerating is not an option. I understand that these are follow up question but given the hype and DWave’s core pitch, these things have to be clearly understood and communicated.

      • I’m not sure I understand your comment. You refer to the ‘scientific irresponsibility on behalf of the annealing experiments’. Can you clarify what you’re referring to?

      • I am referring to McGeoch et al paper. I think comparing an exact solver like CPLEX is not fair. More importantly, it is reflects really badly on McGeoch when they purposefully don’t report performance number on an approximate solver like tabu and defer it to “future work” when such experiments were already conducted! To me this is scientific irresponsibility on their part (nothing on you guys).

      • Anon: Please, please read the paper! You will change your mind about what is going on here.

        The Vesuvius chip WAS compared with tabu, akmaxsat (an award winning sat solver) and cplex. While cplex can be used to prove global optimality, that’s not how it was used in the test. The times reported were the time for cplex to find a solution of a certain quality, not to prove it was optimal. Tabu and cplex were close in how well they performed. No results were ‘held back’.

        The results of the McGeoch study are absolutely beyond reproach. The tests were designed and carried out by people who are considered to be the top experts in the world in this type of test. But don’t take my word for it: read Michael Trick’s latest blog post: http://mat.tepper.cmu.edu/blog/?p=1786 and spread the good word!

    • But Geordie aren’t you using the McGeoch paper to say that there’s a significant speedup (on particular problem sets) with the D-Wave hardware?

  7. Anon, I don’t work at D-Wave! I have several really interesting questions (to me) for Geordie that I’m finishing typing up.

  8. Geordie, what do you think of Lidar’s thesis as per the update in Aaronson’s blog, http://www.scottaaronson.com/blog/?p=1400, that without error correction D-Wave will never exhibit speed-up over classical computing?

    Also, do you still agree that D-Wave’s 2048 qubit system will outperform all combined computing systems on the earth by several orders of magnitude, and that D-Wave’s 8192 qubit system will outperform the universe by many orders of magnitude, both as per Steve Jurvetson’s explanation on his Flickr photostream, http://www.flickr.com/photos/jurvetson/8054771535/in/photostream, regarding what he has called Rose’s Law and the points you have made to him regarding D-Wave’s systems’ performance scalability?

    I personally believe that both cases will hold to be true, and I also believe that you have spent many years thinking about it and testing it with the knowledge and systems required to be able to come up with some model for the scalability of D-Wave’s systems compared to classical computing as the number of D-Wave’s systems’ qubits goes up.

    McGeoch’s paper stated that for an increase of 63 qubits the system exhibited an increase in performance of 3 to 5 times for the algorithms she specifically set up. According to the NYT article, Williams stated that Google’s test problems were even harder and the speed-up over classical computing was even greater than the problems McGeoch set up.

    Therefore, for every one qubit increase, the system’s performance improves by a non-marginal exponent. For the harder computing problems, at 2048 qubits, the next D-Wave will be faster than a double-digit Yottaflop classical computer, and at 8192 qubits, the D-Wave system will be faster than perhaps as much as 1 billion universes’ mass and energy put together.

    • Hi Steven!

      Maybe it’s because of how much machine learning we do here, but the question of what direction to take the technology is always settled in the lab by experiment. We try not to inject our own biases about what may be necessary to do. Kind of like “unsupervised processor learning”🙂. If it turns out that the design starts failing because of some reason (which happens all the time) we try as many things as we can think of to overcome that failure. It’s absolutely possible that adding active error correction might help at some point, maybe even in the next generation. If that is the case, we’ll certainly try anything anyone can think of to make the processors work better! In the specific case of exhibiting scaling differences over conventional algorithms, I’d bet we don’t need error correction (at least at the current snapshot) but at the next level (say 2000+ qubits) maybe we might. If we do, no problem — we’ll find a way!

      Re your second question, it’s hard to say. All I can say is we always try our best to build the most kick-ass thing we can. So far it’s worked out pretty well!

  9. Hi Geordie,

    That’s great to know! The 2048 qubit and 8192 qubit systems will be especially important, they will be the ones that truly change the world, the ones that D-Wave has to absolutely get right.

    Be sure to talk to Daniel Lidar a lot. He seems to actually care about what he does.

    This was on Youtube’s D-Wave channel. There is a 98% chance that you have already seen it, but just in case, it’s the talk Daniel gave on error correction: https://www.youtube.com/watch?v=iZbW5bvcGig

  10. Do you see the cost of your gizmo coming down in the future? What sort of price point can you envision, say, once you had a little more economy of scale going? What’s the most expensive parts right now.

  11. Hi Geordie,

    I just noticed that Lidar has a new book on Quantum Error Correction coming on either this August or September that is published by Cambridge University Press.

    It is going to be an important book, along with the research that the USC-Lockheed Martin Quantum Computation Center is doing. The 2048 and 8192 qubit systems will probably need error correction. Hopefully you and the rest of the system designers at D-Wave are taking the possibility and trade-offs of error correction very seriously.

    Designing the 2048 and 8192 qubit systems correctly is critical.

    • [“Error suppression and error correction in adiabatic quantum computation:
      techniques and challenges”]
      http://arxiv.org/abs/1307.5893

      “We analyze the effectiveness of such error suppression techniques and identify critical constraints on the performance of error suppression in AQC, suggesting that error suppression by itself is insufficient for large-scale, faulttolerant AQC and that a form of error correction is needed”

    • Error corrected quantum annealing with hundreds of qubits
      Daniel A. Lidar

      http://arxiv.org/abs/1307.8190

      “Quantum information processing o ffers dramatic speedups, yet is famously susceptible to decoherence, the process whereby quantum superpositions decay into mutually exclusive classical alternatives, thus robbing quantum computers of their power. This has made the development of quantum error correction an essential and inescapable aspect of both theoretical and experimental quantum computing. So far little is known about protection against decoherence in the context of quantum annealing, a computational paradigm which aims to exploit ground state quantum dynamics to solve optimization problems more rapidly than is possible classically. Here we develop error correction for quantum annealing and provide an experimental demonstration using up to 344 superconducting flux qubits in processors which have recently been shown to physically implement programmable quantum annealing. We demonstrate a substantial improvement over the performance of the processors in the absence of error correction. These results pave a path toward large scale noise-protected adiabatic quantum optimization devices.”

  12. Geordie: There is an Arab saying, which goes something like this: ” The caravan continues to its destination, unheeded by the barking of the village dogs!”. So, continue with your great work. Thanks

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s