BosonSampling, which Alex Arkhipov and I proposed in 2011, is a scheme for using identical single photons, sent through a network of beamsplitters, to perform a certain sampling task (involving the matrix permanent function) that’s believed to be intractable for a classical computer. Unlike a universal quantum computer, a BosonSampling device has no known practical applications. However, it might be easier to build, and the evidence that BosonSampling is classically hard actually seems stronger than the evidence that (say) factoring integers is classically hard. For these reasons, a BosonSampling experiment with about 30 photons could be attractive as a proof-of-principle for the central tenet of quantum computing theory: that Nature cannot be efficiently simulated by classical computers.

In 2012, the first BosonSampling experiments involving 3-4 photons were announced, by four independent groups. Unfortunately, scaling up to larger numbers of photons remains a major challenge, because of the unreliability of current single-photon sources, and the exponential falloff with n in the probability of detecting an n-photon coincidence.

In this talk, I’ll give a high-level tour of BosonSampling, focusing on recent progress in bridging the gap between theory and experiment.

Such progress includes results about how to cope with photon losses, and methods for testing the output of a purported BosonSampling device using a classical computer.

References, articles, and blogs:

As far as links, the original BosonSampling paper is at http://theoryofcomputing.org/articles/v009a004/v009a004.pdf

and there’s an MIT News article at
http://web.mit.edu/newsoffice/2011/quantum-experiment-0302.html

and a blog post at
http://www.scottaaronson.com/blog/?p=1177

Scott Aaronson is the TIBCO Career Development Associate Professor of Electrical Engineering and Computer Science at MIT.

Prior to joining MIT, he received his PhD in computer science from UC Berkeley, and did postdocs at the Institute for Advanced Study, Princeton, and the University of Waterloo. His research focuses on the capabilities and limits of quantum computers, and more generally on computational complexity theory and its relationship to physics.

His first book, “Quantum Computing Since Democritus,” was published this year by Cambridge University Press. Aaronson has written about quantum computing for Scientific American and the New York Times, and writes a popular blog. He’s received the National Science Foundation’s Alan T. Waterman Award, the United States PECASE Award, and MIT’s Junior Bose Award for Excellence in Teaching.

Registration is closed.