![Quantum Hamiltonian Complexity_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Quantum%20Hamiltonian%20Complexity_hi-res.jpg?h=450de763&itok=M65w-RVO)
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.