Abstract
BosonSampling, which Alex Arkhipov and I proposed several years ago, is a rudimentary, non-universal form of linear-optical quantum computing that nevertheless seems to be intractable to simulate using a classical computer. Unfortunately, verifying that a claimed BosonSampling device is working might itself be an intractable computational problem, and BosonSampling has come in for some criticism on that ground. In this talk, after introducing BosonSampling, I will explain recent polynomial-time classical protocols that distinguish a BosonSampling device from several important "null hypotheses." I will also discuss the possibility of an interactive protocol to verify post-classical computational power in a BosonSampling device.