Connection between BosonSampling with quantum and classical input states.

ABSTRACT

BosonSampling is a problem of sampling events according to the transition probabilities of indistinguishable photons in a linear optical network. Computational hardness of BosonSampling depends on photon-number statistics of the input light. BosonSampling with multi-photon Fock states at the input is believed to be classically intractable but there exists an efficient classical algorithm for classical input states. In this paper, we present a mathematical connection between BosonSampling with quantum and classical light inputs. Specifically, we show that the generating function of a transition probability for Fock-state BosonSampling (FBS) can be expressed as a transition probability of thermal-light inputs. The closed-form expression of a thermal-light transition probability allows all possible transition probabilities of FBS to be obtained by calculating a single matrix permanent. Moreover, the transition probability of FBS is shown to be expressed as an integral involving a Gaussian function multiplied by a Laguerre polynomial, resulting in a fast oscillating integrand. Our work sheds new light on computational hardness of FBS by identifying the mathematical connection between BosonSampling with quantum and classical light.