Geometry Seminar

Date: March 10, 2017

Time: 4:00PM - 5:00PM

Location: BLOC 220 - NOTE

Speaker: Scott Aaronson, UT Austin

Title: Boson Sampling and the Permanents of Gaussian Matrices

Abstract: I'll discuss BosonSampling, a proposal by myself and Alex Arkhipov to demonstrate "quantum supremacy" (that is, an exponential computational speedup over classical computers), using a linear-optical setup that falls far short of being a universal quantum computer. The goal, in BosonSampling, is to sample from a certain kind of probability distribution, in which the probabilities are given by the absolute squares of permanents of complex matrices (n-by-n matrices, if there are n photons involved). Of particular interest to mathematicians is that the BosonSampling program leads naturally to rich mathematical questions---some of which we've answered, but many of which remain open---about the permanent itself. (For example: are permanents of i.i.d. Gaussian matrices close to lognormally distributed? Is there an efficient algorithm to estimate them?) I'll focus mainly on those questions. No quantum computation background is needed for this talk.