We extend classical simulation techniques for noisy boson sampling twice. First, we extend the algorithm to include realistic, non-uniform, partially distinguishable photons. Second, we extend the simulation technique to a particular family of structured matrices.
Abstract Boson sampling is the problem of sampling from the same distribution as indistinguishable single photons at the output of a linear optical interferometer. It is an example of a non-universal quantum computation which is believed to be feasible in the near term and cannot be simulated on a classical machine. Like all purported demonstrations of ‘quantum computational supremacy’, this motivates optimising classical simulation schemes for a realistic model of the problem, in this case boson sampling when the implementations experience lost or distinguishable photons. Although current simulation schemes for sufficiently imperfect boson sampling are classically efficient, in principle the polynomial runtime can be infeasibly large. In this work, we develop a scheme for classical simulation of boson sampling under uniform distinguishability and loss, based on the idea of sampling from distributions where at most k photons are indistinguishable. We show that asymptotically this scheme can provide a polynomial improvement in the runtime compared to classically simulating idealised boson sampling. More significantly, we show that in the regime considered experimentally relevant, our approach gives an substantial improvement in runtime over other classical simulation approaches.
Abstract Boson Sampling is a task that is conjectured to be computationally hard for a classical computer, but which can be efficiently solved by linear-optical interferometers with Fock state inputs. Significant advances have been reported in the last few years, with demonstrations of small- and medium-scale devices, as well as implementations of variants such as Gaussian Boson Sampling. Besides the relevance of this class of computational models in the quest for unambiguous experimental demonstrations of quantum advantage, recent results have also proposed the first applications for hybrid quantum computing. Here, we introduce the adoption of non-linear photon–photon interactions in the Boson Sampling framework, and analyze the enhancement in complexity via an explicit linear-optical simulation scheme. By extending the computational expressivity of Boson Sampling, the introduction of non-linearities promises to disclose novel functionalities for this class of quantum devices. Hence, our results are expected to lead to new applications of near-term, restricted photonic quantum computers.