Boson sampling

Consider a multimode linear-optical circuit of N modes that is injected with M indistinguishable single photons (N>M). Then, the photonic implementation of the boson sampling task consists of generating a sample from the probability distribution of single-photon measurements at the output of the circuit. Specifically, this requires reliable sources of single photons (currently the most widely used ones are parametric down-conversion crystals), as well as a linear interferometer. The latter can be fabricated, e.g., with fused-fiber beam splitters,[3] through silica-on-silicon[4] or laser-written[5][6][7] integrated interferometers, or electrically and optically interfaced optical chips.[8] Finally, the scheme also necessitates high efficiency single photon-counting detectors, such as those based on current-biased superconducting nanowires, which perform the measurements at the output of the circuit. Therefore, based on these three ingredients, the boson sampling setup does not require any ancillas, adaptive measurements or entangling operations, as does e.g. the universal optical scheme by Knill, Laflamme and Milburn (the KLM scheme). This makes it a non-universal model of quantum computation, and reduces the amount of physical resources needed for its practical realization.

Specifically, suppose the linear interferometer is described by an N×N unitary matrix ${\displaystyle U,}$ which performs a linear transformation of the creation (annihilation) operators ${\displaystyle a_{i}^{\dagger }}$ ${\displaystyle (a_{i}^{})}$ of the circuit's input modes:

${\displaystyle b_{j}^{\dagger }=\sum _{i=1}^{N}U_{ji}a_{i}^{\dagger }\;\;(b_{j}=\sum _{i=1}^{N}U_{ji}^{*}a_{i}).}$

Here i (j) labels the input (output) modes, and ${\displaystyle b_{j}^{\dagger }}$ ${\displaystyle (b_{j}^{})}$ denotes the creation (annihilation) operators of the output modes (i,j=1,..., N). An interferometer characterized by some unitary ${\displaystyle U}$ naturally induces a unitary evolution ${\displaystyle \varphi _{M}(U)}$ on ${\displaystyle M}$-photon states. Moreover, the map ${\displaystyle \varphi _{M}}$ is a homomorphism between ${\displaystyle N}$-dimensional unitary matrices, and unitaries acting on the exponentially large Hilbert space of the system: simple counting arguments show that the size of the Hilbert space corresponding to a system of M indistinguishable photons distributed among N modes is given by the binomial coefficient ${\displaystyle {\tbinom {M+N-1}{M}}}$ (notice that since this homomorphism exists, not all values of ${\displaystyle W}$ are possible).

Suppose the interferometer is injected with an input state of single photons ${\displaystyle |\psi _{\text{in}}\rangle =}$${\displaystyle |s_{1},s_{2},...,s_{N}\rangle }$ with ${\displaystyle \sum _{k=1}^{N}s_{k}=M}$ ${\displaystyle (s_{k}}$ is the number of photons injected into the kth mode). Then, the state ${\displaystyle |\psi _{\text{out}}\rangle }$ at

the output of the circuit can be written down as ${\displaystyle |\psi _{\text{out}}\rangle =\varphi _{M}(U)|s_{1},s_{2},...,s_{N}\rangle .}$ A simple way to understand the homomorphism between ${\displaystyle U}$ and ${\displaystyle \varphi _{M}(U)}$ is the following :

We define the isomorphism for the basis states: ${\displaystyle P_{|s_{1},s_{2},...,s_{N}\rangle }(}$x${\displaystyle )\equiv x_{1}^{s_{1}}{\cdot }x_{2}^{s_{2}}{\cdot \cdot \cdot }x_{N}^{s_{N}}}$, and get the following result : ${\displaystyle P_{{\varphi (U)}|s_{1},s_{2},...,s_{N}\rangle }(}$x${\displaystyle )=P_{|s_{1},s_{2},...,s_{N}\rangle }(U}$x${\displaystyle )}$

Consequently, the probability ${\displaystyle p(t_{1},t_{2},...,t_{N})}$ of detecting ${\displaystyle t_{k}}$ photons at the kth output mode is given as[9]

${\displaystyle p(t_{1},t_{2},...,t_{N})=|\langle t_{1},t_{2},...,t_{N}|\psi _{\text{out}}\rangle |^{2}={\frac {|{\text{Perm}}\,U_{S,T}|^{2}}{t_{1}!\cdot \cdot \cdot t_{N}!s_{1}!\cdot \cdot \cdot s_{N}!}}.}$

In the above expression ${\displaystyle {\text{Perm}}\,U_{S,T}}$ stands for the permanent of the matrix ${\displaystyle U_{S,T},}$ which is obtained from the unitary ${\displaystyle U}$ by repeating ${\displaystyle s_{i}}$ times its ith column and ${\displaystyle t_{j}}$ times its jth row. Usually, in the context of the boson sampling problem the input state is taken of a standard form, denoted as ${\displaystyle |1_{M}\rangle ,}$ for which each of the first M modes of the interferometer is injected with a single photon. In this case the above expression reads:

${\displaystyle p(t_{1},t_{2},...,t_{N})=|\langle t_{1},t_{2},...,t_{N}|\varphi _{M}(U)|1_{M}\rangle |^{2}={\frac {|{\text{Perm}}\,U_{T}|^{2}}{t_{1}!\cdot \cdot \cdot t_{N}!}},}$

where the matrix ${\displaystyle U_{T}}$ is obtained from ${\displaystyle U}$ by keeping its first M columns and repeating ${\displaystyle t_{j}}$ times its jth row. Subsequently, the task of boson sampling is to sample either exactly or approximately from the above output distribution, given the unitary ${\displaystyle U}$ describing the linear-optical circuit as input. As detailed below, the appearance of the permanent in the corresponding statistics of single-photon measurements contributes to the hardness of the boson sampling problem.

The main reason of the growing interest towards the model of boson sampling is that despite being non-universal it is strongly believed to perform a computational task that is intractable for a classical computer. One of the main reasons behind this is that the probability distribution, which the boson sampling device has to sample from, is related to the permanent of complex matrices. The computation of the permanent is in the general case an extremely hard task: it falls in the #P-hard complexity class. Moreover, its approximation to within multiplicative error is a #P-hard problem as well.

All current proofs of the hardness of simulating boson sampling on a classical computer rely on the strong computational consequences that its efficient simulation by a classical algorithm would have. Namely, these proofs show that an efficient classical simulation would imply the collapse of the polynomial hierarchy to its third level, a possibility that is considered very unlikely by the computer science community, due to its strong computational implications (in line with the strong implications of P=NP problem).

The above requirements for the photonic boson sampling machine allow for its small-scale construction by means of existing technologies. Consequently, shortly after the theoretical model was introduced, four different groups[3][4][6][7] simultaneously reported its realization.

Specifically, this included the implementation of boson sampling with:

• two and three photons scattered by a six-mode linear unitary transformation (represented by two orthogonal polarizations in 3×3 spatial modes of a fused-fiber beam splitter) by a collaboration between the University of Queensland and MIT[3]
• three photons in different modes of a six-mode silica-on-silicon waveguide circuit, by a collaboration between Universities of Oxford, Shanghai, London and Southampton[4]
• three photons in a femtosecond laser-written five-mode interferometer, by a collaboration between universities of Vienna and Jena[6]
• three photons in a femtosecond laser-written five-mode interferometer implementing a Haar-random unitary transformation, by a collaboration between Milan's Institute of Photonics and Nanotechnology, Universidade Federal Fluminense and Sapienza University of Rome.[7]

Later on, more complex boson sampling experiments have been performed, increasing the number of spatial modes of random interferometers up to 13[27] and 9[28] modes, and realizing a 6-mode fully reconfigurable integrated circuit.[8] These experiments altogether constitute the proof-of-principle demonstrations of an operational boson sampling device, and route towards its larger-scale implementations.

The output of a universal quantum computer running, for example, Shor's factoring algorithm, can be efficiently verified classically, as is the case for all problems in the non-deterministic polynomial-time (NP) complexity class. It is however not clear that a similar structure exists for the boson sampling scheme. Namely, as the latter is related to the problem of estimating matrix permanents (falling into #P-hard complexity class), it is not understood how to verify correct operation for large versions of the setup. Specifically, the naive verification of the output of a boson sampler by computing the corresponding measurement probabilities represents a problem intractable for a classical computer.

A first relevant question is whether it is possible or not to distinguish between uniform and boson-sampling distributions by performing a polynomial number of measurements. The initial argument introduced in Ref.[31] stated that as long as one makes use of symmetric measurement settings the above is impossible (roughly speaking a symmetric measurement scheme does not allow for labeling the output modes of the optical circuit). However, within current technologies the assumption of a symmetric setting is not justified (the tracking of the measurement statistics is fully accessible), and therefore the above argument does not apply. It is then possible to define a rigorous and efficient test to discriminate the boson sampling statistics from an unbiased probability distribution.[32] The corresponding discriminator is correlated to the permanent of the submatrix associated with a given measurement pattern, but can be efficiently calculated. This test has been applied experimentally to distinguish between a boson sampling and a uniform distribution in the 3-photon regime with integrated circuits of 5, 7, 9[28] and 13 modes.[27]

The test above does not distinguish between more complex distributions, such as quantum and classical, or between fermionic and bosonic statistics. A physically motivated scenario to be addressed is the unwanted introduction of distinguishability between photons, which destroys quantum interference (this regime is readily accessible experimentally, for example by introducing temporal delay between photons). The opportunity then exists to tune between ideally indistinguishable (quantum) and perfectly distinguishable (classical) data and measure the change in a suitably constructed metric. This scenario can be addressed by a statistical test which performs a one-on-one likelihood comparison of the output probabilities. This test requires the calculation of a small number of permanents, but does not need the calculation of the full expected probability distribution. Experimental implementation of the test has been successfully reported in integrated laser-written circuits for both the standard boson sampling[27] (3 photons in 7-, 9- and 13-mode interferometers) and the scattershot version[20] (3 photons in 9- and 13-mode interferometers with different input states). Another possibility is based on the bunching property of indinguishable photons. One can analyze the probability to find a k-fold coincidence measurement outcomes (without any multiply populated input mode), which is significantly higher for distinguishable particles than for bosons due to the bunching tendency of the latters.[28] Finally, leaving the space of random matrices one may focus on specific multimode setups with certain features. In particular, the analysis of the effect of bosonic clouding (the tendency for bosons to favor events with all particles in the same half of the output array of a continuous-time many-particle quantum walk) has been proven to discriminate the behavior of distinguishable and indistinguishable particles in this specific platform.[28]

A different approach to confirm that the boson sampling machine behaves as the theory predicts is to make use of fully reconfigurable optical circuits. With large-scale single-photon and multiphoton interference verified with predictable multimode correlations in a fully characterized circuit, a reasonable assumption is that the system maintains correct operation as the circuit is continuously reconfigured to implement a random unitary operation. To this end, one can exploit quantum suppression laws (the probability of specific input-output combinations is suppressed when the linear interferometer is described by a Fourier matrix or other matrices with relevant symmetries).[33] These suppression laws can be classically predicted in efficient ways. This approach allows also to exclude other physical models, such as mean-field states, which mimic some collective multiparticle properties (including bosonic clouding). The implementation of a Fourier matrix circuit in a fully reconfigurable 6-mode device has been reported,[8] and experimental observations of the suppression law have been shown for 2 photons in 4- and 8-mode Fourier matrices.[34]

Apart from the photonic realization of the boson sampling task, several other setups have been proposed. This includes, e.g., the encoding of bosons into the local transverse phonon modes of trapped ions. The scheme allows deterministic preparation and high-efficiency readout of the corresponding phonon Fock states and universal manipulation of the phonon modes through a combination of inherent Coulomb interaction and individual phase shifts.[35] This scheme is scalable and relies on the recent advances in ion trapping techniques (several dozens of ions can be successfully trapped, for example, in linear Paul traps by making use of anharmonic axial potentials).

Another platform for implementing the boson sampling setup is a system of interacting spins: recent observation show that boson sampling with M particles in N modes is equivalent to the short-time evolution with M excitations in the XY model of 2N spins.[36] One necessitates several additional assumptions here, including small boson bunching probability and efficient error postselection. This scalable scheme, however, is rather promising, in the light of considerable development in the construction and manipulation of coupled superconducting qubits and specifically the D-Wave machine.

The task of boson sampling shares peculiar similarities with the problem of determining molecular vibronic spectra: a feasible modification of the boson sampling scheme results in a setup that can be used for the reconstruction of a molecule's Franck–Condon profiles (for which no efficient classical algorithm is currently known). Specifically, the task now is to input specific squeezed coherent states into a linear interferometer that is determined by the properties of the molecule of interest.[37] Therefore, this prominent observation makes the interest towards the implementation of the boson sampling task to get spread well beyond the fundamental basis.

It has also been suggested to use a superconducting resonator network Boson Sampling device as an interferometer. This application is assumed to be practical, as small changes in the couplings between the resonators will change the sampling results. Sensing of variation in the parameters capable of altering the couplings is thus achieved, when comparing the sampling results to an unaltered reference.[38]

Variants of the boson sampling model have been used to construct classical computational algorithms, aimed, e.g., at the estimation of certain matrix permanents (for instance, permanents of positive-semidefinite matrices related to the corresponding open problem in computer science[39]) by combining tools proper to quantum optics and computational complexity.[40]

Coarse-grained boson sampling has been proposed as a resource of decision and function problems that are computationally hard, and may thus have cryptographic applications.[41][42][43] The first related proof-of-principle experiment was performed with a photonic boson-sampling machine (fabricated by a direct femtosecond laser-writing technique),[44] and confirmed many of the theoretical predictions.

Gaussian boson sampling has been analyzed as a search component for computing binding propensity between molecules of pharmacological interest as well.[45]

• Linear optical quantum computing
• KLM protocol
• Cross-entropy benchmarking

• QUCHIP project
• Quantum Information Lab – Sapienza: video on boson sampling
• Quantum Information Lab – Sapienza: video on scattershot boson sampling
• The Qubit Lab – Boson Sampling