{"id":5868,"date":"2021-10-10T13:13:03","date_gmt":"2021-10-10T18:13:03","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=5868"},"modified":"2021-10-12T08:12:34","modified_gmt":"2021-10-12T13:12:34","slug":"gaussian-bosonsampling-higher-order-correlations-and-spoofing-an-update","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=5868","title":{"rendered":"Gaussian BosonSampling, higher-order correlations, and spoofing: An update"},"content":{"rendered":"\n

In my last post<\/a>, I wrote (among other things) about an ongoing scientific debate between the group of Chaoyang Lu at USTC in China, which over the past year has been doing experiments that seek to demonstrate quantum supremacy via Gaussian BosonSampling; and the group of Sergio Boixo at Google, which had a recent paper<\/a> on a polynomial-time classical algorithm to sample approximately from the same distributions.  I reported the facts as I understood them at the time.  Since then, though, a long call with the Google team gave me a new and different understanding, and I feel duty-bound to share that here.<\/p>\n\n\n\n

A week ago, I considered it obvious that if, using a classical spoofer, you could beat the USTC experiment on a metric like total variation distance from the ideal distribution, then you would\u2019ve completely destroyed USTC\u2019s claim of quantum supremacy.\u00a0 The reason I believed that<\/em>, in turn, is a proposition that I hadn\u2019t given a name but needs one, so let me call it Hypothesis H<\/strong>:<\/p>\n\n\n\n

The only way a classical algorithm to spoof BosonSampling can possibly do well in total variation distance, is by correctly reproducing the high-order correlations (correlations among the occupation numbers of large numbers of modes) \u2014 because that\u2019s where the complexity of BosonSampling lies (if it lies anywhere).<\/p><\/blockquote>\n\n\n\n

Hypothesis H had important downstream consequences.\u00a0 Google\u2019s algorithm, by the Google team\u2019s own admission, does not reproduce the high-order correlations.\u00a0 Furthermore, because of limitations on both samples and classical computation time, Google\u2019s paper calculates the total variation distance from the ideal distribution only on the marginal distribution on roughly 14 out of 144 modes.\u00a0 On that marginal distribution, Google\u2019s algorithm does do better than the experiment in total variation distance.\u00a0 Google presents a claimed extrapolation to the full 144 modes, but eyeballing the graphs, it was far from clear to me what would happen: like, maybe the spoofing algorithm would continue to win, but maybe the experiment would turn around and win; who knows?<\/p>\n\n\n\n

Chaoyang, meanwhile, made a clear prediction that the experiment would turn around and win, because of<\/p>\n\n\n\n

  1. the experiment\u2019s success in reproducing the high-order correlations,<\/li>
  2. the admitted failure of Google\u2019s algorithm in reproducing the high-order correlations, and<\/li>
  3. the seeming impossibility of doing well on BosonSampling without<\/em> reproducing the high-order correlations (Hypothesis H).<\/li><\/ol>\n\n\n\n

    Given everything my experience told me about the central importance of high-order correlations for BosonSampling, I was inclined to agree with Chaoyang.<\/p>\n\n\n\n

    Now for the kicker: it seems that Hypothesis H is false.  A classical spoofer could beat a BosonSampling experiment on total variation distance from the ideal distribution, without even bothering to reproduce the high-order correlations correctly.<\/p>\n\n\n\n

    This is true because of a combination of two facts about the existing noisy BosonSampling experiments.  The first fact is that the contribution from the order-k correlations falls off like 1\/exp(k).  The second fact is that, due to calibration errors and the like, the experiments already show significant deviations from the ideal distribution on the order-1 and order-2 correlations.<\/p>\n\n\n\n

    Put these facts together and what do you find?  Well, suppose your classical spoofing algorithm takes care to get the low-order contributions to the distribution exactly right.  Just for that reason alone, it could already win over a noisy BosonSampling experiment, as judged by benchmarks like total variation distance from the ideal distribution, or for that matter linear cross-entropy.  Yes, the experiment will beat the classical simulation on the higher-order correlations.  But because those higher-order correlations are exponentially attenuated anyway, they won\u2019t be enough to make up the difference.  The experiment\u2019s lack of perfection on the low-order correlations will swamp everything else.<\/p>\n\n\n\n

    Granted, I still don\u2019t know for sure that this is<\/em> what happens \u2014 that depends on whether I believe Sergio or Chaoyang about the extrapolation of the variation distance to the full 144 modes (my own eyeballs having failed to render a verdict!).  But I now see that it\u2019s logically possible, maybe even plausible.<\/p>\n\n\n\n

    So, let\u2019s imagine for the sake of argument that Google\u2019s simulation wins on variation distance, even though the experiment wins on the high-order correlations.  In that case, what would be our verdict: would USTC have achieved quantum supremacy via BosonSampling, or not?<\/p>\n\n\n\n

    It\u2019s clear what each side could say.<\/p>\n\n\n\n

    Google could say: by a metric that Scott Aaronson, the coinventor of BosonSampling, thought was perfectly adequate as late as last week \u2014 namely, total variation distance from the ideal distribution \u2014 we won.  We achieved lower variation distance than USTC\u2019s experiment, and we did it using a fast classical algorithm.  End of discussion.  No moving the goalposts after the fact.<\/p>\n\n\n\n

    Google could even add: BosonSampling is a sampling<\/em> task; it\u2019s right there in the name!  The only purpose of any benchmark \u2014 whether Linear XEB or high-order correlation \u2014 is to give evidence about whether you are or aren\u2019t sampling from a distribution close to the ideal one.  But that means that, if you accept that we are<\/em> doing the latter better than the experiment, then there\u2019s nothing more to argue about.<\/p>\n\n\n\n

    USTC could respond: even if Scott Aaronson is<\/em> the coinventor of BosonSampling, he\u2019s extremely far from an infallible oracle.  In the case at hand, his lack of appreciation for the sources of error in realistic experiments caused him to fixate inappropriately on variation distance as the success criterion.  If you want to see the quantum advantage in our system, you have to deliberately subtract off the low-order correlations and look at the high-order correlations.<\/p>\n\n\n\n

    USTC could add: from the very beginning, the whole point of quantum supremacy experiments was to demonstrate a clear speedup on some<\/em> benchmark \u2014 we never particularly cared which one!\u00a0 That horse is out of the barn as soon as we\u2019re talking about quantum supremacy at all \u2014 something the Google group, which itself reported the first quantum supremacy experiment in Fall 2019, again for a completely artificial benchmark \u2014 knows as well as anyone else.\u00a0 (The Google team even has experience with adjusting benchmarks: when, for example, Pan and Zhang<\/a> pointed out that Linear XEB as originally specified is pretty easy to spoof for random 2D circuits, the most cogent rejoinder was: OK, fine then, add an extra check that the returned samples are sufficiently different from one another, which kills Pan and Zhang’s spoofing strategy.) In that case, then, why isn\u2019t a benchmark tailored to the high-order correlations as good as variation distance or linear cross-entropy or any other benchmark?<\/p>\n\n\n\n

    Both positions are reasonable and have merit \u2014 though I confess to somewhat greater sympathy for the one that appeals to my doofosity rather than my supposed infallibility!<\/p>\n\n\n\n

    OK, but suppose, again for the sake of argument, that we accepted the second position, and we said that USTC gets to declare quantum supremacy as long as its experiment does better than any known classical simulation at reproducing the high-order correlations.  We\u2019d still face the question: does the USTC experiment, in fact, do better on that metric?  It would be awkward if, having won the right to change the rules in its favor, USTC still lost even under the new rules.<\/p>\n\n\n\n

    Sergio tells me that USTC directly reported experimental data only for up to order-7 correlations, and at least individually, the order-7 correlations are easy to reproduce on a laptop (although sampling<\/em> in a way that reproduces the order-7 correlations might still be hard\u2014a point that Chaoyang confirms, and where further research would be great). OK, but USTC also reported that their experiment seems to reproduce up to order-19 correlations. And order-19 correlations, the Google team agrees, are hard to sample consistently with on a classical computer by any currently known algorithm.<\/p>\n\n\n\n

    So then, why don\u2019t we have direct data for the order-19 correlations?  The trouble is simply that it would\u2019ve taken USTC an astronomical amount of computation time.  So instead, they relied on a statistical extrapolation from the observed strength of the lower-order correlations \u2014 there we go again with the extrapolations!  Of course, if we\u2019re going to let Google rest its case on an extrapolation, then maybe it\u2019s only sporting to let USTC do the same.<\/p>\n\n\n\n

    You might wonder: why didn\u2019t we have to worry about any of this stuff with the other<\/em> path to quantum supremacy, the one via random circuit sampling with superconducting qubits?  The reason is that, with random circuit sampling, all the correlations except the highest-order ones are completely trivial \u2014 or, to say it another way, the reduced state of any small number of output qubits is exponentially close to the maximally mixed state.  This is a real difference between BosonSampling and random circuit sampling\u2014and even 5-6 years ago, we knew that this represented an advantage for random circuit sampling, although I now have a deeper appreciation for just how great of an advantage it is.  For it means that, with random circuit sampling, it\u2019s easier to place a \u201csword in the stone\u201d: to say, for example, here<\/em> is the Linear XEB score achieved by the trivial classical algorithm that outputs random bits, and lo, our experiment achieves a higher score, and lo, we challenge anyone to invent a fast classical spoofing method that achieves a similarly high score.<\/p>\n\n\n\n

    With BosonSampling, by contrast, we have various metrics with which to judge performance, but so far, for none of those metrics do we have a plausible hypothesis that says \u201chere’s<\/em> the best that any polynomial-time classical algorithm can possibly hope to do, and it\u2019s completely plausible that even a noisy current or planned BosonSampling experiment can do better than that.\u201d<\/p>\n\n\n\n

    In the end, then, I come back to the exact same three goals I would\u2019ve recommended a week ago for the future of quantum supremacy experiments, but with all of them now even more acutely important than before:<\/p>\n\n\n\n

    1. Experimentally, to increase the fidelity of the devices (with BosonSampling, for example, to observe a larger contribution from the high-order correlations) \u2014 a much more urgent goal, from the standpoint of evading classical spoofing algorithms, than further increasing the dimensionality of the Hilbert space.<\/li>
    2. Theoretically, to design better ways to verify the results of sampling-based quantum supremacy experiments classically \u2014 ideally, even ways that could be applied via polynomial-time tests.<\/li>
    3. For Gaussian BosonSampling in particular, to get a better understanding of the plausible limits of classical spoofing algorithms, and exactly how good a noisy device needs to be before it exceeds those limits.<\/li><\/ol>\n\n\n\n

      Thanks so much to Sergio Boixo and Ben Villalonga for the conversation, and to Chaoyang Lu and Jelmer Renema for comments on this post. Needless to say, any remaining errors are my own.<\/p>\n","protected":false},"excerpt":{"rendered":"

      In my last post, I wrote (among other things) about an ongoing scientific debate between the group of Chaoyang Lu at USTC in China, which over the past year has been doing experiments that seek to demonstrate quantum supremacy via Gaussian BosonSampling; and the group of Sergio Boixo at Google, which had a recent paper […]<\/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_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":true,"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":[5,18,4],"tags":[],"class_list":["post-5868","post","type-post","status-publish","format-standard","hentry","category-complexity","category-embarrassing-myself","category-quantum"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/5868","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=5868"}],"version-history":[{"count":4,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/5868\/revisions"}],"predecessor-version":[{"id":5878,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/5868\/revisions\/5878"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5868"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5868"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5868"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}