Boson Sampling on a Photonic Chip

See allHide authors and affiliations

Science  15 Feb 2013:
Vol. 339, Issue 6121, pp. 798-801
DOI: 10.1126/science.1231692


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 (14). Although there has been substantial progress in proof-of-principle demonstrations of quantum computation (58), 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 (911).

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 |T=|T1TMΠi=1M(a^i)Ti|0, which describes N=i=1MTi particles distributed in 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 a^i=j=1MΛijb^j, where Λ 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〉 = |S1...SM〉 is given by

Fig. 1

Model of quantum boson sampling. Given a specified initial number state |T〉 = |T1...TM〉 and linear transformation Λ, a QBSM efficiently samples from the distribution P(S|T) of possible outcomes |S〉 = |S1...SM〉.

P(S|T)=|S|Ψout|2=|Per(Λ(S,T))|2j=1MSj!i=1MTi! (1)

where the N × N submatrix Λ(S,T) is obtained by keeping Sj copies of the jth column (and Ti copies of the ith 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).

Fig. 2

Schematic and characterization of the photonic circuit. (A) The silica-on-silicon waveguide circuits consist of M = 6 accessible spatial modes (labeled 1 to 6). For the three-photon experiment, we launched photons into inputs i = 2, 3, and 5 from two PDC sources, which produced near-single photons, and postselected outcomes in which three detections were registered among the output modes j. For the four-photon experiment, which was implemented on a different chip of identical geometry, we injected a double photon pair from a single source into the modes i = 1 and 3 and postselected on four detection events. (B and C) Measured elements of the linear transformation Embedded Image linking the input mode i to the output mode j of our three-photon apparatus. The circuit geometry dictates that several τij are zero, and our phase-insensitive input states and detection methods imply only six nonzero ϕij. Only relative values were needed because of postselection, so we rescaled each row of τ so that its maximum value is unity.

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 PSexp for every allowed outcome |S〉 are shown along with their observed statistical variation. The corresponding theoretical PSth values, calculated by using the right-hand side of Eq. 1, are shown along with their uncertainties arising from the characterization of Λ, described below.

Fig. 3

Boson-sampling results. The measured relative frequencies Pexp of outcomes in which the photons were detected in distinct modes are shown in red for (A) three- and (B) four-photon experiments. Each data set was collected over 160 hours, and statistical variations in counts are shown by the red shaded bars. The theoretical distributions Pth (blue) are obtained from the permanents of submatrices constructed from the full transformation Λ, as depicted in the inset. The blue error bars arise from uncertainties in the characterization of Λ.

We reconstructed Λ with a series of one- and two-photon transmission measurements to determine its complex-valued elements Λij=τijeiϕij (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 P1(j,i)=|Λij|2=τij2. The phases ϕij were determined from two-photon quantum interference measurements. The probability that a photon is detected in each of modes j1 and j2 when they are injected in modes i1 and i2 is given by P2(j1,j2,i1,i2)=|Λi1j1Λi2j2+Λi2j1Λi1j2|2. This expression was used to find the relevant phases ϕij given the previously determined magnitudes τ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 L1 distance d(N)(P(1),P(2))=12S|PS(1)PS(2)|, where 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)(Pexp,Pth) 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 Pth 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(Pexp,Pth) beyond statistical deviation.

Because of experimental limitations, our QBSM occasionally samples distributions other than Pth. 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 Pmod that accounts for the effects of multiphoton emission and photon distinguishability (13). The distance d(Pexp,Pmod) 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(Pmod,Pth) 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).

Fig. 4

Sampling accuracy. We consider several boson distributions: the experimental samples Pexp, the ideal predictions of the matrix permanent Pth, and the predictions of the full model Pmod that includes higher-order emission and photon distinguishability. The L1 distance d between Pth and a Monte Carlo simulation of an ideal machine that samples Pth a finite number of times for our (A) three- and (B) four-photon cases. The errors in this case are solely a result of the finite number of samples collected by the ideal machine. (Insets) Histograms show the variation in d expected for a sample size corresponding to the 1421 and 405 counts collected in our three- and four-photon experiments. The distance d(Pexp,Pth) (red) suggests an underlying systematic inaccuracy because it falls outside the range of outputs of an ideal machine indicated in the histogram. Our full model is validated by the distance d(Pexp,Pmod) (green), which is consistent with statistical variation. The red and green dot positions correspond to the L1 axis only. The predicted variation in d(Pth,Pmod) is shown as a function of λ and the photon distinguishabilites, represented by the reduction in two-photon interference visibility V, for the (C) three- and (D) four-photon cases. Our experimental conditions are marked (red dot).

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(Pexp,Pmod) 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

Materials and Methods

Supplementary Text

References (3337)

References and Notes

  1. Materials and methods are available as supplementary materials on Science Online.
  2. Eq. 1 is expected to hold for any |S〉 and |T〉; however, the classical hardness of sampling P(S|T) is maximized when Sj,Ti ∈ {0,1} for a given N and Λ.
  3. 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.

Stay Connected to Science

Navigate This Article