“School of Physics”
Back to Papers HomeBack to Papers of School of Physics
Paper IPM / P / 14950  


Abstract:  
Boson sampling is a quantum mechanical task involving Fock basis state preparation and detection and evolution using only linear interactions. A classical algorithm for producing samples from this quantum task cannot be efficient unless the polynomial hierarchy of complexity classes collapses, a situation believed to be highly implausible. We present a method for constructing a device which uses Fock state preparations, linear interactions, and Gaussian continuousvariable measurements for which one can show that exact sampling would be hard for a classical algorithm in the same way as boson sampling. The detection events used from this arrangement do not allow a similar conclusion to be drawn for the classical hardness of approximate sampling. We discuss the details of this result outlining some specific properties required by approximate sampling hardness.
Download TeX format 

back to top 