Photonic Boson Sampling in a Tunable Circuit

See allHide authors and affiliations

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


Quantum computers are unnecessary for exponentially efficient computation or simulation if the Extended Church-Turing thesis is correct. The thesis would be strongly contradicted by physical devices that efficiently perform tasks believed to be intractable for classical computers. Such a task is boson sampling: sampling the output distributions of n bosons scattered by some passive, linear unitary process. We tested the central premise of boson sampling, experimentally verifying that three-photon scattering amplitudes are given by the permanents of submatrices generated from a unitary describing a six-mode integrated optical circuit. We find the protocol to be robust, working even with the unavoidable effects of photon loss, non-ideal sources, and imperfect detection. Scaling this to large numbers of photons should be a much simpler task than building a universal quantum computer.

A major motivation for scalable quantum computing is Shor's algorithm (1), which enables the efficient factoring of large composite numbers into their constituent primes. The presumed difficulty of this task is the basis of the majority of today's public-key encryption schemes. It may be that scalable quantum computers are not realistic if, for example, quantum mechanics breaks down for large numbers of qubits (2). If, however, quantum computers are realistic physical devices, then the Extended Church-Turing (ECT) thesis—that any function efficiently computed on a realistic physical device can be efficiently computed on a probabilistic Turing machine—means that a classical efficient factoring algorithm exists. Such an algorithm, long sought after, would enable us to break public-key cryptosystems such as RSA. A third possibility is that the ECT thesis itself is wrong.

How do we answer this trilemma? As yet there is no evidence that large-scale quantum computers are inherently impossible (that will need to be tested directly via experiment), and there is no efficient classical factoring algorithm or mathematical proof of its impossibility. This leaves examining the validity of the ECT thesis, which would be contradicted, for example, by building a physical device that efficiently performs a task thought to be intractable for classical computers.

One such task is boson sampling: sampling from the probability distribution of n identical bosons scattered by some linear unitary process, U. The probabilities are defined in terms of permanents of n × n submatrices of U [in general, calculating these is exponentially difficult, because calculating the permanent is a so-called "#P-complete" problem (3); a class above even "NP-complete" in complexity] and is therefore strongly believed to be intractable. This does not mean that boson sampling is itself #P-complete: The ability to sample from a distribution need not imply the ability to calculate the permanents that gave rise to it. However, by using the fact that the permanent is #P-complete, (4) recently showed that the existence of a fast classical algorithm for this "easier" sampling task leads to drastic consequences in classical computational complexity theory, notably collapse of the polynomial hierarchy.

We tested the central premise of boson sampling, experimentally verifying that the amplitudes of n = 2 and n = 3 photon scattering events are given by the permanents of n × n submatrices of the operator U describing the physical device. We find the protocol to be robust, working even with imperfect sources, optics, and detectors.

Consider a race between two participants: Alice, who only possesses classical resources, and Bob, who in addition possesses quantum resources. They are given some physical operation, described by an evolution operator, U, and agree on a specific n-boson input configuration. Alice calculates an output sample distribution with a classical computer; Bob either builds or programs an existing linear photonic network, sending n single photons through it and obtaining his sample by measuring the output distribution (Fig. 1A). The race ends when both return samples from the distribution: The winner is whoever returns a sample fastest. As n becomes large, it is conjectured that Bob will always win, because Alice's computation runtime increases exponentially, whereas Bob's experimental runtime does not. It becomes intractable to verify Bob's output against Alice's, and, unlike for Shor's algorithm, there is no known efficient algorithm to verify the result (4). However, one can take a large instance—large enough for verification via a classical computer—and show that Bob's quantum computer solves the problem much faster, thereby strongly suggesting that the same behavior will continue for larger systems, casting serious doubt on the ECT thesis. In a fair race, Bob must verify that his device actually implements the target unitary; an alternative fair version is to give both Alice and Bob the same physical device instead of a mathematical description and have Alice characterize it before she predicts output samples via classical computation. Alice can use a characterization method that neither requires nonclassical resources nor adds to the complexity of the task (5).

Fig. 1

Experimental scheme for boson sampling. (A) Both Alice and Bob (possessing classical and quantum resources, respectively) must sample the output distribution from some unitary, U. (B) Equivalent circuit. The orthogonal polarizations in each input spatial mode can be arbitrarily combined by the unitaries a1. . .a3. A multiport, u(3), interferes all modes of the same polarization; orthogonal polarizations are recombined by b1. . .b3. (C) Experiment. Photons are produced via downconversion in a nonlinear crystal (BBO) pumped by a frequency-doubled (SHG) laser (Ti:S) (8). Photon 4 acts as a trigger and photons 1 to 3 are inputs; 1 and 3 can be delayed or advanced with respect to photon 2 by ∆τ1, ∆τ3, respectively. Local unitaries a1. . .b3 are implemented with polarization controllers (POL); u(3) is implemented by a 3 × 3 nonpolarizing FBS; three polarizing fiber beam-splitters (PBS) output six spatial modes to single-photon avalanche diodes (APDs). The fiber beam-splitters work by evanescent coupling between multiple input fibers in close proximity.

We tested boson sampling using an optical network with m = 6 input and output modes and n = 2 and n = 3 photon inputs. We implemented a randomly chosen operator so that the permanents could not be efficiently calculated (6); that is, the elements are complex-valued and the operator U is fully connected, with every input distributed to every output. The 6-input × 6-output modes of U are represented by two orthogonal polarizations in 3 × 3 spatial modes of a fused-fiber beamsplitter (FBS), an intrinsically stable and low-loss device. The mode mapping is {1,...,6} = {|H1,|V1,|H2,|V2,|H3,|V3}, where |H1 is the horizontally polarized mode for spatial mode 1. We can use polarization controllers at the inputs and outputs of the central 3 × 3 FBS to modify the evolution (see the equivalent circuit diagram in Fig. 1B).

Alice calculates the probability of bosonic scattering events in the following way (4, 7). Having characterized the evolution U using the method detailed in supplementary materials section S1 (8), and given the input and output configurations S = (s1,...,sm) and T = (t1,...,tm) with boson occupation numbers si and tj respectively, she produces an n × m submatrix UT by taking tj copies of the jth column of U. Then, she forms the n × n submatrix UST by taking si copies of the ith row of UT. The probability for the scattering event T, for indistinguishable input photons S, is given by PTQ=|Per(UST|2. Conversely, the classical scattering probabilities when the input photons are distinguishable are given by PTC=Per(U˜ST), where U˜STij=|USTij|2.

Bob, on the other hand, experimentally prepares the n-photon Fock state |t1,...,tm〉. After injecting the desired input to the circuit, he determines the probability of the scattering event T by projecting onto its corresponding state using single-photon detectors connected to a coincidence-counting logic. We prepared near–single-photon Fock states via spontaneous parametric downconversion in a nonlinear crystal [Fig. 1C, and for further details, see section S2 (8)]. Once the photons pass through the network, they are detected by single-photon avalanche diodes. The boson sampling protocol measures the frequency of output events; i.e., raw coincident photon counts. These, however, are strongly affected by differences in efficiency between photon counters, an effect that can be removed by measuring nonclassical interference visibility instead


where PTQ and PTC are the quantum and classical probabilities for the output configuration T measured for completely indistinguishable and distinguishable photons, respectively. Distinguishable statistics are obtained by introducing a temporal delay, ∆τ, between the input photons. When all photons are delayed by significantly more than their respective coherence lengths, L, true two-photon quantum interference cannot occur. Figure 2A outlines the technique Alice uses to predict the visibility from the unitary evolution U. For n = 2, high count rates mean that 27 samples of the output T were taken as the temporal delay was changed between the two input photons (9). For n = 3, where we used three of the photons from a four-photon state, low count rates mean that only three measurements were taken to avoid optical misalignment and the signal drift that occurs over necessarily long experimental runtimes. Therefore, for n = 2, the visibilities are calculated from the fitted Gaussian curves (Fig. 2B); for n = 3, the probabilities PTC are obtained from just two measurement settings: (i) PTC = {−∆τ,0,∆τ} and (ii) PTC = {∆τ,0,−∆τ}, where {τ123} are the temporal delays of photons 1, 2, and 3 with respect to photon 2, and ∆τ >> L/c. PTC is calculated as the average of these two probabilities to account for optical misalignment. Accordingly, PTQ is obtained with a single measurement of the output frequencies for completely indistinguishable photons, given by the delays {0,0,0}.

Fig. 2

Two-photon boson sampling. (A) Outline of Alice's technique to predict visibilities from the unitary evolution U (8). For photons input and output in modes 1 and 3, her prediction is given by the bar at bottom right; its uncertainty, obtained by 10 separate characterizations of the unitary, is represented by the shaded box on top of the bar. (B) Two-photon quantum interferences: the five output combinations {1,m} for the input configuration of {1,5}. Errors are smaller than marker size, and the solid blue lines are Gaussian fits used to calculate the visibility from Eq. 1. (C) Alice's predictions (blue line envelope) and Bob's measurements (orange bars) of two-photon visibilities. Input configurations are shown at the top left of each panel; output modes are labeled at the plot bottom. Errors are given by light blue and dark red boxes at the extremes of each data set. Yellow circles are the visibility predictions, given coherent input states.

Figure 2C shows Alice's predictions and Bob's measurements for n = 2. We compare their results using the average L1-norm distance per output configuration, L1=1C(m,n)T|VTAVTB|, where C(m,n) is the binomial coefficient [section S3 (8)]. We find excellent agreement between Alice and Bob, with the average across these three configurations being L¯1 = 0.021 ± 0.001. Next we show that if Alice uses her classically powerful resources, such as coherent states from a laser [section S4 (8)], to perform an analogous experiment to Bob's, she will not obtain the same results. Her classical predictions, given by the yellow circles in Fig. 2C, are markedly different from Bob's quantum measurements, with L¯1 = 0.548 ± 0.006. This large, statistically significant disagreement highlights the fact that Bob is accurately sampling from a highly nonclassical distribution.

Figure 3 shows the results for n = 3: There is a larger average distance between Alice and Bob's distributions, L¯1 = 0.122 ± 0.025, and consequently a smaller distance between Alice's classical predictions and Bob's measurements, L¯1 = 0.358 ± 0.086. We attribute these changes chiefly to the increased ratio of higher-order photon emissions in the three-photon input as compared with the two-photon case [section S5 (8)]. Having tested all possible noncolliding output configurations (that is, one photon per output-mode), we also tested colliding configurations, with two photons per output-mode. This requires photon-number resolution (10, 11), using the method shown in Fig. 4A. The results in Fig. 4B show agreement between Alice's predictions and Bob's measurements similar to the noncolliding case, L1 = 0.153 ± 0.012, and a much larger distance between Alice's classical predictions and Bob's measurements, L1 = 0.995 ± 0.045. The latter is expected because two-photon outputs are correspondingly rarer in the classical distribution.

Fig. 3

Three-photon boson sampling. Alice's predictions (blue line envelope) and Bob's measurements (orange bars) for three-photon visibilities are shown. Labels, errors, and symbols are as defined in Fig. 2C).

Fig. 4

Three-photon boson sampling with colliding outputs. (A) Number resolution was achieved with a 50:50 FBS in mode 5 and an additional detector. An imperfect splitting ratio for this FBS impedes only the effective efficiency of our number-resolving scheme (10, 11). (B) For an input configuration {1,3,5}, and measuring two photons in output 5, the solid blue-line envelope shows Alice's predictions; the green bars are Bob's measured visibilities. Labels, errors, and symbols are as defined in Fig. 2C).

These results confirm that the n = 2 and n = 3 photon scattering amplitudes are indeed given by the permanents of submatrices generated from U. The small differences, larger for n = 3 than n = 2, between Alice's Fock-state predictions and Bob's measurement results are expected, because Alice's calculations are for indistinguishable Fock-state inputs, and Bob does not actually have these. The conditioned outputs from downconversion are known to have higher-order terms; that is, a small probability of producing more than one photon per mode [section S5 and fig. S1 (8)], and are also spectrally entangled, leading to further distinguishability. Spectrally mismatched detector responses can alter the observed signals because of contributions from the immanent (12), of which the determinant and permanent are special cases. Because of flat spectral responses, we can rule this out in our experiment.

Strong evidence against the ECT thesis will come from demonstrating boson sampling with a larger-sized system, in which Bob's experimental sampling is far faster than Alice's calculation and classical verification is still barely possible; according to (4), this regime is on the order of n = 20 to n = 30 photons in a network with m >> n modes. This is beyond current technologies, but rapid improvements in efficient photon detection (13, 14), low-loss (15, 16) and reconfigurable (17, 18) integrated circuits, and improved photon sources (19) are highly promising. Boson sampling has also been proposed using the phononic modes of an ion trap (20).

An important open question remains as to the practical robustness of large implementations. Unlike the case of universal quantum computation, there are no known error correction protocols for boson sampling, or indeed for any of the models of intermediate quantum computation, such as deterministic quantum computing with one qubit (DQC1) (21, 22), temporally unstructured quantum computation (IQP) (23), or permutational quantum computing (PQC) (24). These intermediate models have garnered much attention in recent years, both because of the inherent questions they raise about quantum advantage in computing and because some of them can efficiently solve problems believed to be classically intractable; for example, DQC1 has been applied in fields that range from knot theory (25) to quantum metrology (26). A recent theoretical study posits that photonic boson sampling retains its computational advantage even in the presence of loss (27). Our experimental results are highly promising in regard to the robustness of boson sampling, finding good agreement even with clearly imperfect experimental resources.

Supplementary Materials

Supplementary Text

Fig. S1

Eqs. S1 to S12

References (2833)

References and Notes

  1. Materials and methods are available as supplementary materials on Science Online.
  2. Acknowledgements: We thank R. Fickler for help with characterization; M. de Almeida, D. Biggerstaff, and G. Gillett for experimental assistance; and A. Arkhipov, M. Bremner, and T. Rudolph for discussions. This work was supported in part by the Australian Research Council's Federation Fellow program (grant FF0668810), the Centre for Engineered Quantum Systems (grant CE110001013), and the Centre for Quantum Computation and Communication Technology (grant CE110001027); the University of Queensland Vice-Chancellor's Senior Research Fellowship program; NSF grant no. 0844626 and a Science and Technology Centre grant; a Defense Advanced Research Projects Agency Young Faculty Award grant; a TIBCO Chair; and a Sloan Fellowship.
View Abstract

Stay Connected to Science

Navigate This Article