{"id":1400,"date":"2013-05-16T12:41:17","date_gmt":"2013-05-16T17:41:17","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=1400"},"modified":"2016-12-10T04:21:25","modified_gmt":"2016-12-10T09:21:25","slug":"d-wave-truth-finally-starts-to-emerge","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=1400","title":{"rendered":"D-Wave: Truth finally starts to emerge"},"content":{"rendered":"<p><span style=\"color: #ff0000;\"><strong>Wrap-Up (June 5):<\/strong><\/span> This will be my final update on this post (really!!), since the discussion seems to have reached a point where not much progress is being made, and since I&#8217;d like to oblige the commenters who&#8217;ve asked me to change the subject.\u00a0 Let me try to summarize the <strong>main point<\/strong> I&#8217;ve been trying to get across this whole time.\u00a0 I&#8217;ll call the point (*).<\/p>\n<p style=\"padding-left: 30px;\">(*) D-Wave founder Geordie Rose claims that D-Wave has now accomplished its goal of building a quantum computer that, in his words, is &#8220;better at something than any other option available.&#8221;\u00a0 This claim has been widely and uncritically repeated in the press, so that much of the nerd world now accepts it as fact.\u00a0 However, the claim is not supported by the evidence currently available.\u00a0 It appears that, while the D-Wave machine does outperform certain off-the-shelf solvers, simulated annealing codes have been written that outperform the D-Wave machine on its own native problem when run on a standard laptop.\u00a0 More research is needed to clarify the issue, but in the meantime, it seems worth knowing that this is where things currently stand.<\/p>\n<p>In the comments, many people tried repeatedly to change the subject from (*) to various subsidiary questions.\u00a0 For example: isn&#8217;t it possible that D-Wave&#8217;s current device will be found to provide a speedup on some <em>other<\/em> distribution of instances, besides the one that was tested?\u00a0 Even if not, isn&#8217;t it possible that D-Wave will achieve a genuine speedup with some <em>future<\/em> generation of machines?\u00a0 Did it make business sense for Google to buy a D-Wave machine?\u00a0 What were Google&#8217;s likely reasons?\u00a0 What&#8217;s D-Wave&#8217;s current value as a company?\u00a0 Should Cathy McGeoch have acted differently, in the type of comparison she agreed to do, or in how she communicated about its results?\u00a0 Should <em>I<\/em> have acted differently, in my interaction with McGeoch?<\/p>\n<p>And, I&#8217;m afraid to say, I jumped in to the discussion of all of those questions&#8212;because, let&#8217;s face it, there are very few subjects about which I don&#8217;t have an opinion, or at least a list of qualified observations to make.\u00a0 In retrospect, I now think that was a mistake.\u00a0 It would have been better to sidestep all the other questions&#8212;not one of which I <em>really<\/em> know the answer to, and each of which admits multiple valid perspectives&#8212;and just focus relentlessly on the truth of assertion (*).<\/p>\n<p>Here&#8217;s an analogy: imagine that a biotech startup claimed that, by using an expensive and controversial new gene therapy, it could cure patients at a higher rate than with the best available conventional drugs&#8212;basing its claim on a single clinical trial.\u00a0 Imagine that this claim was widely repeated in the press as an established fact.\u00a0 Now imagine that closer examination of the clinical trial revealed that it showed nothing of the kind: it compared against the wrong drugs.\u00a0 And imagine that a more relevant clinical trial&#8212;mostly unmentioned in the press&#8212;had <em>also<\/em> been done, and discovered that when you compare to the right drugs, the drugs do better.\u00a0 Imagine that someone wrote a blog post bringing all of this to public attention.<\/p>\n<p>And now imagine that the response to that blogger was the following: &#8220;aha, but isn&#8217;t it possible that some <em>future<\/em> clinical trial will show an advantage for the gene therapy&#8212;maybe with some other group of patients?\u00a0 Even if not, isn&#8217;t it possible that the startup will manage to develop an effective gene therapy sometime in the future?\u00a0 Betcha didn&#8217;t consider that, did you?\u00a0 And anyway, at least they&#8217;re out there <em>trying<\/em> to make gene therapy work!\u00a0 So we should all support them, rather than relentlessly criticizing.\u00a0 And as for the startup&#8217;s misleading claims to the public?\u00a0 Oh, don&#8217;t be so na\u00efve: that&#8217;s just PR.\u00a0 If you can&#8217;t tune out the PR and concentrate on the science, that&#8217;s your own damn problem.\u00a0 In summary, the real issue isn&#8217;t what some clinical trial did or didn&#8217;t show; it&#8217;s <em>you<\/em> and your hostile attitude.&#8221;<\/p>\n<p>In a different context, these sorts of responses would be considered strange, and the need to resort to them revealing.\u00a0 But the rules for D-Wave are different.<\/p>\n<p>(Interestingly, in excusing D-Wave&#8217;s statements, some commenters explicitly defended standards of intellectual discourse so relaxed that, as far as I could tell, <em>just about anything anyone could possibly say<\/em> would be OK with them&#8212;except of course for what <em>I<\/em> say on this blog, which is not OK!\u00a0 It reminds me of the central tenet of cultural relativism: that there exist no universal standards by which any culture could ever be judged &#8220;good&#8221; or &#8220;bad,&#8221; except that Western culture is irredeemably evil.)<\/p>\n<p><span style=\"color: #ff0000;\"><strong>Update (June 4):<\/strong><\/span> Matthias Troyer (who, unfortunately, still can&#8217;t comment here for embargo reasons) has asked me to clarify that it&#8217;s not he, but rather his postdoc Sergei Isakov, who deserves the credit for actually writing the simulated annealing code that outperformed the D-Wave machine on the latter&#8217;s own &#8220;home turf&#8221; (i.e., random QUBO instances with the D-Wave constraint graph).\u00a0 The quantum Monte Carlo code, which <em>also<\/em> did quite well at simulating the D-Wave machine, was written by Isakov together with another of Matthias&#8217;s postdocs, Troels R\u00f8nnow.<\/p>\n<p><span style=\"color: #ff0000;\"><strong>Update (June 3):<\/strong><\/span> See Cathy McGeoch&#8217;s response (<a href=\"https:\/\/scottaaronson.blog\/?p=1400#comment-78963\">here<\/a> and <a href=\"https:\/\/scottaaronson.blog\/?p=1400#comment-78972\">here<\/a>), and <a href=\"https:\/\/scottaaronson.blog\/?p=1400#comment-78989\">my response to her response<\/a>.<\/p>\n<p><span style=\"color: #ff0000;\"><strong>Yet More Updates (June 2):<\/strong><\/span> Alex Selby has a <a href=\"http:\/\/www.archduke.org\/stuff\/d-wave-comment-on-comparison-with-classical-computers\/\">detailed new post<\/a> summarizing his comparisons between the D-Wave device (as reported by McGeoch and Wang) and his own solver&#8212;finding that his solver can handily outperform the device and speculating about the reasons why.<\/p>\n<p>In other news, Catherine McGeoch spoke on Friday in the MIT quantum group meeting.\u00a0 Incredibly, she spoke for more than an hour, without once mentioning the USC results that found that simulated annealing on a standard laptop (when competently implemented) handily outperformed the D-Wave machine, or making any attempt to reconcile those results with hers and Wang&#8217;s.\u00a0 Instead, McGeogh used the time to enlighten the assembled experts about what quantum annealing was, what an exact solver was, etc. etc., then repeated the speedup claims as if the more informative comparisons simply didn&#8217;t exist.\u00a0 I left without asking questions, not wanting to be the one to instigate an unpleasant confrontation, and&#8212;I&#8217;ll admit&#8212;questioning my own sanity as a result of no one else asking about the gigantic elephant in the room.<\/p>\n<p><span style=\"color: #ff0000;\"><strong>More Updates (May 21):<\/strong><\/span> Happy 2<sup>5<\/sup>th birthday to me!\u00a0 Among the many interesting comments below, see especially <a href=\"https:\/\/scottaaronson.blog\/?p=1400#comment-76372\">this one by Alex Selby<\/a>, who says he&#8217;s written his own specialist solver for one class of the McGeoch and Wang benchmarks that significantly outperforms the software (and D-Wave machine) tested by McGeoch and Wang on those benchmarks&#8212;and who provides the Python code so you can try it yourself.<\/p>\n<p>Also, Igor Vernik asked me to announce that on July 8th, D-Wave will be giving a technical presentation at the International Superconducting Electronics Conference in Cambridge.\u00a0 <a href=\"http:\/\/www.isec-2013.org\">See here<\/a> for more info; I&#8217;ll be traveling then and won&#8217;t be able to make it.\u00a0 I don&#8217;t know whether the performance comparisons to Matthias Troyer&#8217;s and Alex Selby&#8217;s code will be among the topics discussed, or if there will be an opportunity to ask questions about such things.<\/p>\n<p>In another exciting update, <a href=\"http:\/\/arxiv.org\/abs\/1305.4904\">John Smolin and Graeme Smith posted a paper to the arXiv tonight<\/a> questioning even the &#8220;signature of quantumness&#8221; part of the latest D-Wave claims&#8212;the part that I&#8217;d been ~98% willing to accept, even as I relayed evidence that cast enormous doubt on the &#8220;speedup&#8221; part. Specifically, Smolin and Smith propose a classical model that they say can explain the &#8220;bimodal&#8221; pattern of success probabilities observed by the USC group as well as quantum annealing can. I haven&#8217;t yet had time to read their paper or form an opinion about it, but I&#8217;d be very interested if others wanted to weigh in.\u00a0\u00a0 <span style=\"color: #ff0000;\"><strong>Update (May 26):<\/strong><\/span> The USC group has <a href=\"http:\/\/arxiv.org\/abs\/1305.5837\">put out a new preprint<\/a> responding to Smolin and Smith, offering additional evidence for quantum behavior in the D-Wave device that they say can&#8217;t be explained using Smolin and Smith&#8217;s model.<\/p>\n<p><strong><span style=\"color: #ff0000;\">Update (May 17):<\/span><\/strong> Daniel Lidar emailed me to clarify his views about error-correction and the viability of D-Wave&#8217;s approach.\u00a0 He invited me to share his clarification with others&#8212;something that I&#8217;m delighted to do, since I agree with him wholeheartedly.\u00a0 Without further ado, here&#8217;s what Lidar says:<\/p>\n<p style=\"padding-left: 30px;\">I don&#8217;t believe D-Wave&#8217;s approach is scalable without error correction.\u00a0 I believe that the incorporation of error correction is a necessary condition in order to ever achieve a speedup with D-Wave&#8217;s machines, and I don&#8217;t believe D-Wave&#8217;s machines are any different from other types of quantum information processing in this regard.\u00a0 I have repeatedly made this point to D-Wave over several years, and I hope that in the future their designs will allow more flexibility in the incorporation of error correction.<\/p>\n<p>Lidar also clarified that he not only doesn&#8217;t dispute what Matthias Troyer told me about the lack of speedup of the D-Wave device compared to classical simulated annealing in their experiments, but &#8220;fully agrees, endorses, and approves&#8221; of it&#8212;and indeed, that he himself was part of the team that did the comparison.<\/p>\n<p>In other news,\u00a0<a href=\"https:\/\/news.ycombinator.com\/item?id=5720258\">this Hacker News thread<\/a>, which features clear, comprehending discussions of this blog post and the backstory that led up to it, has helped to restore my faith in humanity.<\/p>\n<hr \/>\n<p>Two years ago almost to the day, I <a href=\"https:\/\/scottaaronson.blog\/?p=639\">announced my retirement as Chief D-Wave Skeptic<\/a>.\u00a0 But&#8212;as many readers predicted at the time&#8212;recent events (and the contents of my inbox!) have given me no choice except to resume my post.\u00a0 In an all-too-familiar pattern, <a href=\"http:\/\/bits.blogs.nytimes.com\/2013\/05\/08\/a-quantum-computer-aces-its-test\/\">multiple<\/a> <a href=\"http:\/\/nextbigfuture.com\/2013\/05\/details-on-quantum-computer-speed.html\">rounds of<\/a> <a href=\"http:\/\/spectrum.ieee.org\/tech-talk\/computing\/hardware\/dwave-quantum-computer-shows-promise-in-tests\">D-Wave-related<\/a> <a href=\"http:\/\/www.theregister.co.uk\/2013\/05\/15\/d_wave_quantum_computer_test\/\">hype<\/a> <a href=\"http:\/\/bits.blogs.nytimes.com\/2013\/05\/16\/google-buys-a-quantum-computer\/\">have<\/a> <a href=\"http:\/\/www.engadget.com\/2013\/05\/16\/google-nasa-quantum-computing\/?utm_medium=feed&amp;utm_source=Feed_Classic&amp;utm_campaign=Engadget\">made<\/a> it all over the world before the truth has had time to put its pants on and drop its daughter off in daycare.\u00a0 And the current hype is <em>particularly<\/em> a shame, because once one slices through all the layers of ugh&#8212;the rigged comparisons, the &#8220;dramatic announcements&#8221; that mean nothing, the lazy journalists cherry-picking what they want to hear and ignoring the inconvenient bits&#8212;there <em>really has<\/em> been a huge scientific advance this past month in characterizing the D-Wave devices.\u00a0 I&#8217;m speaking about the experiments on the D-Wave One installed at USC, the main results of which <a href=\"http:\/\/arxiv.org\/abs\/1304.4595\">finally appeared<\/a> in April.\u00a0 Two of the coauthors of this new work&#8212;Matthias Troyer and Daniel Lidar&#8212;were at MIT recently to speak about their results, Troyer last week and Lidar this Tuesday.\u00a0 Intriguingly, despite being coauthors on the same paper, Troyer and Lidar have very different interpretations of what their results mean, but we&#8217;ll get to that later.\u00a0 For now, let me summarize what I think their work has established.<\/p>\n<p><strong>Evidence for Quantum Annealing Behavior<\/strong><\/p>\n<p>For the first time, we have evidence that the D-Wave One is doing what should be described as &#8220;quantum annealing&#8221; rather than &#8220;classical annealing&#8221; on more than 100 qubits.\u00a0 (Note that D-Wave itself now speaks about &#8220;quantum annealing&#8221; rather than &#8220;quantum adiabatic optimization.&#8221;\u00a0 The difference between the two is that the adiabatic algorithm runs coherently, at zero temperature, while quantum annealing is a &#8220;messier&#8221; version in which the qubits are strongly coupled to their environment throughout, but still maintain <em>some<\/em> quantum coherence.)\u00a0 The evidence for quantum annealing behavior is still extremely indirect, but despite my &#8220;Chief Skeptic&#8221; role, I&#8217;m ready to accept what the evidence indicates with essentially no hesitation.<\/p>\n<p>So what <em>is<\/em> the evidence?\u00a0 Basically, the USC group ran the D-Wave One on a large number of randomly generated instances of what I&#8217;ll call the <strong>&#8220;D-Wave problem&#8221;<\/strong>: namely, the problem of finding the lowest-energy configuration of an Ising spin glass, with nearest-neighbor interactions that correspond to the D-Wave chip&#8217;s particular topology.\u00a0 Of course, restricting attention to this &#8220;D-Wave problem&#8221; tilts the tables heavily in D-Wave&#8217;s favor, but no matter: scientifically, it makes a lot more sense than trying to encode Sudoku puzzles or something like that.\u00a0 Anyway, the group then looked at the <em>distribution of success probabilities<\/em> when each instance was repeatedly fed to the D-Wave machine.\u00a0 For example, would the randomly-generated instances fall into one giant clump, with a few outlying instances that were especially easy or especially hard for the machine?\u00a0 Surprisingly, they found that the answer was no: the pattern was strongly <em>bimodal<\/em>, with most instances either extremely easy or extremely hard, and few instances in between.\u00a0 Next, the group fed the same instances to Quantum Monte Carlo: a standard classical algorithm that uses Wick rotation to find the ground states of &#8220;stoquastic Hamiltonians,&#8221; the particular type of quantum evolution that the D-Wave machine is claimed to implement.\u00a0 When they did that, they found exactly the same bimodal pattern that they found with the D-Wave machine.\u00a0 Finally they fed the instances to a classical simulated annealing program&#8212;but <em>there<\/em> they found a &#8220;unimodal&#8221; distribution, not a bimodal one.\u00a0 So, their conclusion is that whatever the D-Wave machine is doing, it&#8217;s more similar to Quantum Monte Carlo than it is to classical simulated annealing.<\/p>\n<p>Curiously, we don&#8217;t yet have any hint of a theoretical explanation for <em>why <\/em>Quantum Monte Carlo should give rise to a bimodal distribution, while classical simulating annealing should give rise to a unimodal one.\u00a0 The USC group simply observed the pattern empirically (as far as I know, they&#8217;re the first to do so), then took advantage of it to characterize the D-Wave machine.\u00a0 I regard explaining this pattern as an outstanding open problem raised by their work.<\/p>\n<p>In any case, <em>if<\/em> we accept that the D-Wave One is doing &#8220;quantum annealing,&#8221; then despite the absence of a Bell-inequality violation or other direct evidence, it&#8217;s reasonably safe to infer that there <em>should<\/em> be large-scale entanglement in the device.\u00a0 I.e., the true quantum state is no doubt extremely mixed, but there&#8217;s no particular reason to believe we could decompose that state into a mixture of product states.\u00a0 For years, I tirelessly repeated that D-Wave hadn&#8217;t even provided evidence that its qubits were entangled&#8212;and that, while you can have entanglement with no quantum speedup, you can&#8217;t <em>possibly<\/em> have a quantum speedup without at least the capacity to generate entanglement.\u00a0 Now, I&#8217;d say, D-Wave finally <em>has<\/em> cleared the evidence-for-entanglement bar&#8212;and, while they&#8217;re not the first to do so with superconducting qubits, they&#8217;re certainly the first to do so with <em>so many<\/em> superconducting qubits.\u00a0 So I congratulate D-Wave on this accomplishment.\u00a0 If this had been advertised from the start as a scientific research project&#8212;&#8220;<em>of course<\/em> we&#8217;re a long way from QC being practical; no one would ever claim otherwise; but as a first step, we&#8217;ve shown experimentally that we can entangle 100 superconducting qubits with controllable couplings&#8221;&#8212;my reaction would&#8217;ve been, &#8220;cool!&#8221;\u00a0 (Similar to my reaction to any number of <em>other<\/em> steps toward scalable QC being reported by research groups all over the world.)<\/p>\n<p><strong>No Speedup Compared to Classical Simulated Annealing<\/strong><\/p>\n<p>But of course, D-Wave&#8217;s claims&#8212;and the claims being made on its behalf by the Hype-Industrial Complex&#8212;are far more aggressive than that.\u00a0 And so we come to the part of this post that has <em>not<\/em> been pre-approved by the International D-Wave Hype Repeaters Association.\u00a0 Namely, the same USC paper that reported the quantum annealing behavior of the D-Wave One, also <span style=\"color: #ff0000;\"><strong>showed no speed advantage whatsoever for quantum annealing over classical simulated annealing.<\/strong><\/span>\u00a0 In more detail, Matthias Troyer&#8217;s group spent a few months carefully studying the D-Wave problem&#8212;after which, they were able to write optimized simulated annealing code that <em>solves the D-Wave problem on a normal, off-the-shelf classical computer, about 15 times faster than the D-Wave machine <strong>itself<\/strong> solves the D-Wave problem!<\/em>\u00a0 Of course, if you wanted even more classical speedup than that, then you could simply add more processors to your classical computer, for only a tiny fraction of the ~$10 million that a D-Wave One would set you back.<\/p>\n<p>Some people might claim it&#8217;s &#8220;unfair&#8221; to optimize the classical simulated annealing code to take advantage of the quirks of the D-Wave problem.\u00a0 But think about it this way: D-Wave has spent ~$100 million, and hundreds of person-years, optimizing the hell out of a special-purpose annealing device, with the sole aim of solving this one problem that D-Wave itself defined.\u00a0 So if we&#8217;re serious about comparing the results to a classical computer, isn&#8217;t it reasonable to have one professor and a few postdocs spend a <em>few months<\/em> optimizing the classical code as well?<\/p>\n<p>As I said, besides simulated annealing, the USC group also compared the D-Wave One&#8217;s performance against a classical implementation of Quantum Monte Carlo.\u00a0 And maybe not surprisingly, the D-Wave machine <em>was<\/em> faster than a &#8220;direct classical simulation of itself&#8221; (I can&#8217;t remember how many times faster, and couldn&#8217;t find that information in the paper).\u00a0 But even here, there&#8217;s a delicious irony.\u00a0 The only reason the USC group was able to compare the D-Wave one against QMC at all, is that <em>QMC is efficiently implementable on a classical computer!<\/em>\u00a0 (Albeit probably with a large constant overhead compared to running the D-Wave annealer itself&#8212;hence the superior performance of classical simulated annealing over QMC.)\u00a0 This means that, <em>if<\/em> the D-Wave machine can be understood as reaching essentially the same results as QMC (technically, &#8220;QMC with no sign problem&#8221;), then there&#8217;s no real hope for using the D-Wave machine to get an asymptotic speedup over a classical computer.\u00a0 The race between the D-Wave machine and classical simulations of the machine would then <em>necessarily<\/em> be a cat-and-mouse game, a battle of constant factors with no clear asymptotic victor.\u00a0 (Some people might conjecture that it will also be a &#8220;Tom &amp; Jerry game,&#8221; the kind where the classical mouse always gets the better of the quantum cat.)<\/p>\n<p>At this point, it&#8217;s important to give a hearing to three possible counterarguments to what I&#8217;ve written above.<\/p>\n<p>The first counterargument is that, if you plot both the runtime of simulated annealing and the runtime of the D-Wave machine as functions of the instance size n, you find that, while simulated annealing is faster in absolute terms, it can <em>look like<\/em> the curve for the D-Wave machine is less steep.\u00a0 Over on the blog &#8220;nextbigfuture&#8221;, an apparent trend of this kind has been <a href=\"http:\/\/nextbigfuture.com\/2013\/01\/dwave-systems-512-qubits-projected-to.html\">fearlessly extrapolated<\/a> to predict that with 512 qubits, the D-Wave machine will be 10 billion times faster than a classical computer.\u00a0 But there&#8217;s a tiny fly in the ointment.\u00a0 As Troyer carefully explained to me last week, the &#8220;slow growth rate&#8221; of the D-Wave machine&#8217;s runtime is, ironically, basically an artifact of the machine being run too slowly on small values of n.\u00a0 Run the D-Wave machine as fast as it <em>can<\/em> run for small n, and the difference in the slopes disappears, with only the constant-factor advantage for simulated annealing remaining.\u00a0 In short, there seems to be no evidence, at present, that the D-Wave machine is going to overtake simulated annealing for <em>any<\/em> instance size.<\/p>\n<p>The second counterargument is that the correlation between the two &#8220;bimodal distributions&#8221;&#8212;that for the D-Wave machine and that for the Quantum Monte Carlo simulation&#8212;is not perfect.\u00a0 In other words, there are a few instances (not many) that QMC solves faster than the D-Wave machine, and likewise a few instances that the D-Wave machine solves faster than QMC.\u00a0 Not surprisingly, the latter fact has been eagerly seized on by the D-Wave boosters (&#8220;hey, <em>sometimes<\/em> the machine does better!&#8221;).\u00a0 But Troyer has a simple and hilarious response to that.\u00a0 Namely, he found that <em>his group&#8217;s QMC code did a better job of correlating with the D-Wave machine, than the D-Wave machine did of correlating with itself!<\/em>\u00a0 In other words, calibration errors seem <em>entirely<\/em> sufficient to explain the variation in performance, with no need to posit any special class of instances (however small) on which the D-Wave machine dramatically outperforms QMC.<\/p>\n<p>The third counterargument is just the banal one: the USC experiment was only one experiment with one set of instances (albeit, a set one might have thought would be heavily biased <em>toward<\/em> D-Wave).\u00a0 There&#8217;s no proof that, in the future, it won&#8217;t be discovered that the D-Wave machine does something more than QMC, and that there&#8217;s some (perhaps specially-designed) set of instances on which the D-Wave machine asymptotically outperforms both QMC and Troyer&#8217;s simulated annealing code.\u00a0 (Indeed, I gather that folks at D-Wave are now assiduously looking for such instances.)\u00a0 Well, I concede that almost anything is possible in the future&#8212;but &#8220;these experiments, while <em>not<\/em> supporting D-Wave&#8217;s claims about the usefulness of its devices, also don&#8217;t conclusively disprove those claims&#8221; is a very different message than what&#8217;s currently making it into the press.<\/p>\n<p><strong>Comparison to CPLEX is Rigged<\/strong><\/p>\n<p>Unfortunately, the USC paper is not the one that&#8217;s gotten the most press attention&#8212;perhaps because half of it inconveniently told the hypesters something they didn&#8217;t want to hear (&#8220;no speedup&#8221;).\u00a0 Instead, journalists have preferred a paper released this week by <a href=\"http:\/\/graphics8.nytimes.com\/packages\/pdf\/business\/quantum-study.pdf\">Catherine McGeoch and Cong Wang<\/a>, which reports that quantum annealing running on the D-Wave machine outperformed the CPLEX optimization package running on a classical computer by a factor of ~3600, on Ising spin problems involving 439 bits.\u00a0 Wow!\u00a0 That sounds awesome!\u00a0 But before rushing to press, let&#8217;s pause to ask ourselves: how can we reconcile this with the USC group&#8217;s result of <em>no<\/em> speedup?<\/p>\n<p>The answer turns out to be painfully simple.\u00a0 CPLEX is a general-purpose, off-the-shelf <strong>exact<\/strong> optimization package.\u00a0 <em>Of course<\/em> an exact solver can&#8217;t compete against quantum annealing&#8212;or for that matter, against <em>classical<\/em> annealing or other classical heuristics!\u00a0 Noticing this problem, McGeoch and Wang do also compare the D-Wave machine against tabu search, a classical heuristic algorithm.\u00a0 When they do so, they find that an advantage for the D-Wave machine persists, but it becomes much, much smaller (they didn&#8217;t report the exact time comparison).\u00a0 Amusingly, they write in their &#8220;Conclusions and Future Work&#8221; section:<\/p>\n<blockquote><p>It would of course be interesting to see if highly tuned implementations of, say, tabu search or simulated annealing could compete with Blackbox or even QA\u00a0[i.e., the D-Wave machines] on QUBO [quadratic binary optimization] problems; some preliminary work on this question is underway.<\/p><\/blockquote>\n<p>As I said above, at the time\u00a0McGeoch and Wang&#8217;s paper was released to the media (though maybe not at the time it was written?), <span style=\"color: #000000;\">the &#8220;highly tuned implementation&#8221; of simulated annealing that they ask for had already been written and tested, and the result was that it outperformed the D-Wave machine on all instance sizes tested.<\/span>\u00a0 In other words, <span style=\"color: #ff0000;\"><strong>their comparison to CPLEX had already been superseded by a much more informative comparison&#8212;one that gave the &#8220;opposite&#8221; result&#8212;before it ever became public.<\/strong><\/span>\u00a0 For obvious reasons, most press reports have simply ignored this fact.<\/p>\n<p><strong>Troyer, Lidar, and Stone Soup<\/strong><\/p>\n<p>Much of what I&#8217;ve written in this post, I learned by talking to Matthias Troyer&#8212;the man who carefully experimented with the D-Wave machine and figured out how to beat it using simulated annealing, and who I regard as probably the world&#8217;s #1 expert right now on what exactly the machine does.\u00a0 Troyer wasn&#8217;t shy about sharing his opinions, and while couched with qualifications, they tended toward extremely skeptical.\u00a0 For example, Troyer conjectured that, <em>if<\/em> D-Wave ultimately succeeds in getting a speedup over classical computers in a fair comparison, then it will probably be by improving coherence and calibration, incorporating error-correction, and doing other things that &#8220;traditional,&#8221; &#8220;academic&#8221; quantum computing researchers had said all along would need to be done.<\/p>\n<p>As I said, Daniel Lidar is another coauthor on the USC paper, and also recently visited MIT to speak.\u00a0 Lidar and Troyer agree on the basic facts&#8212;yet Lidar noticeably differed from Troyer, in trying to give each fact the most &#8220;pro-D-Wave spin&#8221; it could possibly support.\u00a0 Lidar spoke at our quantum group meeting, not about the D-Wave vs. simulated annealing performance comparison (which he agrees with), but about a proposal of his for incorporating quantum error-correction into the D-Wave device, together with some experimental results.\u00a0 He presented his proposal, not as a <em>reductio ad absurdum<\/em> of D-Wave&#8217;s entire philosophy, but rather as a positive opportunity to get a quantum speedup using D-Wave&#8217;s approach.<\/p>\n<p>So, to summarize my current assessment of the situation: <em>yes, absolutely, D-Wave might someday succeed&#8212;ironically, by adapting the very ideas from &#8220;the gate model&#8221; that its entire business plan has been based on avoiding, and that D-Wave founder Geordie Rose has <a href=\"http:\/\/www.wired.com\/wiredenterprise\/2012\/02\/dwave-quantum-cloud\/all\/\">loudly denigrated<\/a> for D-Wave&#8217;s entire history! \u00a0<\/em>If that&#8217;s what happens, then I predict that science writers, and blogs like &#8220;nextbigfuture,&#8221; will announce from megaphones that D-Wave has been vindicated at last, while its narrow-minded, theorem-obsessed, ivory-tower academic naysayers now have egg all over their faces.\u00a0 No one will care that the path to success&#8212;through quantum error-correction and so on&#8212;actually proved the academic critics <strong>right<\/strong>, and that D-Wave&#8217;s &#8220;vindication&#8221; was precisely like that of the deliciousness of <a href=\"http:\/\/en.wikipedia.org\/wiki\/Stone_Soup\">stone soup<\/a> in the old folktale.\u00a0 As for myself, I&#8217;ll probably bang my head on my desk until I sustain so much brain damage that I no longer care either.\u00a0 But at least I&#8217;ll still have tenure, and the world will have quantum computers.<\/p>\n<p><strong>The Messiah&#8217;s Quantum Annealer<br \/>\n<\/strong><\/p>\n<p>Over the past few days, I&#8217;ve explained the above to at least six different journalists who asked.\u00a0 And I&#8217;ve repeatedly gotten a striking response: &#8220;What you say makes sense&#8212;but then why are all these prestigious people and companies investing in D-Wave?\u00a0 Why did Bo Ewald, a prominent Silicon Valley insider, recently join D-Wave as president of its US operations?\u00a0 Why the deal with Lockheed Martin?\u00a0 Why the <a href=\"http:\/\/www.forbes.com\/sites\/alexknapp\/2013\/05\/16\/nasa-and-google-partner-to-purchase-a-d-wave-quantum-computer\/\">huge deal with NASA and Google<\/a>, just announced today?\u00a0 What&#8217;s your reaction to all this news?&#8221;<\/p>\n<p>My reaction, I confess, is simple.\u00a0 <em>I don&#8217;t care<\/em>&#8212;I actually told them this&#8212;<em>if the former Pope Benedict has ended his retirement to become D-Wave&#8217;s new marketing director.<\/em>\u00a0 I don&#8217;t care if the Messiah has come to Earth on a flaming chariot, not to usher in an age of peace but simply to spend $10 million on D-Wave&#8217;s new Vesuvius chip.\u00a0 And if you imagine that I&#8217;ll <em>ever<\/em> care about such things, then you obviously don&#8217;t know much about me.\u00a0 I&#8217;ll tell you what: if peer pressure is where it&#8217;s at, then come to me with the news that Umesh Vazirani, or Greg Kuperberg, or Matthias Troyer is now convinced, based on the latest evidence, that D-Wave&#8217;s chip asymptotically outperforms simulated annealing in a fair comparison, and does so because of quantum effects.\u00a0 Any one such scientist&#8217;s considered opinion would mean more to me than 500,000 business deals.<\/p>\n<p><strong>The Argument from Consequences<\/strong><\/p>\n<p>Let me end this post with an argument that several of my friends in physics have <em>explicitly<\/em> made to me&#8212;not in the exact words below but in similar ones.<\/p>\n<p style=\"padding-left: 30px;\">&#8220;Look, Scott, let the investors, government bureaucrats, and gullible laypeople believe whatever they want&#8212;and let D-Wave keep telling them whatever&#8217;s necessary to stay in business.\u00a0 It&#8217;s unsportsmanlike and uncollegial of you to hold D-Wave&#8217;s <em>scientists<\/em> accountable for whatever wild claims their company&#8217;s PR department might make.\u00a0 After all, <em>we&#8217;re<\/em> in this game too!\u00a0 Our universities put out all sorts of overhyped press releases, but we don&#8217;t complain because we know that it&#8217;s done for our benefit.\u00a0 Besides, you&#8217;d doubtless be trumpeting the same misleading claims, if you were in D-Wave&#8217;s shoes and needed the cash infusions to survive.\u00a0 Anyway, who really cares whether there&#8217;s a quantum speedup yet or no quantum speedup?\u00a0 At least D-Wave is out there <em>trying<\/em> to build a scalable quantum computer, and getting millions of dollars from Jeff Bezos, Lockheed, Google, the CIA, etc. etc. to do so&#8212;resources more of which would be directed <em>our<\/em> way if we showed a more cooperative attitude!\u00a0 If we care about scalable QCs <em>ever<\/em> getting built, then the wise course is to celebrate what D-Wave <em>has<\/em> done&#8212;they just demonstrated quantum annealing on 100 qubits, for crying out loud!\u00a0 So let&#8217;s all be grownups here, focus on the science, and ignore the marketing buzz as so much meaningless noise&#8212;just like a tennis player might ignore his opponent&#8217;s trash-talking (&#8216;your mother is a whore,&#8217; etc.) and focus on the game.&#8221;<\/p>\n<p>I get this argument: really, I do.\u00a0 I even concede that there&#8217;s something to be said for it.\u00a0 But let me now offer a contrary argument for the reader&#8217;s consideration.<\/p>\n<p>Suppose that, unlike in the &#8220;stone soup&#8221; scenario I outlined above, it eventually becomes clear that quantum annealing <em>can<\/em> be made to work on thousands of qubits, but that it&#8217;s a dead end as far as getting a quantum speedup is concerned.\u00a0 Suppose the evidence piles up that simulated annealing on a conventional computer will continue to beat quantum annealing, if even the slightest effort is put into optimizing the classical annealing code.\u00a0 If that happens, then <strong>I predict that the very same people now hyping D-Wave will turn around and&#8212;without the slightest acknowledgment of error on their part&#8212;declare that the <em>entire field<\/em> of quantum computing has now been unmasked as a mirage, a scam, and a chimera.<\/strong>\u00a0 The same pointy-haired bosses who now flock toward quantum computing, will flock away from it just as quickly and as uncomprehendingly.\u00a0 Academic QC programs will be decimated, despite the slow but genuine progress that they&#8217;d been making the entire time in a &#8220;parallel universe&#8221; from D-Wave.\u00a0 People&#8217;s contempt for academia is such that, while a D-Wave success would be trumpeted as its alone, a D-Wave failure would be blamed on the entire QC community.<\/p>\n<p>When it comes down to it, <em>that&#8217;s<\/em> the reason why I care about this matter enough to have served as &#8220;Chief D-Wave Skeptic&#8221; from 2007 to 2011, and enough to resume my post today.\u00a0 As I&#8217;ve said many times, <span style=\"color: #ff0000;\"><strong>I really, genuinely hope that D-Wave succeeds at building a QC that achieves an unambiguous speedup!<\/strong><\/span>\u00a0 I even hope the academic QC community will contribute to D-Wave&#8217;s success, by doing careful independent studies like the USC group did, and by coming up with proposals like Lidar&#8217;s for how D-Wave could move forward.\u00a0 On the other hand, in the strange, unlikely event that D-Wave <em>doesn&#8217;t<\/em> succeed, I&#8217;d like people to know that many of us in the QC community were doing what academics are <em>supposed<\/em> to do, which is to be skeptical and not leave obvious questions unasked.\u00a0 I&#8217;d like them to know that some of us simply tried to understand and describe what we saw in front of us&#8212;changing our opinions repeatedly as new evidence came in, but disregarding &#8220;meta-arguments&#8221; like my physicist friends&#8217; above.\u00a0 The reason I can joke about <a href=\"https:\/\/scottaaronson.blog\/?p=181\">how easy it is to bribe me<\/a> is that it&#8217;s actually kind of hard.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Wrap-Up (June 5): This will be my final update on this post (really!!), since the discussion seems to have reached a point where not much progress is being made, and since I&#8217;d like to oblige the commenters who&#8217;ve asked me to change the subject.\u00a0 Let me try to summarize the main point I&#8217;ve been trying [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_hide_featured_image":false,"_jetpack_featured_image_duplicate_dismissed":0,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[4,17],"tags":[],"class_list":["post-1400","post","type-post","status-publish","format-standard","hentry","category-quantum","category-speaking-truth-to-parallelism"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1400","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1400"}],"version-history":[{"count":41,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1400\/revisions"}],"predecessor-version":[{"id":3006,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1400\/revisions\/3006"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1400"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1400"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1400"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}