Fig. 1. Boson sampling and its corresponding photonic implementation. (a) Conceptual scheme of the boson sampling task. The output probabilities after the scattering process are related to the evaluation of permanents of n×n submatrices of U, obtained by selecting rows and column of the matrix U describing the linear transformation. A classical simulation then requires the evaluation of hard-to-compute matrix permanents. (b) Photonic approach to building a quantum device that solves the boson sampling task. The three main building blocks are: (i) n photon sources for input state generation, (ii) m-mode linear interferometer, composed of beam splitters and phase shifters, implementing the selected unitary transformation U, and (iii) detectors on each of the output modes.

Fig. 2. Variants of the original boson sampling problem. (a) Scattershot boson sampling with multiple SPDC sources connected to the input ports of the interferometer. (b) Driven boson sampling, where layers of heralded sources are included between Haar-random unitaries to inject photons within the evolution. (c) Gaussian boson sampling, with multiple single-mode squeezers connected to the input ports of Haar-random unitaries. (d) Boson sampling with photon-added or photon-subtracted states, with variants also on the type of evolution (Haar-random or orthogonal matrices), and on the type of measurement (parity, on/off or photon-counting detection). (e) Multiboson correlation sampling (MBCS).

Fig. 3. Experimental solutions, reported in the literature, to build photonic boson sampling machines. On the source side: (a) multiphoton generation from a single nonlinear crystal (NLC), (b) several two-photon generation processes to implement the scattershot boson-sampling, (c) integrated on-chip sources, (d) emission from semiconductor quantum dot. The unitary transformation is often implemented in the spatial modes using (e) multiport waveguide circuits composed of network of directional couplers, (f) micro-optic interferometers or (g) devices where several waveguides or fiber cores are continuously coupled. (h) The use of discrete time bins is also reported, exploiting fiber loops. Single photons are detected by (i) avalanche photo-diodes or (j) superconducting-nanowire detectors.

Fig. 4. Validation of boson sampling experiments. A sequence of tests is progressively performed on a data sample to exclude possible alternative scenarios. Experimental demonstrations with different approaches have shown the possibility of discriminating boson sampling data from the uniform distribution, the one obtained with distinguishable particles, and the mean-field sampler.