{"id":1579,"date":"2013-11-08T13:19:50","date_gmt":"2013-11-08T18:19:50","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=1579"},"modified":"2017-01-12T14:48:37","modified_gmt":"2017-01-12T19:48:37","slug":"scattershot-bosonsampling-a-new-approach-to-scalable-bosonsampling-experiments","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=1579","title":{"rendered":"Scattershot BosonSampling: A new approach to scalable BosonSampling experiments"},"content":{"rendered":"

Update (12\/2)<\/span><\/b>: Jeremy Hsu has written a fantastic piece for IEEE Spectrum<\/i><\/a>, entitled “D-Wave’s Year of Computing Dangerously.”<\/p>\n

\n

Update (11\/13)<\/span><\/b>: See here<\/a> for video of a fantastic talk that Matthias Troyer gave at Stanford, entitled “Quantum annealing and the D-Wave devices.” The talk includes the results of experiments on the 512-qubit machine. (Thanks to commenter jim for the pointer. I attended the talk when Matthias gave it last week at Harvard, but I don’t think that one was videotaped.)<\/p>\n

\n

Update (11\/11)<\/span><\/b>: A commenter named RaulGPS has offered yet another great observation<\/a> that, while forehead-slappingly obvious in retrospect, somehow hadn’t occurred to us.\u00a0 Namely, Raul points out that the argument given in this post, for the hardness of Scattershot BosonSampling, can also be applied to answer open question #4 from my and Alex’s paper: namely, how hard is BosonSampling with Gaussian inputs and number-resolving detectors?\u00a0 Raul points out that the latter, in general, is certainly at least<\/em> as hard as Scattershot BS.\u00a0 For we can embed Scattershot BS into “ordinary” BS with Gaussian inputs, by first generating a bunch of entangled 2-mode Gaussian states (which are highly attenuated, so that with high probability none<\/em> of them have 2 or more photons per mode), and then applying a Haar-random unitary U to the “right halves” of these Gaussian states while doing nothing to the left halves.\u00a0 Then we can measure the left halves to find out which of the input states contained a photon before<\/em> we applied U.\u00a0 This is precisely equivalent to Scattershot BS, except for the unimportant detail that our measurement of the “herald” photons has been deferred till the end of the experiment instead of happening at the beginning.\u00a0 And therefore, since (as I explain in the post) a fast classical algorithm for approximate Scattershot BosonSampling would let us estimate the permanents of i.i.d. Gaussian matrices in BPPNP<\/sup>, we deduce that a fast classical algorithm for approximate Gaussian<\/em> BosonSampling would have the same consequence.\u00a0 In short, approximate Gaussian BS can be argued to be hard under precisely the same complexity assumption as can approximate ordinary<\/em> BS (and approximate Scattershot BS).\u00a0 Thus, in the table in Section 1.4 of our paper<\/a>, the entries “Gaussian states \/ Adaptive, demolition” and “Gaussian states \/ Adaptive, nondemolition” should be “upgraded” from “Exact sampling hard” to “Apx. sampling hard?”<\/p>\n

One other announcement: following a suggestion by commenter Rahul<\/a>, I hereby invite guest posts on Shtetl-Optimized<\/em> by experimentalists working on BosonSampling, offering your personal views about the prospects and difficulties of scaling up.\u00a0 Send me email if you’re interested.\u00a0 (Or if you don’t feel like writing a full post, of course you can also just leave a comment on this one.)<\/p>\n

\n

[Those impatient for a cool, obvious-in-retrospect new idea about BosonSampling, which I learned from the quantum optics group at Oxford, should scroll to the end of this post.\u00a0 Those who don’t even know what BosonSampling is, let alone Scattershot BosonSampling, should start at the beginning.]<\/em><\/p>\n

BosonSampling is a proposal by me and Alex Arkhipov for a rudimentary kind of quantum computer: one that would be based entirely on generating single photons, sending them through a network of beamsplitters and phaseshifters, and then measuring where they ended up. \u00a0BosonSampling devices are not thought to be capable of universal quantum computing, or even universal classical<\/em> computing for that matter.\u00a0 And while they might be a stepping-stone toward universal optical quantum computers, they themselves have a grand total of zero\u00a0known practical applications. \u00a0However, even if the task performed by BosonSamplers is useless<\/strong><\/span>, the task is of some scientific interest, by virtue of apparently being hard!<\/strong><\/span>\u00a0 In particular, Alex and I showed that, if a BosonSampler can be simulated exactly in polynomial time by a classical computer, then P#P<\/sup>=BPPNP<\/sup>, and hence the polynomial hierarchy collapses to the third level. \u00a0Even if a BosonSampler can only be approximately<\/em> simulated in classical polynomial time, the polynomial hierarchy would still collapse, if a reasonable-looking conjecture in classical complexity theory is true.\u00a0 For these reasons, BosonSampling might<\/em> provide an experimental path to testing the Extended Church-Turing Thesis<\/a>—i.e., the thesis that all natural processes can be simulated with polynomial overhead by a classical computer—that’s more “direct” than building a universal quantum computer.\u00a0 (As an asymptotic claim, obviously<\/em> the ECT can never be decisively proved or refuted by a finite number of experiments.\u00a0 However, if one could build a BosonSampler with, let’s say, 30 photons, then while it would still be feasible to verify the results with a classical computer, it would be fair to say that the BosonSampler was working “faster” than any known algorithm running on existing digital computers.)<\/p>\n

In arguing for the hardness of BosonSampling, the crucial fact Alex and I exploited is that the amplitudes for n-photon processes are given by the permanents<\/em><\/a> of nxn matrices of complex numbers, and Leslie Valiant proved in 1979 that the permanent is #P-complete<\/a> (i.e., as hard as any combinatorial counting problem, and probably even “harder” than NP-complete).\u00a0 To clarify, this doesn’t mean that a BosonSampler lets you calculate<\/em> the permanent of a given matrix—that would be too good to be true!\u00a0 (See the tagline of this blog.)\u00a0 What you could do with a BosonSampler is weirder: you could sample from a probability distribution over matrices, in which matrices with large permanents are more likely to show up than matrices with small permanents.\u00a0 So, what Alex and I had to do was to argue that even that sampling task is still<\/em> probably intractable classically—in the sense that, if it weren’t, then there would also be unlikely classical algorithms for more “conventional” problems.<\/p>\n

Anyway, that’s my attempt at a 2-paragraph summary of something we’ve been thinking about on and off for four years. \u00a0See here<\/a> for my and Alex’s original paper on BosonSampling, here<\/a> for a recent followup paper, here<\/a> for PowerPoint slides, here<\/a>\u00a0and here<\/a> for MIT News articles by Larry Hardesty, and here<\/a> for my blog post about the first (very small, 3- or 4-photon) demonstrations of BosonSampling by quantum optics groups last year, with links to the four experimental papers that came out then.<\/p>\n

In general, we’ve been thrilled by the enthusiastic reaction to BosonSampling by quantum optics people—especially given that the idea started out as pure complexity theory, with the connection to optics coming as an “unexpected bonus.”\u00a0 But not surprisingly, BosonSampling has also come in for its share of criticism: e.g., that it’s impractical, unscalable, trivial, useless, oversold, impossible to verify, and probably some other things. \u00a0A few people have even claimed that, in expressing support and cautious optimism about the recent BosonSampling experiments, I’m guilty of the same sort of quantum computing hype that I complain about in others. \u00a0(I’ll let you be the judge of that. \u00a0Reread the paragraphs above, or anything else I’ve ever written about this topic, and then compare to, let’s say,\u00a0this video<\/a>.)<\/p>\n

By far the most<\/em> important criticism of BosonSampling—one that Alex and I have openly acknowledged and worried a lot about almost from the beginning—concerns the proposal’s scalability<\/em>.\u00a0 The basic problem is this: in BosonSampling, your goal is to measure a pattern of quantum interference among n identical, non-interacting photons, where n is as large as possible.\u00a0 (The special case n=2 is called the Hong-Ou-Mandel dip<\/a>; conversely, BosonSampling can be seen as just “Hong-Ou-Mandel on steroids.”)\u00a0 The bigger n gets, the harder the experiment ought to be to simulate using a classical computer (with the difficulty increasing at least like ~2n<\/sup>).\u00a0 The trouble is that, to detect interference among n photons, the various quantum-mechanical paths that your photons could take, from the sources, through the beamsplitter network, and finally to the detectors, have to get them there at exactly the same time<\/em>—or at any rate, close enough to “the same time” that the wavepackets overlap.\u00a0 Yet, while that ought to be possible in theory, the photon sources that actually exist today, and that will<\/em> exist for the foreseeable future, just don’t seem good enough to make it happen, for anything more than a few photons.<\/p>\n

The reason—well-known for decades as a bane to quantum information experiments—is that there’s no known process in nature that can serve as a deterministic single-photon source<\/em>.\u00a0 What you get from an attenuated laser is what’s called a coherent state<\/a>: a particular kind of superposition of 0 photons, 1 photon, 2 photons, 3 photons, etc., rather than just 1 photon with certainty (the latter is called a Fock state<\/a>).\u00a0 Alas, coherent states behave essentially like classical light, which makes them pretty much useless for BosonSampling, and for many other quantum information tasks besides.\u00a0 For that reason, a large fraction of modern quantum optics research relies on a process called Spontaneous Parametric Down-Conversion (SPDC)<\/a>.\u00a0 In SPDC, a laser (called the “pump”) is used to stimulate a crystal to produce further photons.\u00a0 The process is inefficient: most of the time, no photon comes out.\u00a0 But crucially, any time a photon does<\/em> come out, its arrival is “heralded” by a partner photon flying out in the opposite direction.\u00a0 Once in a while, 2 photons come out simultaneously, in which case they’re heralded by 2 partner photons—and even more rarely, 3 photons come out, heralded by 3 partner photons, and so on.\u00a0 Furthermore, there exists something called a number-resolving detector<\/em>, which can tell you (today, sometimes, with as good as ~95% reliability) when one or more partner photons have arrived, and how many of them there are.\u00a0 The result is that SPDC lets us build what’s called a nondeterministic single-photon source<\/em>.\u00a0 I.e., you can’t control exactly when a photon comes out—that’s random—but eventually one (and only one) photon will<\/em> come out, and when that happens, you’ll know<\/em> it happened, without even having to measure and destroy the precious photon.\u00a0 The reason you’ll know is that the partner photon heralds its presence.<\/p>\n

Alas, while SPDC sources have enabled demonstrations of a large number of cool quantum effects, there’s a fundamental problem with using them for BosonSampling.\u00a0 The problem comes from the requirement that n—the number of single photons fired off simultaneously into your beamsplitter network—should be big<\/em> (say, 20 or 30).\u00a0 Suppose that, in a given instant, the probability that your SPDC source succeeds in generating a photon is p.\u00a0 Then what’s the probability that two<\/em> SPDC sources will both<\/em> succeed in generating a photon at that instant?\u00a0 p2<\/sup>.\u00a0 And the probability that three sources will succeed is p3<\/sup>, etc.\u00a0 In general, with n sources, the probability that they’ll succeed simultaneously falls off exponentially with n, and the amount of time you’ll need to sit in the lab waiting for the lucky event increases<\/em> exponentially with n.\u00a0 Sure, when it finally does<\/em> happen, it will be “heralded.”\u00a0 But if you need to wait exponential time for it to happen, then there would seem to be no advantage over classical computation.\u00a0 This is the reason why so far, BosonSampling has only been demonstrated with 3-4 photons.<\/p>\n

At least three solutions to the scaling problem suggest themselves, but each one has problems of its own.\u00a0 The first solution is simply to use general methods for quantum fault-tolerance: it’s not hard to see that, if you had a fault-tolerant universal quantum computer, then you could simulate BosonSampling with as many photons as you wanted.\u00a0 The trouble is that this requires a fault-tolerant universal quantum computer!\u00a0 And if you had that, then you’d probably just skip BosonSampling and use Shor’s algorithm to factor some 10,000-digit numbers.\u00a0 The second solution is to invent some specialized fault-tolerance method that would apply directly to quantum optics.\u00a0 Unfortunately, we don’t know how to do that.\u00a0 The third solution—until recently, the one that interested me and Alex the most—would be to argue that, even if your sources are so cruddy that you have no idea which ones generated a photon and which didn’t in any particular run, the BosonSampling distribution is still<\/em> intractable to simulate classically.\u00a0 After all, the great advantage of BosonSampling is that, unlike with (say) factoring or quantum simulation, we don’t actually care which problem we’re solving!\u00a0 All we care about is that we’re doing something<\/em> that we can argue is hard for classical computers.\u00a0 And we have enormous leeway to change what that “something” is, to match the capabilities of current technology.\u00a0 Alas, yet again, we don’t<\/em> know how to argue that BosonSampling is hard to simulate approximately in the presence of realistic amounts of noise—at best, we can argue that it’s hard to simulate approximately in the presence of tiny<\/em> amounts of noise, and hard to simulate super<\/em>-accurately in the presence of realistic noise.<\/p>\n

When faced with these problems, until recently, all we could do was<\/p>\n

    \n
  1. shrug our shoulders,<\/li>\n
  2. point out that none of the difficulties added up to a principled argument that scalable BosonSampling was not<\/em> possible,<\/li>\n
  3. stress, again, that all we were asking for was to scale to 20 or 30 photons, not 100 or 1000 photons, and<\/li>\n
  4. express hope that technologies for single-photon generation currently on the drawing board—most notably, something called “optical multiplexing”—could be used to get up to the 20 or 30 photons we wanted.<\/li>\n<\/ol>\n

    Well, I’m pleased to announce, with this post, that there’s now a better idea for how to scale BosonSampling to interesting numbers of photons.\u00a0 The idea, which I’ve taken to calling Scattershot BosonSampling<\/strong>, is not mine or Alex’s.\u00a0 I learned of it from Ian Walmsley’s group at Oxford, where it’s been championed in particular by Steve Kolthammer<\/a>.\u00a0 (Update:<\/strong><\/span> A commenter has pointed me to a preprint<\/a> by Lund, Rahimi-Keshari, and Ralph from May of this year, which I hadn’t seen before, and which contains substantially the same idea, albeit with an unsatisfactory argument for computational hardness.\u00a0 In any case, as you’ll see, it’s not surprising that this idea would’ve occurred to multiple groups of experimentalists independently; what’s surprising is that we didn’t think of it!<\/em>)\u00a0 The minute I heard about Scattershot BS, I kicked myself for failing to think of it, and for getting sidetracked by much more complicated ideas.\u00a0 Steve and others are working on a paper about Scattershot BS, but in the meantime, Steve has generously given me permission to share the idea on this blog.\u00a0 I suggested a blog post for two reasons: first, as you’ll see, this idea really is “blog-sized.”\u00a0 Once you make the observation, there’s barely any theoretical analysis that needs to be done!\u00a0 And second, I was impatient to get out to the “experimental BosonSampling community”—not to mention to the critics!—that there’s now a better way to BosonSample, and one that’s incredibly simple to boot.<\/p>\n

    OK, so what is<\/em> the idea?\u00a0 Well, recall from above what an SPDC source does: it produces a photon with only a small probability, but whenever it does, it “heralds” the event with a second photon.\u00a0 So, let’s imagine that you have an array of 200 SPDC sources.\u00a0 And imagine that, these sources being unpredictable, only (say) 10 of them, on average, produce a photon at any given time.\u00a0 Then what can you do?\u00a0 Simple: just define<\/em> those 10 sources to be the inputs to your experiment!\u00a0 Or to say it more carefully: instead of sampling only from a probability distribution over output<\/em> configurations of your n photons, now you’ll sample from a joint distribution over inputs and<\/em> outputs: one where the input is uniformly random, and the output depends on the input (and also, of course, on the beamsplitter network).\u00a0 So, this idea could also be called “Double BosonSampling”: now, not only do you not control which output will be observed (but only the probability distribution over outputs), you don’t control which input either—yet this lack of control is not a problem!\u00a0 There are two key reasons why it isn’t:<\/p>\n

      \n
    1. As I said before, SPDC sources have the crucial property that they herald<\/em> a photon when they produce one.\u00a0 So, even though you can’t control which 10 or so of your 200 SPDC sources will produce a photon in any given run, you know<\/em> which 10 they were.<\/li>\n
    2. In my and Alex’s original paper, the “hardest” case of BosonSampling that we were able to find—the case we used for our hardness reductions—is simply the one where the mxn “scattering matrix,” which describes the map between the n input modes and the m>>n output modes, is a Haar-random matrix whose columns are orthonormal vectors.\u00a0 But now suppose we have m input modes and<\/em> m output modes, and the mxm unitary matrix U mapping inputs to outputs is Haar-random.\u00a0 Then any mxn submatrix of U will simply be an instance of the “original” hard case that Alex and I studied!<\/li>\n<\/ol>\n

      More formally, what can we\u00a0 say about the computational complexity of Scattershot BS?\u00a0 Admittedly, I don’t know of a reduction from ordinary BS to Scattershot BS (though it’s easy to give a reduction in the other direction).\u00a0 However, under exactly the same assumption that Alex and I used to argue that ordinary BosonSampling was hard—our so-called Permanent of Gaussians Conjecture (PGC)—one can show that Scattershot BS is hard also, and by essentially the same proof.\u00a0 The only difference is that, instead of talking about the permanents of nxn submatrices of an mxn Haar-random, column-orthonormal matrix, now we talk about the permanents of nxn submatrices of an mxm Haar-random unitary matrix.\u00a0 Or to put it differently: where before we fixed the columns that defined our nxn submatrix and only varied the rows, now we vary both the rows and<\/em> the columns.\u00a0 But the resulting nxn submatrix is still close in variation distance to a matrix of i.i.d. Gaussians, for exactly the same reasons it was before.\u00a0 And we can still check whether submatrices with large permanents are more likely to be sampled than submatrices with small permanents, in the way predicted by quantum mechanics.<\/p>\n

      Now, everything above assumed that each SPDC source produces either 0 or 1 photon.\u00a0 But what happens when the SPDC sources produce 2 or more photons, as they sometimes do?\u00a0 It turns out that there are two good ways to deal with these “higher-order terms” in the context of Scattershot BS. \u00a0The first way is by using number-resolving detectors to count how many herald photons each SPDC source produces. \u00a0That way, at least you’ll know<\/em>\u00a0exactly which sources produced extra photons, and how many extra photons each one produced. \u00a0And, as is often the case in BosonSampling, a devil you know is a devil you can deal with. \u00a0In particular, a few known sources producing extra photons, just means that the amplitudes of the output configurations will now be permanents of matrices with a few repeated rows in them. \u00a0But the permanent of an otherwise-random matrix with a few repeated rows should still<\/em> be hard to compute! \u00a0Granted, we don’t know how to derive that as a consequence of our original hardness assumption, but this seems like a case where one is perfectly justified to stick one’s neck out and make a new assumption.<\/p>\n

      But there’s also a more elegant way to deal with higher-order terms. \u00a0Namely, suppose m>>n2<\/sup> (i.e., the number of input modes is at least quadratically greater than the average number of photons). \u00a0That’s an assumption that Alex and I typically made anyway<\/em> in our original BosonSampling paper, because of our desire to avoid what we called the “Bosonic Birthday Paradox” (i.e., the situation where two or more photons congregate in the same output mode). \u00a0What’s wonderful is that exactly the same<\/em> assumption also implies that, in Scattershot BS, two or more photons will almost never be found in the same input<\/em> mode! \u00a0That is, when you do the calculation, you find that, once you’ve attenuated your SPDC sources enough to avoid the Bosonic Birthday Paradox at the output modes, you’ve also<\/em> attenuated them enough to avoid higher-order terms at the input modes. \u00a0Cool, huh?<\/p>\n

      Are there any drawbacks<\/em> to Scattershot BS?\u00a0 Well, Scattershot BS certainly requires more SPDC sources than ordinary BosonSampling does, for the same average number of photons.\u00a0 A little less obviously, Scattershot BS also requires a larger-depth beamsplitter network.\u00a0 In our original paper, Alex and I showed that for ordinary BosonSampling, it suffices to use a beamsplitter network of depth O(n log m), where n is the number of photons and m is the number of output modes (or equivalently detectors). \u00a0However, our construction took advantage of the fact that we knew<\/em> exactly which n<<m sources the photons were going to come from, and could therefore optimize for those. \u00a0For Scattershot BS, the depth bound increases to O(m log m): since the n photons could come from any possible subset of the m input modes, we no longer get the savings based on knowing where they originate. \u00a0But this seems like a relatively minor issue.<\/p>\n

      I don’t want to give the impression that Scattershot BS is a silver bullet that will immediately let us BosonSample with 30 photons.\u00a0 The most obvious limiting factor that remains is the efficiency of the photon detectors<\/em>—both those used to detect the photons that have passed through the beamsplitter network, and those used to detect the herald photons. \u00a0Because of detector inefficiencies, I’m told that, without further technological improvements (or theoretical ideas), it will still be quite hard to push Scattershot BS beyond about 10 photons. \u00a0Still, as you might have noticed, 10 is greater than 4 (the current record)! \u00a0And certainly, Scattershot BS itself—a simple, obvious-in-retrospect idea that was under our noses for years, and that immediately pushes forward the number of photons a BosonSampler can handle—should make us exceedingly reluctant to declare there can’t be any more<\/em> such ideas, and that our current ignorance amounts to a proof of impossibility.<\/p>\n","protected":false},"excerpt":{"rendered":"

      Update (12\/2): Jeremy Hsu has written a fantastic piece for IEEE Spectrum, entitled “D-Wave’s Year of Computing Dangerously.” Update (11\/13): See here for video of a fantastic talk that Matthias Troyer gave at Stanford, entitled “Quantum annealing and the D-Wave devices.” The talk includes the results of experiments on the 512-qubit machine. (Thanks to commenter […]<\/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_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":[5,4],"tags":[],"class_list":["post-1579","post","type-post","status-publish","format-standard","hentry","category-complexity","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\/1579","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=1579"}],"version-history":[{"count":15,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1579\/revisions"}],"predecessor-version":[{"id":1605,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1579\/revisions\/1605"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1579"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1579"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1579"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}