Boson-Sampling in the light of sample complexity

• DOI: 10.48550/arxiv.1306.3995
• Publication Date: 2013-01-01
• Authors: Christian Gogolin; Martin Kliesch; Leandro Aolita; Jens Eisert
• Keywords: Sample (material)

Boson-Sampling is a classically computationally hard problem that can - in principle be efficiently solved with quantum linear optical networks. Very recently, rush of experimental activity has ignited the aim developing such devices as feasible instances simulators. Even approximate believed to high probability if unitary describing network drawn from Haar measure. In this work we show setup, exponentially close one number bosons, no symmetric algorithm distinguish distribution uniform fewer than many samples. This means two distributions are operationally indistinguishable without detailed priori knowledge. We carefully discuss prospects using knowledge about implemented for devising non-symmetric algorithms could potentially improve upon this. conclude due very fact hard, efficient classical certification seems out reach.