Insert D-Wave Post Here
In the two months since I last blogged, the US has continued its descent into madness. Yet even while so many certainties have proven ephemeral as the morning dew—the US’s autonomy from Russia, the sanity of our nuclear chain of command, the outcome of our Civil War, the constraints on rulers that supposedly set us apart from the world’s dictator-run hellholes—I’ve learned that certain facts of life remain constant.
The moon still waxes and wanes. Electrons remain bound to their nuclei. P≠NP proofs still fill my inbox. Squirrels still gather acorns. And—of course!—people continue to claim big quantum speedups using D-Wave devices, and those claims still require careful scrutiny.
With that preamble, I hereby offer you eight quantum computing news items.
Cathy McGeoch Episode II: The Selby Comparison
On January 17, a group from D-Wave—including Cathy McGeoch, who now works directly for D-Wave—put out a preprint claiming a factor-of-2500 speedup for the D-Wave machine (the new, 2000-qubit one) compared to the best classical algorithms. Notably, they wrote that the speedup persisted when they compared against simulated annealing, quantum Monte Carlo, and even the so-called Hamze-de Freitas-Selby (HFS) algorithm, which was often the classical victor in previous performance comparisons against the D-Wave machine.
Reading this, I was happy to see how far the discussion has advanced since 2013, when McGeoch and Cong Wang reported a factor-of-3600 speedup for the D-Wave machine, but then it turned out that they’d compared only against classical exact solvers rather than heuristics—a choice for which they were heavily criticized on this blog and elsewhere. (And indeed, that particular speedup disappeared once the classical computer’s shackles were removed.)
So, when people asked me this January about the new speedup claim—the one even against the HFS algorithm—I replied that, even though we’ve by now been around this carousel several times, I felt like the ball was now firmly in the D-Wave skeptics’ court, to reproduce the observed performance classically. And if, after a year or so, no one could, that would be a good time to start taking seriously that a D-Wave speedup might finally be here to stay—and to move on to the next question, of whether this speedup had anything to do with quantum computation, or only with the building of a piece of special-purpose optimization hardware.
A&M: Annealing and Matching
As it happened, it only took one month. On March 2, Salvatore Mandrà, Helmut Katzgraber, and Creighton Thomas put up a response preprint, pointing out that the instances studied by the D-Wave group in their most recent comparison are actually reducible to the minimum-weight perfect matching problem—and for that reason, are solvable in polynomial time on a classical computer. Much of Mandrà et al.’s paper just consists of graphs, wherein they plot the running times of the D-Wave machine and of a classical heuristic on the relevant instances—clearly all different flavors of exponential—and then Edmonds’ matching algorithm from the 1960s, which breaks away from the pack into polynomiality.
But let me bend over backwards to tell you the full story. Last week, I had the privilege of visiting Texas A&M to give a talk. While there, I got to meet Helmut Katzgraber, a condensed-matter physicist who’s one of the world experts on quantum annealing experiments, to talk to him about their new response paper. Helmut was clear in his prediction that, with only small modifications to the instances considered, one could see similar performance by the D-Wave machine while avoiding the reduction to perfect matching. With those future modifications, it’s possible that one really might see a D-Wave speedup that survived serious attempts by skeptics to make it go away.
But Helmut was equally clear in saying that, even in such a case, he sees no evidence at present that the speedup would be asymptotic or quantum-computational in nature. In other words, he thinks the existing data is well explained by the observation that we’re comparing D-Wave against classical algorithms for Ising spin minimization problems on Chimera graphs, and D-Wave has heroically engineered an expensive piece of hardware specifically for Ising spin minimization problems on Chimera graphs and basically nothing else. If so, then the prediction would be that such speedups as can be found are unlikely to extend either to more “practical” optimization problems—which need to be embedded into the Chimera graph with considerable losses—or to better scaling behavior on large instances. (As usual, as long as the comparison is against the best classical algorithms, and as long as we grant the classical algorithm the same non-quantum advantages that the D-Wave machine enjoys, such as classical parallelism—as Rønnow et al advocated.)
Incidentally, my visit to Texas A&M was partly an “apology tour.” When I announced on this blog that I was moving from MIT to UT Austin, I talked about the challenge and excitement of setting up a quantum computing research center in a place that currently had little quantum computing for hundreds of miles around. This thoughtless remark inexcusably left out not only my friends at Louisiana State (like Jon Dowling and Mark Wilde), but even closer to home, Katzgraber and the others at Texas A&M. I felt terrible about this for months. So it gives me special satisfaction to have the opportunity to call out Katzgraber’s new work in this post. In football, UT and A&M were longtime arch-rivals, but when it comes to the appropriate level of skepticism to apply to quantum supremacy claims, the Texas Republic seems remarkably unified.
When 15 MilliKelvin is Toasty
In other D-Wave-related scientific news, on Monday night Tameem Albash, Victor Martin-Mayer, and Itay Hen put out a preprint arguing that, in order for quantum annealing to have any real chance of yielding a speedup over classical optimization methods, the temperature of the annealer should decrease at least like 1/log(n), where n is the instance size, and more likely like 1/nβ (i.e., as an inverse power law).
If this is correct, then cold as the D-Wave machine is, at 0.015 degrees or whatever above absolute zero, it still wouldn’t be cold enough to see a scalable speedup, at least not without quantum fault-tolerance, something that D-Wave has so far eschewed. With no error-correction, any constant temperature that’s above zero would cause dangerous level-crossings up to excited states when the instances get large enough. Only a temperature that actually converged to zero as the problems got larger would suffice.
Over the last few years, I’ve heard many experts make this exact same point in conversation, but this is the first time I’ve seen the argument spelled out in a paper, with explicit calculations (modulo assumptions) of the rate at which the temperature would need to go to zero for uncorrected quantum annealing to be a viable path to a speedup. I lack the expertise to evaluate the calculations myself, but any experts who’d like to share their insight in the comments section are “warmly” (har har) invited.
“Their Current Numbers Are Still To Be Checked”
As some of you will have seen, The Economist now has a sprawling 10-page cover story about quantum computing and other quantum technologies. I had some contact with the author while the story was in the works.
The piece covers a lot of ground and contains many true statements. It could be much worse.
But I take issue with two things.
First, The Economist claims: “What is notable about the effort [to build scalable QCs] now is that the challenges are no longer scientific but have become matters of engineering.” As John Preskill and others pointed out, this is pretty far from true, at least if we interpret the claim in the way most engineers and businesspeople would.
Yes, we know the rules of quantum mechanics, and the theory of quantum fault-tolerance, and a few promising applications; and the basic building blocks of QC have already been demonstrated in several platforms. But if (let’s say) someone were to pony up $100 billion, asking only for a universal quantum computer as soon as possible, I think the rational thing to do would be to spend initially on a frenzy of basic research: should we bet on superconducting qubits, trapped ions, nonabelian anyons, photonics, a combination thereof, or something else? (Even that is far from settled.) Can we invent better error-correcting codes and magic state distillation schemes, in order to push the resource requirements for universal QC down by three or four orders of magnitude? Which decoherence mechanisms will be relevant when we try to do this stuff at scale? And of course, which new quantum algorithms can we discover, and which new cryptographic codes resistant to quantum attack?
The second statement I take issue with is this:
“For years experts questioned whether the [D-Wave] devices were actually exploiting quantum mechanics and whether they worked better than traditional computers. Those questions have since been conclusively answered—yes, and sometimes”
I would instead say that the answers are:
- depends on what you mean by “exploit” (yes, there are quantum tunneling effects, but do they help you solve problems faster?), and
- no, the evidence remains weak to nonexistent that the D-Wave machine solves anything faster than a traditional computer—certainly if, by “traditional computer,” we mean a device that gets all the advantages of the D-Wave machine (e.g., classical parallelism, hardware heroically specialized to the one type of problem we’re testing on), but no quantum effects.
Shortly afterward, when discussing the race to achieve “quantum supremacy” (i.e., a clear quantum computing speedup for some task, not necessarily a useful one), the Economist piece hedges: “D-Wave has hinted it has already [achieved quantum supremacy], but has made similar claims in the past; their current numbers are still to be checked.”
To me, “their current numbers are still to be checked” deserves its place alongside “mistakes were made” among the great understatements of the English language—perhaps a fitting honor for The Economist.
Defeat Device
Some of you might also have seen that D-Wave announced a deal with Volkswagen, to use D-Wave machines for traffic flow. I had some advance warning of this deal, when reporters called asking me to comment on it. At least in the materials I saw, no evidence is discussed that the D-Wave machine actually solves whatever problem VW is interested in faster than it could be solved with a classical computer. Indeed, in a pattern we’ve seen repeatedly for the past decade, the question of such evidence is never even directly confronted or acknowledged.
So I guess I’ll say the same thing here that I said to the journalists. Namely, until there’s a paper or some other technical information, obviously there’s not much I can say about this D-Wave/Volkswagen collaboration. But it would be astonishing if quantum supremacy were to be achieved on an application problem of interest to a carmaker, even as scientists struggle to achieve that milestone on contrived and artificial benchmarks, even as the milestone seems repeatedly to elude D-Wave itself on contrived and artificial benchmarks. In the previous such partnerships—such as that with Lockheed Martin—we can reasonably guess that no convincing evidence for quantum supremacy was found, because if it had been, it would’ve been trumpeted from the rooftops.
Anyway, I confess that I couldn’t resist adding a tiny snark—something about how, if these claims of amazing performance were found not to withstand an examination of the details, it would not be the first time in Volkswagen’s recent history.
Farewell to a Visionary Leader—One Who Was Trash-Talking Critics on Social Media A Decade Before President Trump
This isn’t really news, but since it happened since my last D-Wave post, I figured I should share. Apparently D-Wave’s outspoken and inimitable founder, Geordie Rose, left D-Wave to form a machine-learning startup (see D-Wave’s leadership page, where Rose is absent). I wish Geordie the best with his new venture.
Martinis Visits UT Austin
On Feb. 22, we were privileged to have John Martinis of Google visit UT Austin for a day and give the physics colloquium. Martinis concentrated on the quest to achieve quantum supremacy, in the near future, using sampling problems inspired by theoretical proposals such as BosonSampling and IQP, but tailored to Google’s architecture. He elaborated on Google’s plan to build a 49-qubit device within the next few years: basically, a 7×7 square array of superconducting qubits with controllable nearest-neighbor couplings. To a layperson, 49 qubits might sound unimpressive compared to D-Wave’s 2000—but the point is that these qubits will hopefully maintain coherence times thousands of times longer than the D-Wave qubits, and will also support arbitrary quantum computations (rather than only annealing). Obviously I don’t know whether Google will succeed in its announced plan, but if it does, I’m very optimistic about a convincing quantum supremacy demonstration being possible with this sort of device.
Perhaps most memorably, Martinis unveiled some spectacular data, which showed near-perfect agreement between Google’s earlier 9-qubit quantum computer and the theoretical predictions for a simulation of the Hofstadter butterfly (incidentally invented by Douglas Hofstadter, of Gödel, Escher, Bach fame, when he was still a physics graduate student). My colleague Andrew Potter explained to me that the Hofstadter butterfly can’t be used to show quantum supremacy, because it’s mathematically equivalent to a system of non-interacting fermions, and can therefore be simulated in classical polynomial time. But it’s certainly an impressive calibration test for Google’s device.
2000 Qubits Are Easy, 50 Qubits Are Hard
Just like the Google group, IBM has also publicly set itself the ambitious goal of building a 50-qubit superconducting quantum computer in the near future (i.e., the next few years). Here in Austin, IBM held a quantum computing session at South by Southwest, so I went—my first exposure of any kind to SXSW. There were 10 or 15 people in the audience; the purpose of the presentation was to walk through the use of the IBM Quantum Experience in designing 5-qubit quantum circuits and submitting them first to a simulator and then to IBM’s actual superconducting device. (To the end user, of course, the real machine differs from the simulation only in that with the former, you can see the exact effects of decoherence.) Afterward, I chatted with the presenters, who were extremely friendly and knowledgeable, and relieved (they said) that I found nothing substantial to criticize in their summary of quantum computing.
Hope everyone had a great Pi Day and Ides of March.
Follow
Comment #1 March 16th, 2017 at 9:57 am
Thank you for this fine post Scott. And thank you too, for your continuing stance — with which I agree entirely — opposing “know-nothing” American politics, .
I will mention too, that QIP 2017 in Seattle was a big success, not least your student-collaborator Shalev Ben-David’s well-received talk “Sculpting Quantum Speedups” (available as YouTube video 84dEqkOoOEk). Outstanding work.
Without knowing this particular DWAVE-centric Shtetl Optimized post was in the works, yesterday I drew upon QIP 2017 presentations in posting to Lance Fortnow and Bill GASARCH’s Computational Complexity weblog a comment addressing two high-profile questions:
My Fortnow/GASARCH comment surveyed the parallels between Terry Tao’s appreciation of Q1</b and Garnet Chan's appreciation of Q2 (as presented at QIP 2017).
As background, cf. Terry Tao’s Albert Einstein Memorial Lecture “Can the Navier-Stokes Equations Blow Up in Finite Time?” (Jerusalem 2015, YouTube DgmuGqeRTto) as parallel too Garnet Chan’s “Simulating Quantum Systems on Classical Computers” (YouTube yYwUQe2Aorw).
The Fortnow/GASARCH comment noted:
Obviously there’s no shortage of QIP 2017 grist for further Shtetl Optimized commentary. Exciting times! 🙂
We can all appreciate, in particular, that “mere polynomial” Chan-style/DWAVE-compatible simulation speedups can be, in practice, utterly transformational in their economic, strategic, medical, scientific, and mathematical implications.
Large kudos are extended to MicroSoft Research/StationQ for making all of the QIP 2017 talks available (details and video links here).
Comment #2 March 16th, 2017 at 10:03 am
Hi Scott, is there an easy way to describe the matrix for which Hofstadter state is realized as a state of non interacting fermions? (How many Fermions and modes are needed?)
Comment #3 March 16th, 2017 at 10:30 am
Glad to see you’re back, Scott, I was starting to worry!
Comment #4 March 16th, 2017 at 10:33 am
Scott: great post. I was waiting for something like this sine months!
Rose’s change does not surprise me. He stayed on the chair as long as possible, but he is smart enough to make the jump before the collapse (my opinion). I have to ask about this to friends at dwave..
Comment #5 March 16th, 2017 at 12:03 pm
From https://arxiv.org/abs/quant-ph/0012112, in which a (in hindsight quite poorly explained) annealing procedure is based on projecting away configurations in a way related to their suboptimality:
“Therefore the implicit cost in this scheme (and others like it) is energy: it turns out (see below) that if b ≡ log a is the effective temperature for an annealing schedule, then we will require on the order of a^D photons (here D is a distance scale for the TSP given below) for a successful realization”
Comment #6 March 16th, 2017 at 2:33 pm
Steve #5: Thanks for the link! It doesn’t surprise me that someone would’ve done a similar calculation much earlier. But shouldn’t b be the inverse temperature, rather than the temperature?
Comment #7 March 16th, 2017 at 2:34 pm
Gil #2: I don’t know the answer to that, but I’ll ask Andrew Potter.
Comment #8 March 16th, 2017 at 5:47 pm
Scott,
I’ve heard one of reasons google is pushing into quantum computing is they believe it may somehow help with machine learning. I keep hearing buzz-words like “quantum machine learning” lately but don’t know how this fits in with the work on quantum algorithms.
How are people hoping to using quantum computers to aid machine learning?
And are there any hints that it will actually be more efficient than classical machine learning?
Comment #9 March 16th, 2017 at 6:46 pm
Three noteworthy updates from Google, TDS and LANL:
1. Google upgrades to the D-Wave 2000Q
-https://www.dwavesys.com/press-releases/d-wave-2000q-system-be-installed-quantum-artificial-intelligence-lab-run-google-nasa
2. Temporal Defense Systems buys a D-Wave 2000Q
-https://www.dwavesys.com/press-releases/temporal-defense-systems-purchases-first-d-wave-2000q-quantum-computer
3. LANL has a D-Wave 1000 qubit machine
– http://www.lanl.gov/projects/national-security-education-center/information-science-technology/dwave/
– http://www.lanl.gov/discover/publications/1663/2016-july/not-magic-quantum.php
Comment #10 March 16th, 2017 at 8:32 pm
Scott- Indeed b is really $\beta$ in the paper. And a is really $\alpha = O(n)$ if you want a polytime solution, as shown a bit later therein. In fact a Boltzmann-Gibbs distribution naturally emerges in the (quite elementary) analysis.
Comment #11 March 16th, 2017 at 9:24 pm
Why do they deserve any consideration at all?
Comment #12 March 16th, 2017 at 9:56 pm
Marta #8: For my take on some of the recent quantum machine learning algorithms, see my Nature News piece “Read the Fine Print”. It’s an exciting and rapidly developing area. But a key question, which I don’t think has been sufficiently addressed, is to what extent the cases where the quantum ML algorithms work well are actually hard classically. It’s something I’d love to look into myself, or have a student look into. Note that if there are quantum/classical separations, they might actually be provable here, for example by giving lower bounds on randomized query complexity.
Comment #13 March 16th, 2017 at 10:18 pm
Douglas #11:
Why do they deserve any consideration at all?
For one thing, because Helmut Katzgraber, Matthias Troyer, and John Martinis find understanding the D-Wave machine to be scientifically interesting—even if their actual views about what’s going on with it are not far from mine. (Which isn’t a coincidence: people like them are the experts, so mostly I listen to them and try to learn.)
For a second, because I’ve learned that the outside world doesn’t care about arguments of the form “D-Wave already had X number of chances—if their claims didn’t survive scrutiny then, we’re not obligated even to consider them now.” Most people have incredibly short attention spans, and think the latest deal with Volkswagen or whatever means the burden is on us, the QC research community, to refute whatever D-Wave might be saying. Rather than complaining about this, I’ve tried to rise to the challenge and treat it as a consistent source of fodder for my blog. 🙂
Comment #14 March 16th, 2017 at 11:33 pm
Who is this outside world that you are trying to convince? Journalists? If you say “D-Wave is bullshit. Always has been,” won’t they print that?
Comment #15 March 16th, 2017 at 11:50 pm
Helmut Katzgraber should be in a unique position to resolve the Schrödinger Paradox.
Comment #16 March 17th, 2017 at 4:50 am
Raoul #15: What, because he can grab the Kat? But then he’ll just become entangled with the Kat, so he’ll know whether it’s alive or dead, but we still won’t.
Comment #17 March 17th, 2017 at 10:10 am
“Anyway, I confess that I couldn’t resist adding a tiny snark—something about how, if these claims of amazing performance were found not to withstand an examination of the details, it would not be the first time in Volkswagen’s recent history.” my initial responses of LOL and touche” have been dampened after i read https://www.nytimes.com/2017/03/06/science/volkswagen-emissions-scandal-air-pollution-deaths.html?_r=0
Comment #18 March 17th, 2017 at 10:22 am
This observation guides us to consider the overlap of
(1) questions that are wide open, and
(2) questions that are scientifically interesting, and
(3) questions that DWAVE machines help us to answer, and
(4) questions whose answers the employees of large corporations and national security agencies are legally, contractually, and morally free to discuss.
Distilling such questions is itself a considerable creative challenge. E.g., what geometric “shapes” characterize subsets of (Hilbert-space) quantum states that suffice to unravel density matrix of DWAVE devices?
Here “geometric” is understood to encompass those global/local mathematical properties that (at present) are studied by tools conceived by Liouville, Riemann, Serre, Lie, Kahler, Noether, Mac Lane, Grothendieck, Lefschetz (and dozens more).
Especially because these “Yellow Book” mathematical methods are not taught at the undergraduate level, researchers at conferences like QIP 2017 struggle mightily even to understand one another.
Humanity’s advancing understanding of general geometric principles helps in particular to advance our geometric understanding of DWAVE devices. Conversely, in virtue of their stubborn physicality, DWAVE devices insistently teach us mathematical lessons that otherwise we might be tempted to overlook.
In respect to devices as “dirty” as DWAVE’s, physicists as able as Wolfgang Pauli and Isidore Rabi gave their students notably bad advice back in the 1930s and 1940s. For example, in Robert Cahn’s The Coming of Materials Science (2003) we read (the following is edited for brevity)
In summary, it is well for researchers to ask themselves whether DWAVE dynamics arise from “Dreck” versus “Gelt”. As it seems to many researchers — including the aforementioned Helmut Katzgraber, Matthias Troyer, and John Martinis (uhhh … and me too) — an impressive body of mathematical and physical literature points us toward toward “Gelt”.
This is because, for humanity in general, the enduring “Gelt” is less DWAVE’s devices, and more humanity’s shared geometric, algebraic, dynamical and computational understanding of DWAVE’s devices.
It’s the sharing of our advancing DWAVE understanding that is (at it seems to me) the tough-but-fun part.
Comment #19 March 17th, 2017 at 10:24 am
I can see the headlines now:
Biggest Scientific Breakthrough of the Century Made by Company Whose Expensive Special-Purpose Hardware Repeatedly Failed to Beat a Laptop in Solving Cherry-Picked Problems
Ok… maybe that’s a long and hard-to-parse headline.
Comment #20 March 17th, 2017 at 10:41 am
Darn! That is the way quantum paradoxes always seem to go: you try to pin things down and dig deeper, and there is another paradox; kind of “Paradoxes all the way down”.
I have always thought that it MIGHT turn out that QC will never work, because every issue resolved uncovers another issue. Kind of “One darn thing after another, all the way down”.
Comment #21 March 17th, 2017 at 12:01 pm
Thoroughly enjoyed your summary as usual, so thanks.
This caught me by surprise, given the modest number of qubits. Could you briefly justify your optimism?
Comment #22 March 17th, 2017 at 12:35 pm
Probably a super silly question – but is there definite/obvious proof that quantum computers wouldn’t actually have less power than classical computers? Or are we certain that at the very least quantum algo are equivalent to classical ones?
Comment #23 March 17th, 2017 at 1:54 pm
I know that your blog post was about quantum computing news. At the same time, given what you stated about the US “continuing its descent into madness” (your quotes), have you and your family given any further thoughts to leaving the country for good?
I’m sure people in Canada would love for you to come here (I believe you were a postdoc at the Perimeter Institute in the past, so you’re fairly well familiar with the theoretical CS research community here).
Comment #24 March 17th, 2017 at 3:41 pm
Douglas #14:
If you say “D-Wave is bullshit. Always has been,” won’t they print that?
They probably would—and then D-Wave’s supporters would rejoice at how intemperate, uncollegial, and unresponsive to new events they had caught me being, and how that discredited anything further I had to say.
This stuff is hard. But I note that the actual experiments that Troyer, Katzgraber, and others did, showing how one can reproduce the D-Wave results classically, had a large effect on moving the conversation forward, even making it into the majority of the popular articles. So explaining the content of their papers, rather than just fuming about “bullshit,” seems like one of the most useful roles this blog can play.
Comment #25 March 17th, 2017 at 3:52 pm
George Stelle #21:
This caught me by surprise, given the modest number of qubits. Could you briefly justify your optimism?
Sure. If you simply put a random quantum circuit on 49 qubits, of a large enough depth, then the best classical algorithm anyone knows to sample the output distribution of that circuit will need at least about 249 or 563 trillion arithmetic operations, and a similar amount of memory. (You can also get by with much less memory, but only at the cost of pushing the number of operations even further up, to an amount that will grow with the depth of the circuit.)
So you could get all three of the following things, in a single experiment:
(1) An observed “quantum speedup,” in raw wall-clock time, by a factor of billions.
(2) A theoretical argument that, if you generalized to n qubits, the quantum complexity would scale like poly(n) while the classical complexity would scale like exp(n). (For this, see for example my recent paper with Lijie Chen.)
(3) A causal connection between (1) and (2).
And getting all three of those things in one experiment is basically what I mean by “achieving quantum supremacy.”
Comment #26 March 17th, 2017 at 3:58 pm
fred #22:
is there definite/obvious proof that quantum computers wouldn’t actually have less power than classical computers?
Yes. A basic theorem, proved early in a quantum computing theory course, says that
P ⊆ BPP ⊆ BQP.
I.e., quantum computers can (at the very least) efficiently emulate classical computers, moreover even if the classical computers are equipped with random-number generators. The way we prove this is simply by observing that certain quantum gates, like the Toffoli gate, are universal for classical computation (e.g. because they can simulate AND and NOT), and moreover we can generate random bits by applying Hadamard gates to initially |0⟩ qubits.
Or if that’s too abstract for you, we could always fall back on the “experimental proof”: whatever you’re using to read this blog comment is clearly universal for classical computation, and also clearly runs on a substrate of quantum mechanics, thereby illustrating that QM is at least capable of efficiently simulating a Turing machine. 😉
Comment #27 March 17th, 2017 at 4:14 pm
Aaron G #23: Thanks for the warm welcome to Canada!
There’s no question that, at the margin, Trump and Bannon’s rise to power has made me more open to the idea of moving out of the US. And if I did, then Waterloo, Canada—a place I love, and where I spent two of the best years of my life—would certainly be one the first places I’d think of.
Right now, though, no plans to move. The main considerations are:
(1) As terrible as Trump has been and will be for the US and the world, for now I’m OK personally, except for it being a lot harder to recruit international students—Austin remains the nice city it was under Obama, my main current grant comes from the Defense Department and seems in no danger of getting cancelled, etc. (Of course any of those things could change in a few years, and if so I’ll reassess the situation.)
(2) I still hold out hope that the sane part of the US will triumph in the end—either by getting Trump impeached, or by resoundingly defeating him in 2020, or in the longer term, by demographically overwhelming the Republicans (something that the Republicans are correct to fear—Trumpism can be seen as a desperate, last-ditch attempt to reassert the power of the old, white, rural, and uneducated over the young, multiethnic, urban, and educated, but it’s far from obvious that it will succeed).
(3) If Trumpism does succeed, then alas, I tend to think that not just the US but the entire world is doomed, and that moving from the US would at most buy a bit more time. 🙁
So, all in all, the current balance of considerations seems to point toward staying here and doing what I can to fight this.
Comment #28 March 17th, 2017 at 6:55 pm
I didn’t know that Google is also claiming ’50 qubits soon’ on top of IBM. I made a Metaculus.com question to ask when this will actually happen:
https://www.metaculus.com/questions/447/50-qubit-universal-quantum-computer/
interested in people’s opinions, here or there.
Comment #29 March 17th, 2017 at 8:31 pm
Anthony #28: For whatever it’s worth, I believe Google was claiming it before IBM was claiming it! 🙂
Comment #30 March 17th, 2017 at 10:22 pm
How does this problem relate to boson sampling? Is it essentially the circuit version?
Also, what’s the quantum circuit that solves the sampling problem you described?
Comment #31 March 17th, 2017 at 11:19 pm
Job #30: The sampling problem we’re talking about here is obviously closely related to BosonSampling—in both cases, the conjectured hardness arises from the little deviations from uniformity in the output distribution—but it differs by lacking the nice mathematical structure arising from the permanent. That’s both a good and a bad thing: good, because it plausibly makes it even more unlikely that a fast classical algorithm would exist to approximate the output distribution; but bad because it’s that much harder to theoretically analyze what’s going on. Again, for much more about these points, check out my recent paper with Lijie Chen.
The quantum circuit that solves the problem, of sampling from the output distribution of a given quantum circuit C, is just C itself! 🙂
Comment #32 March 17th, 2017 at 11:58 pm
Well ok. So unless the circuit computes a function that’s provably difficult to evaluate classically, we’re just checking that the QC is working properly.
And actually, that would be sufficient to convince me. If we can create a QC that correctly executes all random circuits we give it (with high probability), that’s good enough for me.
Comment #33 March 18th, 2017 at 12:05 am
Job #32: But you can also see a random quantum circuit C as “solving a problem,” namely the problem of producing samples from C’s output distribution. That’s not a useful problem, but it’s a problem that we do have strong reasons to think is hard classically—indeed, probably stronger than our reasons for thinking that factoring (for example) is hard classically. (Again, see my paper with Lijie.)
Comment #34 March 18th, 2017 at 12:22 am
Yes, but IMO that’s not sufficiently conclusive because we know that many of the random circuits can be efficiently sampled classically, and yet we’d be taking a successful quantum run as evidence for the contrary.
For proof of actual quantum supremacy, i would rather just run Simon’s algorithm on random Simon functions.
Comment #35 March 18th, 2017 at 3:43 am
Hi Scott, I’m the lead author of the recent D-Wave work. To set the record straight, the work of Mandrà et al. does not rise to the challenge implicit in our paper.
Specifically, our inputs, like the Google inputs of Denchev et al., are based on generating an Ising Hamiltonian on a 2D lattice (i.e., the logical problem), and embedding it on D-Wave’s Chimera graph by expanding each lattice node into a ferromagnetically-coupled cluster in the shape of a Chimera unit tile (to create the embedded problem).
We explicitly stated that the logical problems are easy. In the case of our inputs, the problems are polytime solvable because they have no fields. This is not a new result. The reduction that Mandrà et al. use is due to Barahona in 1982.
The solvers reported by Mandrà et al. simply look for and reverse the expansion of lattice nodes, then solve the logical problems, completely against the spirit of the exercise, which is to compare heuristic algorithms in a well-controlled environment of problems with both local ruggedness and global frustration in their energy landscapes (hence the title of our paper—Quantum Annealing amid Local Ruggedness and Global Frustration).
To be clear, there are plenty of cluster-detecting algorithms I would consider to be fair game. However, these would have to be algorithms that detect clusters dynamically and flip those clusters in the context of the embedded problem. For example, Swendsen and Wang’s cluster-based parallel tempering algorithm, which does exactly this, would be an ideal candidate. We tried it and it was not competitive on these problems, even when using a great deal of preprocessing on each problem to find an ideal temperature ladder. Mandrà et al. did apply this algorithm, but only directly to the logical problems which is not meaningful. I suggested to Katzgraber that they apply it to the embedded problems but this suggestion was ignored. Maybe you could ask him. He claims they have a highly-optimized implementation and I’d be very interested in seeing how it did on our embedded problems.
One might consider the work of Mandrà et al. to be fair treatment of the problems because one might say that if we aren’t bothering to hide the logical problems they’re fair game. But where does that lead us? We could hide the logical problems either by weakening bonds inside certain clusters to turn them from hard constraints to soft constraints, or splitting certain clusters into two clusters. Then they can tweak their solvers to sniff out those modifications, then we could come up with new modifications, ad nauseam. Would this arms race of increasingly baroque synthetic problems and tailored solvers really move science forward or would it just drag it into the mud and waste everybody’s time?
As far as I’m concerned, the challenge is still open. We have yet to see any software solvers, even on state-of-the-art GPUs, that, without sniffing out and directly solving the logical problems, solve our embedded problems faster than those we presented. Note that the same cannot be said for the Google problems. Selby’s solver can handle those with relative ease because almost all of the ‘difficulty’ of those synthetic problems is in the local gadgets. By contrast, our inputs have far more global frustration in the logical problems. Regardless of whether or not they can be solved in polynomial time, this frustration is meaningful in the study of heuristic algorithms.
Comment #36 March 18th, 2017 at 4:12 am
“or in the longer term, by demographically overwhelming the Republicans (something that the Republicans are correct to fear—”
I can only hope for more such honesty.
Comment #37 March 18th, 2017 at 7:05 am
Jonathan #36: I meant, of course, that the Republicans are correct to fear the US’s changing demographics in the same sense that the South was correct to fear Lincoln. That is, it’s instrumentally rational, conditional on broader commitments that are pretty horrifying.
Comment #38 March 18th, 2017 at 7:39 am
Jamie #35: Thanks for your comment. Indeed, when I met Helmut, my very first question for him was why it wouldn’t be possible to evade the reduction to perfect matching by modifying the instances a bit, and I discussed his response in detail in the post.
We might say the situation is analogous to that of cryptanalysts who break a much-touted cryptosystem using some silly side-channel attack—whereupon the inventors of the cryptosystem complain that the cryptanalysts violated “the spirit of the exercise.” In such a case, I’m actually inclined to be sympathetic to the cryptosystem inventors … but maybe only to the extent that I agree with “the spirit of the exercise” in the first place!
In this case, as I said in the post, I start from the presupposition (open to being refuted, of course) that whatever speedups there are to be found with the D-Wave device, are likely to have much more to do with the heroic engineering of a piece of special-purpose hardware for Ising spin minimization on Chimera graphs, than with the genuine asymptotic advantages that make people excited about quantum computing in the first place. My reasons for thinking that have to do with the spectral gaps for interesting NP-complete problem instances shrinking exponentially with problem size, and my difficulty in understanding how you navigate that at a fixed nonzero temperature.
So maybe the right analogy is that a cryptosystem of a kind that seems fundamentally impossible to build in a secure way, was indeed broken, but for an incidental reason rather than the fundamental one. I hope my post successfully got across that this is what happened.
Comment #39 March 18th, 2017 at 11:27 am
Howdy! A couple of comments…
First, the comment in the blog post “In other words, he thinks the existing data is well explained by the observation that we’re comparing D-Wave against classical algorithms for Ising spin minimization problems on Chimera graphs, and D-Wave has heroically engineered an expensive piece of hardware specifically for Ising spin minimization problems on Chimera graphs and basically nothing else.” refers exclusively to minimization of cost functions. It could be that the DW device could be used for other applications where it might excel compared to classical methods.
Second, yes, the paper by King et al. does mention that the logical problems should be easy. So why was this not added to the manuscript in more detail? I guess the best analogy of what is happening here is that we have an arms race. And until DW does not develop the hydrogen bomb, we will be going back and forth.
Note also, that in our paper we suggest a very simple modification of the problems that will render exact methods useless and will likely be very hard for other SOA classical solvers due to the high connectivity of the graph.
I thus encourage everyone to read our paper beyond the first few pages and take a peak at the solution we offer towards the end…
Comment #40 March 18th, 2017 at 3:11 pm
Aaron G Says: 23, Scott #27 re “continuing its descent into madness”.
While it is obviously unfortunate that we find ourselves in this fluke drama, the good news is that the U.S. Constitution and system is proving to be pretty resilient. So far, the longterm damage is pretty limited, and most of the worst appears to be getting stuck in the mud. If the “little hands” guy is gone pretty soon, things should recover rapidly, and hopefully he can take of lot of the loonies in congress down with him.
If I was running a gambling establishment and taking bets on how long the current president lasts, I would set the “over/under” for the date of resignation, impeachment, or death at two years from inauguration, i.e., Jan 20 2019. What’s his name is one of the oldest presidents ever, obviously out of shape, the kind of person who would never listen to a doctor, under high stress, and (in the biggest show of his live) his trustworthy bluster and BS’ing isn’t working very good anymore. And, there is always the possibility of an Old Testament style lightning bolt.
Comment #41 March 18th, 2017 at 6:38 pm
Scott #38: I think we’re in agreement about the trivial side-channel attack. And I understand also that you’re waiting for quantum-attributable asymptotic speedup and that constant-factor speedups aren’t that interesting to you. But those are two separate issues.
My concern is that your post frames our work and the work of Mandrà et al. in a way that I think many readers, right or wrong, could go away thinking that D-Wave came out with a big claim and was promptly smacked down, which I think you’d agree is not at all what happened. I’m talking specifically about the two paragraphs starting “So, when people asked me…” and “As it happened….”
If you really do believe that the Mandrà et al. note amounts to “reproducing the observed results classically”, then that’s something we’ll just have to disagree on. Otherwise, I’d be very grateful if you’d consider clarifying this in your post.
I for one was hoping to see an honest effort from the skeptics to match our performance on the embedded problems. The HFS algorithm could be multithreaded, run on beefier CPUs, and tweaked beyond Selby’s implementation to get a speedup of maybe 10x to 30x. Maybe bit-packing parallelism applied to cluster parallel tempering would make it competitive. There might be more powerful GPU-based algorithms than SA and QMC. For example, can cluster parallel tempering be implemented efficiently on GPUs in a way I haven’t realized? Beyond that, if parallelism spreads across multiple processing units, there will be significant communication overhead. So can classical methods actually match our results on these simple and well-motivated synthetic inputs without just ignoring the point of the whole exercise and sneaking in the back door?
This kind of work would actually move the science forward and I’m still hoping to see some from somebody.
Helmut #39: There are two issues with your approach. The first is that you’re attacking the logical problems directly, and the second is that you’re using Barahona’s reduction to solve the logical problem exactly in polytime.
If we wanted to prevent the second issue, it’s easy. All we’d have to do is add fields to the logical problem. The problem then becomes NP-complete [Barahona 1982]. You claim that your solver can also solve the Google problems in polytime but I don’t see how this can be correct, unless you’re using a custom reduction for those, because they have fields.
The bigger issue is the first one, i.e., that you’re just attacking the logical problems directly. This has nothing to do with the logical problems being NP-complete or not and would therefore not be affected by the suggestions in your paper. We could only prevent it by attempting to “hide the back door” in the pointless arms race. And to what end? Imagine we softened certain clusters in a way that the logical problem could not be attacked directly and nobody could match our performance even with knowledge of the problem class. All we would have is more highly-contrived synthetic instances that, in my opinion, are a less-valuable testbed than the one we started with. This would also be an immense waste of time and we all have more important work we should be doing instead. Playing whack-a-mole with synthetic inputs and tailored solvers does nothing to advance the science.
Comment #42 March 19th, 2017 at 12:15 am
Jamie King #41: Again thanks for your constructive engagement.
I would say that Helmut et al. did reproduce your results, but in such a way that you’ll almost certainly be able to evade what they did in the next volley—thereby forcing the skeptics back to the sorts of classical algorithms that are of greater interest to you. I look forward to seeing that happen, and blogging about the next round.
But I’d also add that I think all sides in this debate should be wary of shifting goalposts! To take an example: I remember a couple years ago, when D-Wave managed to outperform simulated annealing on suitably-designed instances, but the HFS algorithm still beat it. At that time, certain D-Wave fans explained to me at length why simulated annealing was the relevant comparison, and using the HFS algorithm was just cheating, since that algorithm was preprogrammed to know about the 8-bit clusters, and how they should all be flipped at once.
But now that you have instances where D-Wave outperforms HFS (at least by some constant factor—asymptotically is a different question), now we learn that HFS is the key benchmark, the gold standard of classical algorithms against which D-Wave should always have been compared. 🙂
Of course, none of us want to be the person who (as Stephen Colbert put it) “believes the exact same thing on Wednesday that they did on Monday, regardless of what happened on Tuesday.” E.g., I no longer criticize D-Wave for not having demonstrated quantum tunneling behavior, not subjecting its claims to scrutiny by outside experts, or making absurd statements about quantum computing as a whole, because in all three respects, things really improved substantially in the last decade (which is awesome!).
But I do think I’ve been consistent this whole time about what counts as “success” for me—and that’s a big, unambiguous speedup by a quantum computer compared to all known conventional methods for some task, together with a convincing argument that that speedup arose by virtue of the quantum computer’s being a quantum computer, and not by virtue of incidental, non-quantum properties that we could reproduce with FPGAs or whatever. I think such an achievement will be a sufficiently historic milestone for our field, and for science more broadly, that it’s worth being crystal-clear about it, accepting no substitutes, and trying to keep the press, funding bodies, etc. from crying wolf before we’re actually there. I wouldn’t want to hold D-Wave to any lesser standard. 🙂
Comment #43 March 19th, 2017 at 12:40 pm
Scott #42: While I agree with the last paragraph of your comment, I think that D-Wave should actually aim for a different standard; namely, they should demonstrate that solving some type of problem with their devices is cheaper than solving the same problem with ordinary computers. If they can’t do that, then they’ll have no hope of widespread commercial adoption of their hardware (which, after all, should be their ultimate goal). Of course this is not in any way specific to D-Wave; if any kind of quantum computer is to be more than just an academic exercise, its operating cost is at least as important as its speed. However, as far as I’m aware, only D-Wave can actually measure things like the power consumption of their device and get meaningful results.
Comment #44 March 19th, 2017 at 7:16 pm
Is it possible that Volkswagen has made a deal with D-wave because they want a very fast special-purpose hardware for some computational problem, whether quantum speedups are involved or not? If they have a real world problem to solve, then they might not care about where the speedups come from.
Scott: Zach says at http://www.smbc-comics.com/comic/soonish that you have written back cover blurb for his new book (which will be released in 2017-10). The actual quote seems somewhat out of character for you, but Zach promises that only one of you were coerced (I believe that means he didn’t threaten you with torturing a thousand copies of you). Can you expand on this or anything else about his book?
Comment #45 March 19th, 2017 at 9:50 pm
jonas #44: I’d also find it astonishing if a piece of non-quantum special-purpose annealing hardware were to outperform conventional computers in a fair comparison, not for finding low-energy states for the hardware’s own connection topology, but for “real-world” problems that needed to be embedded into the hardware with considerable losses. Not saying it’s impossible, but one should also consider the Occam’s Razor possibility (quantum traffic optimization sounds cool, Volkswagen is happy, D-Wave is happy, the press is happy, only ones not happy are some pointy-headed academics, what’s the problem? 🙂 ).
Yes, I did read an advance copy of Soonish and I did think it was amazing (though what appeared as my jacket blurb was a small truncation of a larger thing I wrote). I consider Zach and Kelly personal friends at this point, so you should take my recommendation with a large grain of salt, but having said that, yes, you should totally read their book!
Comment #46 March 20th, 2017 at 12:19 am
(I wonder if Scott will reply to this since its posted after another post has already gone up.)
I can understand why journalists would hype D-wave works!
I can understand why people at D-wave would hype D-wave works!
But VW and other companies that have bought a D-wave machine with real money- why are they doing it? Don’t they have their own scientists look at D-wave honestly and advise them not to?
I realize this question might not be in your domain but you know folks who know folks- so a pointer to an article or person who might know, in essense, WHY DO PEOPLE WITH ACTUAL MONEY TO LOSE INVEST IN D-WAVE, please point me to them.
Comment #47 March 20th, 2017 at 7:15 am
@GASARCH I guess its because for giant companies like VW, LM, etc the money invested on a D-WAVE machine is probably less than peanuts and it might have some impact on their public image (VW desperately needs ANY kind of positive news…but I doubt it will help)
Comment #48 March 20th, 2017 at 8:53 am
Please let me second GASARCH’s request.
Sufficiently many, sufficiently broad-ranging answers to his question are possible, that an wonderfully provocative Shtetl Optimized essay could be devoted to it.
It was Tom Paine who said:
Today’s quantum researchers have it easier than Tom Paine, in that a Paine-style “age of revolution” has arrived for quantum research, and fortunately the ArXiv server, Google, and the quantum blog-o-sphere are together supplying us with quotes in sufficient abundance, as to richly and diversely answer GASARCH’s excellent question. 🙂
—
PS The Paine quote is from Chapter 1, footnote 18 of Bernard Vincent’s The Transatlantic Republican: Thomas Paine and the Age of Revolution (2005) … a work that conveys plenty of lessons (as I read it anyway) for quantum researchers.
Comment #49 March 20th, 2017 at 9:04 am
[…] el resumen de la situación actual de Scott Aaronson, “Insert D-Wave Post Here,” Shtetl-Optimized, 16 Mar 2017; por ello en esta entrada te resumo su resumen y te recomiendo consultar el original para […]
Comment #50 March 20th, 2017 at 10:26 am
John Sidles #48: I agree with the answer of GS #47. I would add that for a large organization, just getting experience in playing around with a primitive QC—even if it’s not actually faster for anything—could easily be justified as worth the $15 million price tag. (And while I don’t have confirmation for this, I’ve been told that, the way supercomputer sales work, the buyer pays much much less than the sticker price anyway.)
Comment #51 March 25th, 2017 at 7:18 am
[…] disappointing not only for me. Some points may be found in Scott Aaronson’s blog post. But after similar claim “physicists go home” in a lecture couple year ago and some thematic […]
Comment #52 April 4th, 2017 at 4:31 pm
will you pay for more than a quality meal for a DWAVE machine?
Comment #53 October 19th, 2017 at 11:43 am
[…] A good round-up of D-Wave progress by Scott Aaronson. […]