## Abstract

Although universal quantum computers ideally solve problems such as factoring integers exponentially more efficiently than classical machines, the formidable challenges in building such devices motivate the demonstration of simpler, problem-specific algorithms that still promise a quantum speedup. We constructed a quantum boson-sampling machine (QBSM) to sample the output distribution resulting from the nonclassical interference of photons in an integrated photonic circuit, a problem thought to be exponentially hard to solve classically. Unlike universal quantum computation, boson sampling merely requires indistinguishable photons, linear state evolution, and detectors. We benchmarked our QBSM with three and four photons and analyzed sources of sampling inaccuracy. Scaling up to larger devices could offer the first definitive quantum-enhanced computation.

Universal quantum computers require physical systems that are well isolated from the decohering effects of their environment, while at the same time allowing precise manipulation during computation. They also require qubit-specific state initialization, measurement, and generation of quantum correlations across the system (*1*–*4*). Although there has been substantial progress in proof-of-principle demonstrations of quantum computation (*5*–*8*), simultaneously meeting these demands has proven difficult. This motivates the search for schemes that can demonstrate quantum-enhanced computation under more favorable experimental conditions. Investigating the space between classical and universal quantum computers has attracted broad interest (*9*–*11*).

Boson sampling has recently been proposed as a specific quantum computation that is more efficient than its classical counterpart but only requires indistinguishable bosons, low decoherence linear evolution, and measurement (*12*). The distribution of bosons that have undergone a unitary transformation *U* is thought to be exponentially hard to sample from classically (*12*). The probability amplitude of obtaining a certain output is directly proportional to the permanent of a corresponding submatrix of *U* (*13*). The permanent expresses the wave function of identical bosons, which are symmetric under exchange (*14*, *15*); in contrast, the Slater determinant expresses the wave function of identical fermions, which are antisymmetric under exchange. Whereas determinants can be evaluated efficiently, permanents have long been believed to be hard to compute (*16*); the best-known algorithm scales exponentially with the size of the matrix.

One can envision a race between a classical and a quantum machine to sample the boson distribution given an input state and *U*. The classical machine would evaluate at least part of the probability distribution, which requires the analysis of matrix permanents. An ideal quantum boson-sampling machine (QBSM) instead creates indistinguishable bosons, physically implements *U*, and records the outputs. Although the QBSM is not believed to efficiently estimate any individual matrix permanent, for a sufficiently large system it is expected to beat the classical computer in sampling over the entire distribution (*12*).

Photonics is a natural platform to implement boson sampling because sources of indistinguishable photons are well developed (*17*), and integrated optics offers a scalable route to low decoherence linear transformations over many modes (*18*). Such circuits can be rapidly reconfigured to sample from a user-defined operation (*19*, *20*). Importantly, boson sampling requires neither nonlinearities nor on-demand entanglement, which are substantial challenges in photonic universal quantum computation (*21*). This clears the way for experimental boson sampling with existing photonic technology, building on the extensively studied two-photon Hong-Ou-Mandel interference effect (*22*).

A QBSM (Fig. 1) samples the output distribution of a multiparticle bosonic quantum state |Ψ_{out}〉, prepared from a specified initial state |**T**〉 and linear transformation Λ. Unavoidable losses in the system imply Λ will not be unitary, although lossy QBSMs can still surpass classical computation (*12*, *23*). A trial begins with the input state *M* input modes in the occupation-number representation. The output state |Ψ_{out}〉 is generated according to the linear map between input and output mode creation operators **Λ** is an *M* × *M* matrix. Lastly, the particles in each of the *M* output modes are counted. The probability of a particular measurement outcome |**S**〉 = |*S*_{1}...*S _{M}*〉 is given by

where the *N* × *N* submatrix *S _{j}* copies of the

*j*

^{th}column (and

*T*copies of the

_{i}*i*

^{th}row) of

**Λ**(

*13*).

Our QBSM consists of sources of indistinguishable single photons, a multiport linear optical circuit, and single-photon counting detectors. Two parametric down-conversion (PDC) pair sources (*24*) were used to inject up to four photons into a silica-on-silicon integrated photonic circuit, fabricated by ultraviolet laser writing (*19*, *25*). The circuit (Fig. 2A) consists of *M* = 6 input and output spatial modes coupled by a network of 10 beam splitters (*18*). The output state was measured with single-photon avalanche photodiodes on each mode. We only considered outcomes in which the number of detections equals the intended number of input photons (*13*).

Our central result of three- and four-boson sampling is shown in Fig. 3. In the first case, we repeatedly injected three photons in the input state |**T**〉 = |011010〉, monitored all outputs, and collected all threefold coincident events. In the four-photon experiment, we used the input |**T**〉 = |202000〉 and recorded all fourfold events (*26*). For each experiment, the measured relative frequencies **S**〉 are shown along with their observed statistical variation. The corresponding theoretical **Λ**, described below.

We reconstructed **Λ** with a series of one- and two-photon transmission measurements to determine its complex-valued elements *27*). The characterization results for the circuit used in the three-photon experiment are shown in Fig. 2, B and C. To obtain the magnitude τ* _{ij}*, single photons were injected in mode

*i*. The probability of a subsequent detection in mode

*j*is given by

*were determined from two-photon quantum interference measurements. The probability that a photon is detected in each of modes*

_{ij}*j*

_{1}and

*j*

_{2}when they are injected in modes

*i*

_{1}and

*i*

_{2}is given by

*given the previously determined magnitudes τ*

_{ij}*(*

_{ij}*13*).

To analyze the performance of our QBSM, we compared our results to an ideal machine. We quantified the match of two sets of relative frequencies **P**^{(1)} and **P**^{(2)} by calculating the L_{1} distance *N* denotes the number of photons in a sample (*28*). Identical and maximally dissimilar distributions correspond to *d* = 0 and *d* = 1, respectively. For our experiments, we calculated *d*^{(}^{N}^{)}(**P**^{exp},**P**^{th}) to give *d*^{(3)} = 0.094 ± 0.014 and *d*^{(4)} = 0.097 ± 0.004, where errors arise solely from the experimental uncertainty represented by the red shaded bars in Fig. 3. Even in an ideal QBSM with perfect state preparation and detection, the statistical variations result in nonzero *d*. When we substituted for our experimental data a Monte Carlo sampling of **P**^{th} with sample size equivalent to our experiments, we instead calculated *d*^{(3)} = 0.043 ± 0.012 and *d*^{(4)} = 0.059 ± 0.022. This suggests that there are appreciable contributions to *d*(**P**^{exp},**P**^{th}) beyond statistical deviation.

Because of experimental limitations, our QBSM occasionally samples distributions other than **P**^{th}. The dominant sources of this sampling inaccuracy in our experiment are multiphoton emission and partial distinguishability among the photons. In practice, all single-photon sources produce multiple photons with a finite probability (*17*). For our PDC sources, the output state is about |00〉 + λ|11〉 + λ^{2}|22〉, with λ << 1. Both single-photon and undesired multiphoton terms increase with λ. In our three-photon experiments, for example, multiphoton emission from the two PDC sources can lead to input states |**T**〉 = |021010〉 or |012020〉, which contribute to threefold coincident events if photons are lost or emerge in the same output mode. In addition, partial distinguishability of the photons contaminates the distribution sampled by the QBSM by mixing in one- and two-photon interference effects (*29*).

We formed a new distribution **P**^{mod} that accounts for the effects of multiphoton emission and photon distinguishability (*13*). The distance *d*(**P**^{exp},**P**^{mod}) shown by the green point (Fig. 4, A and B insets) was found to be consistent with the statistical variation resulting from a finite sample size, for both the three- and four-photon experiments. This suggests we have correctly identified and modeled the sources of inaccuracy. To investigate how the performance of our QBSM depends on λ and photon distinguishability, we calculated *d*(**P**^{mod},**P**^{th}) for a range of operating parameters (Fig. 4, C and D). In terms of λ, a clear trade-off is presented between data rate and inaccuracy because of multiphoton emission, which is an intrinsic consequence of using PDC sources. Improvement in photon indistinguishability increases the fidelity to the ideal machine and additionally is thought to enhance the computational power of a QBSM (*29*).

Our results demonstrate that boson sampling is related to the computation of matrix permanents, a problem believed to be classically hard. Our successful diagnosis of the source and magnitude of the principal sampling errors, as validated by a reduction in *d*(**P**^{exp},**P**^{mod}) to within the statistical variation of a perfect QBSM, will inform the design of next-generation devices. Although investigations into quantum-enhanced computation in the presence of errors is ongoing, it already appears that the boson-sampling model makes less stringent demands on device performance than universal photonic quantum computers (*12*, *23*, *29*). There is thus reason for optimism that ongoing advances in integrated photonics, such as reduced transmission loss, efficient number-resolving detectors (*30*), and multiplexed (*31*, *32*) or single-emitter (*17*) photon sources, will enable larger QBSMs that outperform classical computers. Beyond the specific boson-sampling problem, such a device would provide evidence for the computational power of quantum mechanics.

## Supplementary Materials

www.sciencemag.org/cgi/content/full/science.1231692/DC1

Materials and Methods

Supplementary Text

## References and Notes

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
Materials and methods are available as supplementary materials on
*Science*Online. - ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
Eq. 1 is expected to hold for any |
**S**〉 and |**T**〉; however, the classical hardness of sampling*P*(**S**|**T**) is maximized when*S*∈ {0,1} for a given_{j},T_{i}*N*and**Λ**. - ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
**Acknowledgments:**We thank J. Nunn for valuable insights. This work was supported by the Engineering and Physical Sciences Research Council (EP/C013840/1, EP/H03031X/1, and EP/J000051/1), the European Commission project Q-ESSENCE (248095), the Royal Society, and the Air Force Office of Scientific Research (European Office of Aerospace Research and Development). X.M.J. and N.K.L. are supported by European Union Marie-Curie fellowships (PIIF-GA-2011-300820 and PIEF-GA-2010-275103). J.B.S. acknowledges support from the U.S. Air Force Institute of Technology. The views expressed in this article are those of the authors and do not reflect the official policy or position of the U.S. Air Force, Department of Defense, or the U.S. Government.