{"id":4447,"date":"2019-12-28T10:08:12","date_gmt":"2019-12-28T16:08:12","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=4447"},"modified":"2019-12-28T18:44:28","modified_gmt":"2019-12-29T00:44:28","slug":"quantum-computing-motte-and-baileys","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=4447","title":{"rendered":"Quantum computing motte-and-baileys"},"content":{"rendered":"\n

In the wake of two culture-war posts—the first<\/a> on the term “quantum supremacy,” the second<\/a> on the acronym “NIPS”—it’s clear that we all need to cool off with something anodyne and uncontroversial. Fortunately, this holiday season, I know just the thing to bring everyone together: groaning about quantum computing hype!<\/p>\n\n\n\n

When I was at the Q2B conference<\/a> in San Jose, I learned about lots of cool stuff that’s happening in the wake of Google’s quantum supremacy announcement. I heard about the 57-qubit superconducting chip that the Google group is now building, following up on its 53-qubit one; and also about their first small-scale experimental demonstration of my certified randomness protocol. I learned about recent progress on costing out the numbers of qubits and gates needed to do fault-tolerant quantum simulations of useful chemical reactions (IIRC, maybe a hundred thousand qubits and a few hours’ worth of gates—scary, but not Shor’s algorithm scary).<\/p>\n\n\n\n

I also learned about two claims about quantum algorithms that startups have made, and which are being wrongly interpreted. The basic pattern is one that I’ve come to know well over the years, and which you could call a science version of the motte-and-bailey<\/a>. (For those not up on nerd blogosphere terminology: in medieval times, the motte was a dank castle to which you\u2019d retreat while under attack; the bailey was the desirable land that you\u2019d farm once the attackers left.)<\/p>\n\n\n\n

To wit:<\/p>\n\n\n\n

  1. Startup makes claims that have both a true boring interpretation (e.g., you can do X with a quantum computer), as well as a false exciting interpretation (e.g., you can do X with a quantum computer, and it would actually make sense to do this, because you’ll get an asymptotic speedup over the best known classical algorithm<\/em>).<\/li>
  2. Lots of business and government people get all excited, because they assume the false exciting interpretation must be true (or why else would everyone be talking about this?). Some of those people ask me for comment.<\/li>
  3. I look into it, perhaps by asking the folks at the startup. The startup folks clarify that they meant only the true boring interpretation. To be sure, they’re actively exploring<\/em> the false exciting interpretation—whether some parts of it might be true after all—but they’re certainly not making any claims about it that would merit, say, a harsh post on Shtetl-Optimized<\/em>.<\/li>
  4. I’m satisfied to have gotten to the bottom of things, and I tell the startup folks to go their merry way.<\/li>
  5. Yet many people continue to seem as excited as if the false exciting interpretation had been shown to be true. They continue asking me questions that presuppose its truth.<\/li><\/ol>\n\n\n\n

    Our first instance of this pattern is the recent claim<\/a>, by Zapata Computing<\/a>, to have set a world record for integer factoring (1,099,551,473,989 = 1,048,589 \u00d7 1,048,601) with a quantum computer, by running a QAOA\/variational algorithm on IBM’s superconducting device. Gosh! That sure sounds a lot better than the 21 that’s been factored with Shor’s algorithm, doesn’t it?<\/p>\n\n\n\n

    I read the Zapata paper<\/a> that this is based on, entitled “Variational Quantum Factoring,” and I don’t believe that a single word in it is false. My issue is something the paper omits<\/em>: namely, that once you’ve reduced factoring to a generic optimization problem, you’ve thrown away all the mathematical structure that Shor’s algorithm<\/a> cleverly exploits, and that makes factoring asymptotically easy for a quantum computer. And hence there’s no reason to expect your quantum algorithm to scale any better than brute-force trial division (or in the most optimistic scenario, trial division enhanced with Grover search). On large numbers, your algorithm will be roundly outperformed even by classical<\/em> algorithms that do exploit structure, like the Number Field Sieve<\/a>. Indeed, the quantum computer’s success at factoring the number will have had little or nothing to do with its being quantum<\/em> at all—a classical optimization algorithm would’ve served as well. And thus, the only reasons to factor a number on a quantum device in this way, would seem to be stuff like calibrating the device.<\/p>\n\n\n\n

    Admittedly, to people who work in quantum algorithms, everything above is so obvious that it doesn’t need to be said. But I learned at Q2B that there are interested people for whom this is not<\/em> obvious, and even comes as a revelation. So that’s why I’m saying it.<\/p>\n\n\n\n

    Again and again over the past twenty years, I’ve seen people reinvent the notion of a “simpler alternative” to Shor’s algorithm: one that cuts out all the difficulty of building a fault-tolerant quantum computer. In every case, the trouble, typically left unstated, has been that these alternatives also<\/em> cut out the exponential speedup that’s Shor’s algorithm’s raison d’\u00eatre.<\/p>\n\n\n\n

    Our second example today of a quantum computing motte-and-bailey is the claim, by Toronto-based quantum computing startup Xanadu<\/a>, that Gaussian BosonSampling<\/a> can be used to solve all sorts of graph problems, like graph isomorphism, graph similarity, and densest subgraph. As the co-inventor of BosonSampling<\/a>, few things would warm my heart more than finding an actual application for that model (besides quantum supremacy experiments and, perhaps, certified random number generation). But I still regard this as an open problem—if by “application,” we mean outperforming what you could’ve done classically.<\/p>\n\n\n\n

    In papers (see for example here<\/a>, here<\/a>, here<\/a>), members of the Xanadu team have given all sorts of ways to take a graph, and encode it into an instance of Gaussian BosonSampling, in such a way that the output distribution will then reveal features of the graph, like its isomorphism type or its dense subgraphs. The trouble is that so far, I\u2019ve seen no indications that this will actually lead to quantum algorithms that outperform the best classical algorithms, for any graph problems of practical interest.<\/p>\n\n\n\n

    In the case of Densest Subgraph, the Xanadu folks use the output of a Gaussian BosonSampler to seed (that is, provide an initial guess for) a classical local search algorithm. They say they observe better results this way than if they seed that classical local search algorithm with completely random initial conditions. But of course, the real question is: could we get equally good results by seeding with the output of some classical<\/em> heuristic? Or by solving Densest Subgraph with a different approach entirely? Given how hard it\u2019s turned out to be just to verify<\/em> that the outputs of a BosonSampling device come from such a device at all, it would seem astonishing if the answer to these questions wasn\u2019t \u201cyes.\u201d<\/p>\n\n\n\n

    In the case of Graph Isomorphism, the situation is even clearer. There, the central claim made by the Xanadu folks is that given a graph G, they can use a Gaussian BosonSampling device to sample a probability distribution that encodes G\u2019s isomorphism type. So, isn\u2019t this \u201cpromising\u201d for solving GI with a quantum computer? All you\u2019d need to do now is invent some fast classical algorithm that could look at the samples coming from two graphs G and H, and tell you whether the probability distributions were the same.<\/p>\n\n\n\n

    Except, not really. While the Xanadu paper never says so, if all you want is to sample a distribution that encodes a graph\u2019s isomorphism type, that\u2019s easy to do classically! (I even put this on the final exam for my undergraduate Quantum Information Science course a couple weeks ago.) Here\u2019s how: given as input a graph G, just output G but with its vertices randomly permuted. Indeed, this will even provide a further property, better than anything the BosonSampling approach has been shown to provide (or than it probably does provide): namely, if G and H are not<\/em> isomorphic, then the two probability distributions will not only be different but will have disjoint supports. Alas, this still leaves us with the problem of distinguishing which distribution a given sample came from, which is as hard as Graph Isomorphism itself. None of these approaches, classical or quantum, seem to lead to any algorithm that\u2019s subexponential time, let alone competitive with the \u201cBabai approach\u201d<\/a> of thinking really hard about graphs.<\/p>\n\n\n\n

    All of this stuff falls victim to what I regard as the Fundamental Error of Quantum Algorithms Research: namely, to treat it as “promising” that a quantum algorithm works at all, or works better than some brute-force classical algorithm, without asking yourself whether there are any indications that your approach will ever<\/em> be able to exploit interference of amplitudes to outperform the best<\/em> classical algorithm.<\/p>\n\n\n\n

    Incidentally, I\u2019m not sure exactly why, but in practice, a major red flag that the Fundamental Error is about to be committed is when someone starts talking about \u201chybrid quantum\/classical algorithms.\u201d By this they seem to mean: \u201coutside the domain of traditional quantum algorithms, so don\u2019t judge us by the standards of that domain.\u201d But I liked the way someone at Q2B put it to me: every<\/em> quantum algorithm is a \u201chybrid quantum\/classical algorithm,\u201d with classical processors used wherever they can be, and qubits used only where they must be.<\/p>\n\n\n\n

    The other thing people do, when challenged, is to say \u201cwell, admittedly we have no rigorous proof<\/em> of an asymptotic quantum speedup\u201d\u2014thereby brilliantly reframing the whole conversation, to make people like me look like churlish theoreticians insisting on an impossible and perhaps irrelevant standard of rigor, blind to some huge practical quantum speedup that\u2019s about to change the world. The real issue, of course, is not that they haven\u2019t given a proof<\/em> of a quantum speedup (in either the real world or the black-box world); rather, it\u2019s that they\u2019ve typically given no reasons whatsoever to think that there might<\/em> be a quantum speedup, compared to the best classical algorithms available.<\/p>\n\n\n\n

    In the holiday spirit, let me end on a positive note. When I did the Q&A at Q2B—the same one where Sarah Kaiser asked me to comment on the term “quantum supremacy”—one of my answers touched on the most important theoretical open problems about sampling-based quantum supremacy experiments. At the top of the list, I said, was whether there’s some interactive protocol by which a near-term quantum computer can not only exhibit quantum supremacy, but prove<\/em> it to a polynomial-time-bounded classical skeptic. I mentioned that there was one<\/em> proposal for how to do this, in the IQP model, due to Bremner and Shepherd<\/a>, from way back in 2008. I said that their proposal deserved much more attention than it had received, and that trying to break it would be one obvious thing to work on. Little did I know that, literally while I was speaking<\/strong>, a paper was being posted to the arXiv<\/a>, by Gregory Kahanamoku-Meyer, that claims to break Bremner and Shepherd’s protocol. I haven’t yet studied the paper, but assuming it’s correct, it represents the first clear progress on this problem in years (even though of a negative kind). Cool!!<\/p>\n","protected":false},"excerpt":{"rendered":"

    In the wake of two culture-war posts—the first on the term “quantum supremacy,” the second on the acronym “NIPS”—it’s clear that we all need to cool off with something anodyne and uncontroversial. Fortunately, this holiday season, I know just the thing to bring everyone together: groaning about quantum computing hype! When I was at the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","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},"categories":[5,4],"tags":[],"class_list":["post-4447","post","type-post","status-publish","format-standard","hentry","category-complexity","category-quantum"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/4447","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=4447"}],"version-history":[{"count":5,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/4447\/revisions"}],"predecessor-version":[{"id":4507,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/4447\/revisions\/4507"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4447"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4447"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4447"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}