1.

Introduction

In recent years, much work has been directed to the development of suitable technologies for scalable quantum computation. This effort is motivated by the promise of quantum algorithmic speed-up, with a notable early example provided by Shor’s algorithm for integer factoring.¹ Despite the tremendous advances in quantum technologies^2–7 reported in the last few years, the implementation of a large-scale universal quantum computer is still far from our current capabilities. Hence, intermediate milestones need to be identified in the long-term effort toward harnessing the computational potential of quantum systems. A first fundamental step in this direction would be the achievement of the regime of quantum computational supremacy,⁸ i.e., the experimental demonstration of a quantum device capable of performing a computational task unambiguously faster than present-day classical computers.

Within this framework, Aaronson and Arkhipov (AA)⁹ formulated a well-defined computational problem that they called boson sampling. This problem consists in sampling from the output distribution of $n$ indistinguishable bosons that interfere during the evolution through a Haar-random-chosen linear network. In Ref. 9, strong evidence was provided that boson sampling is an intractable problem for classical computers, as it is related to the evaluation of permanents of matrices with complex entries (a problem known, in computational complexity terms, to belong to the #P-hard class¹⁰). On the other hand, boson sampling can be tackled with a dedicated quantum hardware, which, despite not being universal for quantum computation, is capable of implementing the required dynamics. To this end, one of the most suitable platforms is provided by photonic systems, as the necessary elements (sources, linear evolution, and detection) are available with present technology.² Given the lack of error-correction—an issue shared by all current proposals for quantum computational supremacy⁸—it is an open question whether current technology is capable of scaling boson sampling to arbitrarily large sizes while maintaining a quantum advantage, which has also motivated research in more robust variants of the model.^11–17 Following these theoretical developments, a strong experimental effort was then initiated to realize progressively larger instances of boson sampling experiments. This is leading to a race aimed at reaching the quantum advantage¹⁸ regime in a photonic platform, namely the condition where the experiment is outperforming a classical computer. In parallel, theoretical work was required to define suitable methods to verify that a given device is sampling from the correct distribution.¹⁹ This is indeed a relevant issue since the very complexity of the problem forbids the application of usual verification methods, and classical simulations become progressively intractable for the increasing system size.

In this paper, we discuss recent advances in the field of photonic boson sampling, with particular attention to experimental implementations and validation methods. The remainder of this paper is organized as follows. In Sec. 2, we first provide a theoretical overview on the problem, discussing the computational model, classical simulation algorithms, and conditions that turn the system amenable to efficient classical simulation. Then in Sec. 3, we discuss variants of the original task that have been proposed to improve the efficiency of the quantum simulator, without affecting the problem’s complexity. In Sec. 4, we review the experimental implementations reported so far, discussing the employed photonic platforms. In Sec. 5, we provide an overview of the validation techniques for boson sampling that have been proposed and tested experimentally. In Sec. 6, we then discuss the scalability of photonic platforms toward achieving the quantum supremacy regime. Finally, we provide an outlook in Sec. 7, where we also discuss recently highlighted applications of boson sampling in contexts different from the original proposal.

2.

Boson Sampling: Theoretical Overview

In this section, we review the theoretical underpinnings of the boson sampling problem. In Sec. 2.1, we define the problem and discuss its computational complexity. In Sec. 2.2, we review the known classical simulation algorithms, and in Sec. 2.3 we discuss some regimes, in which the classical simulation of boson sampling is known to become tractable.

2.1.

Model

Consider a set of $m$ modes with associated creation operators $a_i^{†}$, for $i=1,\dots ,m$, satisfying bosonic commutation relations. A Fock state of $n$ photons in these modes can be written as

Eq. (1)

$$|S⟩=|s_1{s}_2\dots s_m⟩=\prod _{i=1}^m\frac{{(a_i^{†})}^{s_i}}{s_i!}|0⟩,$$

where $s_i$ are the non-negative integers that count the number of photons in each mode and $\sum s_i=n$. When $s_i\le 1$ for all $i$, the state is a no-collision state, meaning that there is no individual mode containing two or more photons.

Consider now an $m$-mode linear-optical transformation (i.e., an interferometer) described by $U\in SU(m)$. Its action is fully determined by the evolution of the creation operators:

Eq. (2)

$$a_i^{†}\to \sum _{j=1}^m{U}_{ij}{a}_j^{†}.$$

It follows^9,20,21,22 that the transition probability between an input state $|S⟩=|s_1{s}_2\dots s_m⟩$ and an output state $|T⟩=|t_1{t}_2\dots t_m⟩$ can be written as

Eq. (3)

$$\mathrm{Pr}[S\to T]=\frac{{|\mathrm{Per}(U_{S,T})|}^2}{s_1!\dots s_m!t_1!\dots t_m!},$$

where $U_{S,T}$ is an $n\times n$ submatrix of $U$ constructed by taking $t_i$ copies of the $i$’th row of $U$ and $s_j$ copies of its $j$’th column,⁹ and

Eq. (4)

$$\mathrm{Per}(B)=\sum _{\sigma \in S_n}\prod _{i=1}^n{b}_{i,\sigma (i)}$$

is the permanent¹⁰ of matrix $B$, and $S_n$ is the symmetric group.

Since the permanent is, in general, hard to compute,¹⁰ Eq. (3) underpins the complexity of a particular class of linear optical experiments. In complexity theory terms, the permanent is #P-hard,¹⁰ and the best known classical algorithm for computing it, due to Ryser, takes $O(n{2}^n)$ steps for an $n\times n$ matrix. The connection to complexity theory was noted by Troyansky and Tishby²¹ who attempted to leverage Eq. (3) to build a quantum-mechanical algorithm to compute permanents. They realized that their algorithm was not efficient, as exponentially many experimental samples would be needed to produce a sufficiently good approximation. AA explored this connection further by shifting to sampling problems, where the computational task is to produce a sample from some probability distribution sufficiently close to the ideal one.⁹ We now outline the argument of AA, emphasizing the requirements it raises for experimental demonstrations of boson sampling. Further developments that attempted to soften the initial requirements are reviewed in Sec. 3.

The standard boson sampling setup⁹ consists of the following ingredients (see Fig. 1).

• (i) Preparation of a $n$-photon, $m$-mode input state, with each mode containing either zero or one photon. Without loss of generality, we can choose an input state with a single photon in each of the first $n$ modes. Having more photons per input mode means choosing repeated columns in the submatrix of Eq. (3), which is likely to make the permanent easier to compute (in the situation where all photons are input in the same mode, the computation becomes trivial).

• (ii) An $m$-mode interferometer described by an $m$-dimensional Haar-random unitary operator $U$, where $m=O(n^2)$. An arbitrary interferometer can be built as a circuit with $O(m^2)$ two-mode elements and depth $O(m)$.^23,24 Since only some input modes are occupied, it is possible to reduce this further to a circuit of $O(mn)$ elements and depth $O(n\log m)$.⁹ The randomness of $U$ has two main purposes. The first is so $U$ does not have any special structure that a classical simulation algorithm could exploit. The second is that, for Haar-random unitaries in $O(n^2)$ modes, the outcomes are dominated by no-collision events due to the bosonic birthday paradox.^9,25

• (iii) Photon detectors on every output. Given (ii), it suffices for them to be bucket detectors, i.e., to only distinguish between vacuum and nonvacuum states.

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\times 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.

Let $\mathcal{D}$ be the probability distribution predicted by quantum mechanics for the no-collision outcomes of such an experiment, and let $\Vert ·\Vert$ represent the total variation distance (TVD).⁹ The main result of AA states (up to two additional complexity-theoretic conjectures) that, if a classical algorithm existed that could produce a sample from any distribution ${\mathcal{D}}^{\prime }$ such that

Eq. (5)

$$\Vert \mathcal{D}-{\mathcal{D}}^{\prime }\Vert <ϵ,$$

in time $\mathrm{poly}(n,1/ϵ)$, the polynomial hierarchy (PH) would collapse to the third level. Since PH is a tower of complexity classes that is strongly believed to be infinite, the result of AA provides strong evidence against the possibility of an efficient classical simulation of boson sampling.

The proposal of AA uses an approximate notion of simulation, as seen in Eq. (5). Thus one could attempt a classical simulation using an algorithm for approximating the permanent, rather than Ryser’s exact algorithm. The problem with this approach is that it can be shown that the permanent would also be #P-hard to approximate on the worst case⁹ to the required precision. One classical algorithm to approximate the permanent is due to Gurvits.²⁶ It takes time $O(n^2/{ϵ}^2)$ to compute the permanents of the $n\times n$ matrices in a boson sampling distribution to precision $ϵ$. This is not sufficient to give a simulation of boson sampling because there we typically have exponentially many permanents that are exponentially small, and so approximating them to a nontrivial precision via this algorithm would take exponential time.

In very broad strokes, the argument of AA is as follows. If $U$ is a Haar-random matrix and $m=O(n^2)$, it can be proven that $n\times n$ submatrices of $U$ look approximately Gaussian. Since Gaussian matrices do not seem to possess any special structure that a classical algorithm could exploit, it is reasonable to conjecture that, with high probability, the permanent of a Gaussian matrix is among the hardest ones to compute (this is the permanent-of-Gaussians conjecture). However, if a classical algorithm could sample from a distribution $ϵ$-close in TVD to the ideal one, it would have to be approximating most probabilities very well. Using an algorithm attributable to Stockmeyer,²⁷ it would then be possible to solve a #P-hard problem inside BPP^NP, which is a complexity class that resides inside the third level of the PH. Using a theorem due to Toda,²⁸ this would imply that the entire hierarchy would have to collapse to its third level. This result, thus, establishes that boson sampling is hard to simulate, even in an approximate sense, up to three conjectures that: (i) PH is infinite, (ii) permanents of Gaussian matrices are #P-hard to approximate, and (iii) permanents of Gaussian matrices are not too concentrated around zero. The third conjecture is more technical but is necessary to relate two versions of the problem of approximating permanents of Gaussian matrices: to within additive and multiplicative errors.

3.

Variants of Boson Sampling

After the initial boson sampling proposal by AA, other variants of the problem were proposed.^11,13–17 These variants include the use of variable input modes, as opposed to a fixed set of input modes; the use of different input quantum states and detectors different from single-photon bucket detectors. In this section, we review some variants of the boson sampling problem (see Fig. 2).

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).

4.

Experimental Boson Sampling

To perform a standard boson sampling experiment with photons, one needs the following three building blocks: single-photon sources, unitary transformations (representing possible linear interferometers), and single-photon detectors. In Fig. 3, we summarize the technical solutions adopted in the experimental demonstrations of boson sampling so far. A list of the experiments reported in the literature is provided in Table 1, where the main features of the three building blocks are also detailed.

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.

Table 1

Relevant details of the main photonic boson sampling experiments reported in the literature. Note: n is the maximum number of detected photons in the boson sampling experiment after unitary evolution; m is the number of available optical modes. SBS, scattershot boson sampling; GBS, Gaussian boson sampling.

While diverse in the experimental details, the first demonstrations of boson sampling^{63–67,69,76} share the main features of their experimental platforms. In particular, in all these experiments, several identical photons are generated by SPDC in nonlinear crystals [Fig. 3(a)], they undergo a unitary transformation in a guided-wave architecture [Figs. 3(e) and 3(g)], and they are finally detected by silicon single-photon avalanche photodiodes (SPADs) [Fig. 3(i)].

In order to produce more than two identical photons, the pump intensity of the SPDC process is increased so that the probability of simultaneous generation of two or more pairs becomes significant. If the different pairs of photons are collected on distinct spatial or polarization modes, the photons can easily be directed to separate input ports of the linear optical circuit. However, emission of multiple pairs is exponentially less efficient than the generation of a single pair. In fact, in the mentioned experiments, at most four identical photons were generated on different modes, pumping one^{63,65,66,69,76} or two^64,67 distinct nonlinear crystals. In addition, it should be noted that in this process the emission of two pairs on the same two modes (an outcome that is not desired) has the same probability of the emission of two pairs on four distinct modes. The correct event is identified by employing one of the four output photons as trigger while only the remaining three are injected in the interferometer, and postselection is operated on the overall detection of four photons. This is a relevant aspect since multiple emissions of photons on the same mode must be avoided in boson sampling experiments. In this case, transition amplitudes are related to matrix permanents with repeated rows that can be easier to compute. As a result, all these first experiments report at most three-photon genuine-boson-sampling instances. In Ref. 67, the output distribution of four photons on different modes is reconstructed a posteriori from a probabilistic input.

The implementation of the unitary transformation was done with a guided-wave architecture, which enables one to cascade interferometers with compactness and stability impossible to achieve by a conventional bulk-optics approach. While boson sampling experiments have been reported also making use of fiber splitters^63,70 or arrays of parallel and continuously coupled waveguides⁶⁷ [Fig. 3(g)], the most common layout employs an integrated network of directional couplers (the integrated version of the bulk beam splitter) and phase shifters. Indeed, by arranging such discrete elements in a triangular^23,66,69 or rectangular²⁴ layout, with judiciously chosen values of the reflectivities and phase shifts, it is possible to realize any arbitrary linear transformation of the optical modes. In Ref. 77, it was also shown how to construct an operational approach to directly implement Haar-random matrices from appropriate distributions for the optical components. One should note that the capability of producing arbitrary transformations is definitely needed to extract and implement Haar-random unitaries, and thus it is essential for the demonstration of a real quantum advantage in a boson sampling experiment.

Up to now, the realization of arbitrarily chosen transformations by the mentioned triangular-network approach has been experimentally reported in femtosecond laser written⁶⁶ or silica-on-silicon⁶⁹ waveguide circuits. The femtosecond laser writing technology⁷⁸ gives the unique possibility to realize three-dimensional (3-D) waveguide circuits;⁷⁹ the third dimension was exploited in Ref. 66 to deform the waveguide paths out of the plane and thus independently adjust phases and reflectivities within the interferometer. In particular, such an innovative design enabled the realization of an arbitrarily chosen five-mode transformation [Fig. 3(e)]. More recently, a six-mode interferometer with full reconfiguration capabilities was demonstrated in Ref. 69, using state-of-art silica-on-silicon lithographic technology. The authors developed an integrated interferometer provided with 30 electronically controlled thermo-optic phase shifters, which allow the dynamical tuning of the circuit to obtain any six-mode linear interferometer. In that device, the individual splitting elements in the triangular network are replaced by Mach–Zehnder interferometers: in this way, it is possible to control the equivalent directional coupler’s reflectivity by acting on the internal phase of the Mach–Zehnder.

As a matter of fact, all the experiments discussed above suffer from a few common and very relevant limitations, which hamper an effective scaling of photonic boson sampling up to the level of a provable quantum advantage over current classical computers. As a first point, the SPDC generation scheme presented above hardly allows the scaling of the number of input photons beyond the small numbers already demonstrated.

One possible experimental route to achieve multiphoton input states with higher efficiency while still relying on nonlinear frequency conversion, is the scattershot approach [Fig. 3(b)], whose theory was discussed in Sec. 3.1. An experimental demonstration of this method was given in Ref. 68. There, six sources of down-converted photon pairs (implemented using three distinct BBO crystals) operate in parallel in order to inject three-photon states into integrated interferometers with up to 13 modes. One of the sources feeds a photon pair to a fixed couple of inputs. The other five sources produce random, but heralded, single photons that are coupled to other input ports of the interferometer. Detection of three photons at the output, in coincidence with one heralding event, postselects the occurrence of a proper input state with three photons in separate modes. This technique enabled a 4.5-times enhanced generation rate of three-photon states with respect to the multipair SPDC scheme adopted previously. In a recent paper,⁷⁴ the scattershot approach has been scaled up to 12 sources, located in six nonlinear crystals. Each of the crystals can emit probabilistically up to two heralded photons with horizontal and/or vertical polarization, multiplexed in the same spatial mode. The sources were then connected to the input ports of an interferometer consisting of six spatial modes. By considering the polarization degree of freedom, this experimental scheme implemented a 12-mode transformation composed by two $6\times 6$ unitary-independent blocks. This led to the observation of three, four, and five-photon events thanks to the increased signal rate provided by the scattershot approach. The measured event rates were, respectively, 3.9 kHz, 44 Hz, and 0.3 Hz. When trying to scale up the number of sources, a bulk implementation of SPDC will eventually reach a limit size, whereas a more promising platform for larger experiments can be provided by the adoption of arrays of integrated sources^80–83 and multiplexing.⁸⁴ Demonstrations of arrayed integrated sources have indeed been reported using different technologies and approaches, including spontaneous-four-wave-mixing (SFWM) in silicon photonics^75,83 and glass waveguides,⁸⁰ or SPDC in nonlinear waveguides.^81,82 Very recently, scattershot and Gaussian boson sampling in a silicon chip was reported online,⁷⁵ in a device that includes four waveguide-integrated photon-pair sources, based on nondegenerate SFWM. These sources consist in spiralling waveguides (to increase the nonlinear interaction region), where two-mode vacuum squeezing is produced via a single-wavelength laser pump [Fig. 3(c)]. In the chip, the sources are directly connected to an array of 12 evanescently coupled waveguides, enabling detection of 8 photons in the chip corresponding to four-photon boson sampling experiments. The measured rates were four events/hour for the scattershot regime, for an overall number of $\sim 20$ recorded events and 1.1 Hz for the Gaussian scenario.

A different strategy involves the use of quantum-dot sources to generate trains of identical single photons ^70–73 with high efficiency. Such quantum-dot sources are based on single-defect states in the semiconductor lattice, localized within a resonant microcavity [Fig. 3(d)]. A laser pulse excites the defect state, which, upon spontaneous decay, emits a single photon. These defect states are discrete and well-defined in energy: consecutive excitation pulses thus result in the emission of highly indistinguishable single photons. The use of mode-locked oscillators as pump lasers enables single-photon trains at tens of megahertz repetition rates from the quantum dot. To efficiently route the photons into different spatial optical modes, i.e., distinct inputs of the unitary circuit, active time-to-space demultiplexing^71–73 is preferably adopted (passive demultiplexing has also been used,⁷⁰ but it is not efficient when scaling up the number of photons). With this kind of source, boson sampling experiments with up to five detected photons have been demonstrated,^72,73 with five-photon events rates of 4 Hz⁷² and 0.78 kHz,⁷³ respectively. In those works, active demultiplexing was performed by a chain of Pockels cells. However, the switching frequency of those bulk-optics devices did not exceed the megahertz. Miniaturized guided-wave electro-optic switches,⁸⁵ fabricated in nonlinear substrates, might enable scaling up the operating frequencies to match the pulse frequency of mode-locked oscillators. Indeed, it is still a challenge to produce such devices with reasonably low insertion losses. As a further aspect to note, semiconductor quantum dot sources typically emit at near-infrared wavelengths around 900 nm, close to the sensitivity limits of silicon detectors. Superconducting nanowire single-photon detectors (SNSPDs), see Fig. 3(j) may thus be a convenient choice in this case.^71,73

A second important problem of the first experiments of photonic boson sampling is the relevant insertion loss of the circuit implementing the linear interferometer: in fact, the typical transmission of an integrated-optics device with reasonable complexity and 10 to 20 modes is in the order of 30%. Losses are a very relevant problem as the number $n$ of photons increases. Indeed, the success rate of the boson sampling experiment scales as the circuit losses to the power of $n$. Two innovative experimental implementations have emerged recently that may allow one to substantially reduce the loss of the interferometric apparatus.

Wang et al.^72,73 proposed and demonstrated boson sampling using multimode interferometers operating in free-space that consist in micro-optical assemblies. These are built of several fused-quartz trapezoids, covered with differently reflecting optical coatings, stacked together [see Fig. 3(f)] to produce a device with the size of a few centimetres. Collimated light beams, injected at the sides, experience multiple reflections and interference inside the structure, each interface between two trapezoids corresponding to a row of beam splitters. Such structures have been reported with geometries that mimic both the triangular⁷² and the rectangular⁷³ interferometric layouts that would allow one, in principle, to implement arbitrary linear-optical transformations. However, while the achieved experimental results prove the optimal transmission (over 99%) and high phase-stability of these structures, it is not clear whether they could be adopted to realize linear-optical transformations that are truly Haar-random, as the free parameters of the circuit appear to be quite reduced. In fact, the reflectivity of one interface defines the characteristics of an entire row of beam splitters, and phases also cannot be controlled punctually within a given trapezoid.

A fundamentally different approach was proposed theoretically in Ref. 86 and recently reported experimentally in Ref. 71, and relies on the use of temporal modes instead of spatial ones. The available modes are a train of time bins separated by an interval $\tau$. The unitary transformation is implemented by means of two different low-loss fiber loops where the photons can be routed by means of rapidly switching modulators [see Fig. 3(h)]. The smaller loop, introducing a $\tau$ delay on the injected photons, enables one to interfere adjacent time bins. The larger loop, instead, produces a delay much larger than $\tau$ and feeds back the circuit with the same photon packets, thus allowing for successive interference steps. It is easily shown that with this scheme one can implement the same beam-splitter networks that, in space, allow for arbitrary linear interferometers.⁸⁶ Such an apparatus was used, in conjunction with a quantum dot source, to realize a boson sampling experiment with four photons interfering in eight modes.⁷¹ Notably, in this approach, the photon-pulse train generated by the quantum dot source does not need to be spatially demultiplexed.

An experimental implementation of the multiboson correlation sampling scheme¹⁵ with photons generated from three atomic-ensemble quantum memories has been reported⁸⁷ very recently, showing that measurement over inner modes can be a useful resource in multiphoton networks.⁸⁸

5.

Validation of Boson Sampling

By its very nature, boson sampling⁹ is a sampling task, whose solution might not be efficiently verifiable (contrarily to problems in the complexity class NP, such as factoring). It is nevertheless crucial to identify suitable methodologies able to tackle this fundamental aspect. Indeed, any experimental instance approaching the regime of quantum advantage must be necessarily accompanied by appropriate evidence that the employed device is correctly performing the sampling process, rather than drawing data from other distributions that can be efficiently classically sampled that merely resemble the correct one. The first experimental instances of boson sampling^63–66 have employed a direct comparison between the measured sample and the expected distribution, evaluated classically with a numerical approach, as a means to verify the device operation. However, such an approach cannot be scaled to larger instances since calculating the expected distribution is exponentially hard, and an exponentially large sample has to be collected in order to obtain a meaningful estimate of the output probabilities.

While full certification is believed to be out of reach, a bottom-up approach to assess the correct functioning of a boson sampling machine is currently under investigation. The idea behind such schemes is to identify suitable classically computable mock-up distributions that represent plausible error models for the device operation. Appropriate methods should then be applied to exclude that the data were sampled from such mock-up distributions. Finally, progressively refined models representing more stringent tests can be included in the toolbox.

Starting from Ref. 89, which raised the fundamental question of boson sampling verification, some initial approaches to validation were developed (a schematic view is shown in Fig. 4). The very first example of mock-up distribution is the uniform one, for which an efficient method requiring a very small sample size has been proposed¹⁹ and tested experimentally.^67,76 The validation technique is based on the evaluation of an efficiently computable quantity, which is obtained from the elements of the unitary matrix and is only partially correlated to the permanents expressing the input–output probabilities. A less trivial mock-up distribution is the one obtained by sampling an $m$-mode interferometer, described by the same unitary transformation $U$, with distinguishable particles as inputs. In the latter case, no quantum interference occurs and an efficient classical sampling algorithm can be employed to draw data samples.⁹ To discriminate between this distinguishable-photon scenario and a boson sampling machine, a method based on likelihood ratio tests has been developed and experimentally tested⁷⁶ with up to 3 photons in a 13-mode integrated interferometer, also considering a Bayesian variant⁹⁰ and its extension to the analysis of scattershot boson sampling data.⁶⁸ More recently, likelihood ratio tests have been employed in more complex boson sampling experiments^70–73 and even used to assess a method for the classical simulation of boson sampling based on Markov chains.¹⁸ The upside of likelihood ratio tests can be found in the fast convergence rate in terms of sample size, whereas the main downside is that they rely on the evaluation of matrix permanents, and thus they are not computationally efficient. A different approach to discriminate against distinguishable particles can be found in exploiting collective properties of multiphoton interference such as bunching or clouding,⁶⁷ the latter being the tendency of bosons to exit on nearby output modes in quantum walks unitaries. By combining the observation of such property with Bayesian hypothesis testing, it was possible to discriminate multiphoton interference with respect to distinguishable particles for 3 photons in an integrated quantum walk unitary of 21 modes.

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.

As a matter of fact, approaches employing bunching or clouding as a signature of the correct behavior of a boson sampling machine can be tricked by a classically computable configuration called mean-field sampler.⁹¹ The latter is a model originating from independent, noninterfering single-photon states with random phases and is able to mimic some (but not all) features of genuine multiphoton interference. To help discriminate against this model, zero transmission laws⁹² based on peculiar transformations can be employed. More specifically, for certain unitary matrices and input states possessing specific symmetries, it is possible to efficiently predict (without relying on permanent calculations) that a significant subset of input–output combinations will never be observed when genuine multiphoton interference is present. Hence, by implementing such transformations and by directly counting how many events are recorded in the forbidden combinations, it is possible to verify whether the input state is a mean-field sampler. These zero-transmission laws have been proposed^91,92 for Fourier interferometers, and tested experimentally in integrated devices by employing a universal design⁶⁹ or an efficient 3-D layout,⁹³ leading to the observation of zero transmission law with 2- and 3-photons in devices with up to 8 modes. Theoretical^94,95 and experimental⁹⁶ papers have extended this approach to so-called Sylvester interferometers, which were analyzed using a general mathematical framework.^97,98 Sylvester interferometers have been also suggested and tested as being optimal transformations for certain number of photons and modes,⁹⁹ in terms of minimizing the achievable error rate as a function of the sample size in a general test of genuine multiphoton interference. Further studies focusing on specific interferometer designs have shown the possibility of constructing a genuine indistinguishability witness in a similar spirit to the detection of genuine multipartite entanglement.¹⁰⁰

Moving a step further, other validation methods that can be adopted for any linear evolution and do not require the implementation of purpose-built interferometers have been devised. A first class of validation tests based on pattern recognition techniques¹⁰¹ was developed for both boson sampling validation and its scattershot variant. Such an approach constructs a compatibility test¹⁰² that compares two different samples and determines whether they have been both generated by indistinguishable (distinguishable) particles or not. This is obtained using machine learning techniques for the identification of internal patterns within the measured samples. This approach has been tested in 3-photon, 13-mode experiments. A different methodology relying on statistical signatures of many-body quantum interference has been recently proposed¹⁰³ (with an associated perspective article¹⁰⁴). This method is based on advanced and mostly analytic tools from statistical physics and random matrix theory and is efficient in the number of photons $n$ and modes $m$. This approach has been implemented experimentally¹⁰⁵ in a three-photon, seven-mode experiment, by including machine learning techniques to optimize the identification whether the sample has been generated by indistinguishable or distinguishable photons. Further methods have been proposed recently,^106,107,108 but they are still lacking of experimental implementation.

The latter two methods we have discussed in some detail are actually representatives of the two main categories of validation schemes: (i) approaches based on computational criteria and (ii) physically motivated approaches. In the first case, the validator employs computational techniques to find patterns or peculiar features in data samples. Such techniques can be general-purpose and do not rely on knowledge of the system under investigation (multiphoton evolution in multimode interferometers). Those approaches directly look at the output data produced by the quantum device and search for common properties without making any specific assumption on the system under investigation. In the second case, the validation methods exploit the physical phenomenon behind the boson sampling task, and thus design techniques that rely on the knowledge that output data have been produced by multiphoton interference. These physically motivated approaches can also employ tools inspired by other physical systems, such as many-body physics.

Note that the two distinct methodologies described above (computationally or physically based) can also be combined and benefit from each other. On the one side, computationally oriented approaches can provide new insights in the physical problem, thus highlighting hidden features otherwise not detectable. On the other hand, the performances of physically based approaches can be boosted by adding computational modules in the data identification stage.

6.

Scalability Toward Quantum Supremacy

It is important to note that many of the requirements for boson sampling may be relaxed if future theoretical work manages to provide evidence for hardness of simulation of simpler experiments. For example, the requirements of using $m=O(n^2)$ modes and that interferometers be drawn from the uniform, Haar ensemble, were assumptions made for technical convenience in the original work by AA,⁹ but it is an open question whether they are strictly necessary.

One major scalability issue that seems to follow from the requirement of Haar-random interferometers is related to losses. Arbitrary linear-optical networks have worst-case depth that is linear (in the number of modes).^23,24,109 If each beam splitter has a fixed loss factor, this implies an exponentially small per-photon probability of survival in the interferometer, which would imply that boson sampling is not scalable. One important avenue of theoretical work is to investigate the hardness of boson sampling with other interferometer ensembles that hopefully can be built with shorter depth (similar to the idea of $t$ designs in quantum computing¹¹⁰) and thus circumvent losses. Another theoretical improvement that would help in this direction would be proving the hardness of boson sampling with fewer than $O(n^2)$ modes [hopefully only $O(n)$ modes]. A caveat is that this might introduce the need for number-resolving detectors. Interestingly, in the context of exact boson sampling it is known that interferometers of depth 4 and $O(2n)$ modes are already hard to simulate,¹² although it remains an important open question whether a similar result holds also for approximate simulation.

The other main scalability issue to reach the quantum advantage regime with photonic boson sampling devices is represented by photon sources. The main requirements toward a scalable implementation are high generation probability, high level of photon indistinguishability, and low probability of generating higher order photon number terms. Current approaches employ parametric down-conversion, spontaneous four wave mixing, and solid-state quantum-dot sources.

The first category of photon generation modules suffers from an intrinsic small generation probability. Indeed, parametric down-conversion is a probabilistic process where the generation efficiency $g$ must be kept low to avoid significant contributions from higher order terms with more than one photon per mode. This feature becomes an issue when using parametric down-conversion sources for fixed input boson sampling since the probability of generating the correct $n$-photon input is exponentially decreasing as $g^n$. Nevertheless, some of the variants of the original task, such as scattershot and Gaussian boson sampling, employ a careful design leading to a significant enhancement in the generation rate with parametric down-conversion sources. Scaling up to a larger number of photons requires reaching high values of heralding efficiencies and photon indistinguishability. Recent studies have shown the possibility of tailoring the source characteristics to obtain significant improvements in those parameters.⁷⁴ Further perspectives for scaling up the number of photons can be envisaged with multiplexing,⁸⁴ within an integrated platform.⁸⁰

The second approach employing solid-state sources has been recently introduced in the boson sampling context. Such a platform presents significantly higher efficiency and generation rate⁷³ than parametric down-conversion, maintaining a negligible probability of generating multiple photons at the same time. Current experiments employ single quantum-dot sources combined with time-to-spatial multiplexing,⁸⁵ thus distributing a train of $n$ single photons generated at subsequent time bins in $n$ different spatial modes. Such an approach requires implementing multiplexing with a low level of losses for scaling up to large photon number. An alternative approach would require generating highly indistinguishable photons from different quantum-dot sources.

The problem of devising photon sources of high efficiency and indistinguishability is also strongly related to the transition between a classically simulable regime and the hard-to-simulate regime. More specifically, recent studies^38,44 have shown that partial photon indistinguishability $p$ limits the hardness of a classical simulation. Indeed, given a certain value of $p$, it has been shown that an $n$-photon system presents a complexity that corresponds to a lower number of photons $k<n$. Furthermore, such threshold only depends on the photon indistinguishability $p$ and is actually independent from $n$, meaning that it is not possible to overcome this issue only by increasing $n$. Thus strong effort should be dedicated to building sources with a high level of photon indistinguishability.

7.

Outlook

In this review, we have discussed recent advances in the implementation of photonic boson sampling. Starting from the original proposal by AA⁹ and from the first instances reported in Refs. 6364.65.–66, significant progress has been reported on both theory and experiments. Several theoretical studies have focused on different aspects of the problem, including the definition of the limits for classical simulations, the role of experimental imperfections in the complexity of classical simulation, as well as proposals of new variants of the original problem. In parallel, technological advances have led to the implementation of progressively larger experimental instances. Indeed, tools such as quantum dot single-photon sources or superconducting nanowire single-photon detector have enabled the possibility to generate and measure samples with larger number of photons, opening the route to further advances. Additionally, progress in the implementation of integrated multimode interferometers allowed the inclusion of reconfigurable elements in the structures, in order to realize arbitrary linear operations.

A fundamental issue toward achieving the regime of quantum advantage is the capability to identify whether a given set of data has been sampled from the correct distribution. This is particularly important for future, larger-scale implementations where the classical simulation will become unfeasible. The first results focusing on identifying specific errors (such as sampling from a distribution with distinguishable particles) via different techniques have been developed and tested, but additional work in this direction is required.

Finally, the first proposals of application of boson sampling devices outside its original scope have been reported. For instance, it has been shown that Gaussian boson sampling represents a tool for photonic simulation of vibronic spectra in molecular dynamics.^59,60,75 Promising perspectives have been also pointed out in the context of hybrid quantum computation: in this approach, specific quantum routines are embedded in a more complex computation task performed with a classical approach, providing an overall quantum boost. Some examples have very recently been proposed for the Gaussian boson sampling variant, which is related to the sampling of hafnians of the evolution matrix. More specifically, two relevant scenarios have been identified. On one side, Arrazola et al.⁵⁸ have introduced an NP-hard optimization problem (Max-Haf). A Gaussian boson sampling device can be inserted within the computation performed by stochastic algorithms (such as random search or simulated annealing) to improve the algorithm performance. The key ingredient can be found in replacing the uniform sampling part of the algorithm with a quantum device that performs sampling from a probability distribution proportional to matrix hafnians, thus leading to a faster convergence to the output of the computation. In parallel, the connection between hafnians and graph theory¹¹¹ has led to a few proposals aiming to exploit Gaussian boson sampling in the analysis of complex graphs. For instance, in Ref. 57, it has been shown that the estimation of the number of perfect matchings in undirected graphs can be performed more efficiently by encoding the adjacency matrix of a graph in a Gaussian state, allowing one to improve the sampling success rate. Furthermore, stochastic algorithms that tackle an NP-hard problem, such as the densest $k$-subgraph problem, can have its performance enhanced when sampling is performed via a Gaussian boson sampling device.⁵⁶ Finally, a very recent work¹¹² has shown the connection between such computational model and graph isomorphism. These ideas can represent a starting point for the application of quantum boson sampling devices also to problems not envisaged in the original theoretical proposal.