If the world ends today, at least it won’t do so without three identical photons having been used to sample from a probability distribution defined in terms of the permanents of 3×3 matrices, thereby demonstrating the Aaronson-Arkhipov BosonSampling protocol. And the results were obtained by no fewer than four independent experimental groups, some of whom have now published in Science. One of the groups is based in Brisbane, Australia, one in Oxford, one in Vienna, and one in Rome; they coordinated to release their results the same day. That’s right, the number of papers (4) that these groups managed to choreograph to appear simultaneously actually exceeds the number of photons that they so managed (3). The Brisbane group was even generous enough to ask me to coauthor: I haven’t been within 10,000 miles of their lab, but I did try to make myself useful to them as a “complexity theory consultant.”
Here are links to the four experimental BosonSampling papers released in the past week:
- Experimental BosonSampling by Broome et al. (Brisbane)
- Experimental Boson Sampling by Tillmann et al. (Vienna)
- Experimental Boson Sampling by Walmsley et al. (Oxford)
- Experimental boson sampling in arbitrary integrated photonic circuits by Crespi et al. (Italy)
For those who want to know the theoretical background to this work:
- My and Alex’s original 100-page BosonSampling paper (to appear soon in the journal Theory of Computing)
- The 10-page STOC’2011 version of our paper
- My PowerPoint slides
- Alex’s slides
- Theoretical Computer Science StackExchange question and answer
- Gil Kalai’s blog post
- Old Shtetl-Optimized post
For those just tuning in, here are some popular-level articles about BosonSampling:
- Larry Hardesty’s MIT News article (from last year)
- University of Queensland press release
- Victorian counting device gets speedy quantum makeover (this week, from New Scientist; the article is not bad except that it ought to credit Alex Arkhipov)
- New Form of Quantum Computation Promises Showdown with Ordinary Computers, by Adrian Cho (from Science)
I’ll be happy to answer further questions in the comments; for now, here’s a brief FAQ:
Q: Why do you need photons in particular for these experiments?
A: What we need is identical bosons, whose transition amplitudes are given by the permanents of matrices. If it were practical to do this experiment with Higgs bosons, they would work too! But photons are more readily available.
Q: But a BosonSampling device isn’t really a “computer,” is it?
A: It depends what you mean by “computer”! If you mean a physical system that you load input into, let evolve according to the laws of physics, then measure to get an answer to a well-defined mathematical problem, then sure, it’s a computer! The only question is whether it’s a useful computer. We don’t believe it can be used as a universal quantum computer—or even, for that matter, as a universal classical computer. More than that, Alex and I weren’t able to show that solving the BosonSampling problem has any practical use for anything. However, we did manage to amass evidence that, despite being useless, the BosonSampling problem is also hard (at least for a classical computer). And for us, the hardness of classical simulation was the entire point.
Q: So, these experiments reported in Science this week have done something that no classical computer could feasibly simulate?
A: No, a classical computer can handle the simulation of 3 photons without much—or really, any—difficulty. This is only a first step: before this, the analogous experiment (called the Hong-Ou-Mandel dip) had only ever been performed with 2 photons, for which there’s not even any difference in complexity between the permanent and the determinant (i.e., between bosons and fermions). However, if you could scale this experiment up to about 30 photons, then it’s likely that the experiment would be solving the BosonSampling problem faster than any existing classical computer (though the latter could eventually solve the problem as well). And if you could scale it up to 100 photons, then you might never even know if your experiment was working correctly, because a classical computer would need such an astronomical amount of time to check the results.