Abstract

Boson Sampling [1] is a specialized task which consists in sampling from the output distribution of a system of non-interacting bosons evolving through a linear unitary transformation. It is believed that simulating Boson Sampling experiments (even approximately) is computationally hard for classical computers, since it requires the calculation of permanents of square matrices. This task represents a promising approach to show the computational capabilities of quantum mechanics in systems of smaller size than a large-scale universal quantum computer, which is far from being implementable with present-day technology. This task is naturally solved by photons evolving through a linear optical interferometers and coincidence detection at the output. The recent progresses in photonics technology have led to the first experimental implementations of Boson Sampling experiments in small-scale systems [2-5], and to an experimental study of bunching phenomena in multi-photon interferometers. At variance with other computational tasks, such as factoring of large integer numbers, due to its very complexity there is no-trivial way to certify the correct operation of a medium-scale Boson Sampling device [7-10]. Hence it is crucial to identify suitable strategies to correctly discriminate Boson Sampling events from data sampled from other alternative distributions. Several approaches have been proposed [8] and tested experimentally [9-10].

© 2015 IEEE