Quantum computational advantage using photons

Abstract

Quantum computers promises to perform certain tasks that are believed to be intractable to classical computers. Boson sampling is such a task and is considered as a strong candidate to demonstrate the quantum computational advantage. We perform Gaussian boson sampling by sending 50 indistinguishable single-mode squeezed states into a 100-mode ultralow-loss interferometer with full connectivity and random matrix—the whole optical setup is phase-locked—and sampling the output using 100 high-efficiency single-photon detectors. The obtained samples are validated against plausible hypotheses exploiting thermal states, distinguishable photons, and uniform distribution. The photonic quantum computer generates up to 76 output photon clicks, which yields an output state-space dimension of 1030 and a sampling rate that is ~1014 faster than using the state-of-the-art simulation strategy and supercomputers.

The Extended Church-Turing Thesis is a foundational tenet in computer science, which states that a probabilistic Turing machine can efficiently simulate any process on a realistic physical device (1). In the 1980s, Richard Feynman observed that many-body quantum problems seemed difficult for classical computers due to the exponentially growing size of the quantum state Hilbert space. He proposed that a quantum computer would be a natural solution.

A number of quantum algorithms have since been devised to efficiently solve problems believed to be classically hard, such as Shor’s factoring algorithm (2). Building a fault-tolerant quantum computer to run Shor’s algorithm, however, still requires long-term efforts. Quantum sampling algorithms (36), based on plausible computational complexity arguments, were proposed for near-term demonstrations of quantum computational speedup in solving certain well-defined tasks compared to current supercomputers. If the speedup appears overwhelming such that no classical computer can perform the same task in a reasonable amount of time and is unlikely overturned by classical algorithmic or hardware improvements, it was called quantum computational advantage or quantum supremacy (78). Here, we use the first term.

A very recent experiment on a 53-qubit processor has generated a million noisy (~0.2% fidelity) samples in 200 s (8), while a supercomputer would take 10,000 years. It was soon argued that the classical algorithm can be improved to cost only a few days to compute all the 253 quantum probability amplitudes and generate ideal samples (9). Thus, if the competition were to generate a much larger size of samples, for example, ~1010, the quantum advantage would be reversed provided with sufficient storage. This sample-size-dependence of the comparison—an analog to loopholes in Bell tests (10)—suggests that quantum advantage would require long-term competitions between faster classical simulations and improved quantum devices.

Boson sampling, proposed by Aaronson and Arkhipov (5), was the first feasible protocol for quantum computational advantage. In boson sampling and its variants (1112), non-classical light is injected into a linear optical network, and in the output highly random, photon-number- and path-entangled state is measured by single-photon detectors. The dimension of the entangled state grows exponentially with both the number of photons and the modes, which fast renders the storage of the quantum probability amplitudes impossible. The state-of-the-art classical simulation algorithm is to calculate one probability amplitude (Permanent of the submatrix) at a time. The Permanent is classically hard and at least one Permanent should be evaluated for each sample (1314), thus the sample size loophole can be avoided. In addition, boson samplers use photons which can be operated at room temperature and are robust to decoherence.

Early proof-of-principle demonstrations of boson sampling (1516) used probabilistic, post-selected pseudo-single photons from parametric down-conversion (PDC) (17). Improved single-photon sources based on quantum dots were developed and employed to increase the multi-photon count rates, which culminated at 14-photon detection (18). However, scaling up boson sampling to a computationally interesting regime remained an outstanding experimental challenge.

Recently, Gaussian boson sampling (GBS) (1112) has emerged as a new paradigm that can not only provide a highly-efficient approach to large-scale implementations but also offer potential applications in graph-based problems (19) and quantum chemistry (20). Instead of using single photons, GBS makes full use of the Gaussian nature of the PDC sources and utilizes single-mode squeezed states (SMSS) as input nonclassical light sources which can be deterministically prepared. Sending k SMSSs through an m-mode interferometer and sampling the output scattering events using threshold detectors (see fig. S1), it has been shown that the output distribution is related to a matrix function called Torontonian (12) which is related to Permanent. Computing the Torontonian appears a computationally hard problem in the complexity class #P. It was shown recently that it takes about two days to evaluate a Torontonian function for a 50-photon click pattern (21).

Although there were small-scale demonstrations of GBS with up to five photons (2223), implementing a large-scale GBS faced significant challenges. First, it requires arrays of SMSSs with sufficiently high squeezing parameters, photon indistinguishability, and collection efficiency, simultaneously. Second, large interferometers are needed with full connectivity, matrix randomness, near-perfect wave-packet overlap and phase stability, and near-unity transmission rate, simultaneously. Third, in contrast to the Aaronson-Arkhipov boson sampling where there is no phase relation between single photons, GBS requires phase control of all the photon number states in the SMSSs. Fourth, high-efficiency detectors are needed to sample the output distribution. Finally, the obtained sparse samples from a huge output state-space should be validated, and the performance of the GBS should be benchmarked and compared with a supercomputer.

We start by describing the quantum light source arrays. Transform-limited laser pulses, with an average power of 1.4 W at a repetition rate of 250 kHz (figs. S1 and S2), is split into 13 paths and focused on 25 PPKTP crystals (Fig. 1A and figs. S3 and S4) to produce 25 two-mode squeezed states (TMSSs), which is equivalent to 50 SMSSs using a hybrid encoding as discussed later. The relative phase and squeezing parameter for each pair are shown in Fig. 1B. The PPKTP crystals are designed and temperature-controlled (fig. S5) to generate degenerate and frequency-uncorrelated photon pairs, as confirmed by joint spectrum in Fig. 1C which predicts a spectral purity of 0.98. The purity is increased to 0.99 using a 12-nm filtering (figs. S6 and S7). A second estimation of the pairwise purity is by unheralded second-order correlation measurements (24). The measured purities are plotted in Fig. 1D, with an average of 0.938. The decrease of the purity compared to the prediction from the joint spectra is mainly due to self-phase modulation. Figure 1E shows that average collection efficiency is 0.628.

Fig. 1Quantum light sources for the GBS.

(A) An illustration of the experimental setup for generating squeezed states. A custom-designed laser system consisting of a Mira 900, a pulse shaper, and a RegA 9000 is used to generate the pump laser, which was spectrally and spatially shaped to reach transform limit (figs. S1 and S2). The pulsed laser is split into 13 paths (figs. S3 and S4) and focused onto 25 PPKTP crystals. Each crystal is placed on a thermoelectric cooler (TEC) for wavelength tuning. The down-converted photons are separated from the pumping laser by a dichromic mirror (DM), the time walk between different polarizations are compensated by a KTP crystal. (B) Wigner functions of all the 25 sources. The squeezing parameter r and phase ϕ of each source is presented as (r, ϕ) in each panel. (C) The measured joint spectrum of the photon pairs indicates that the two photons are frequency uncorrelated. (D) The purity of the 25 photon sources. The measured average purity is 0.938, obtained by unheralded second-order correlation measurement. (E) The measured collection efficiencies with an average of 0.628.

The whole optical setup—from the 25 PPKTPs to the 100-mode interferometer—must be locked to a fixed phase in the presence of various environmental perturbations. To this aim, we develop an active phase locking (Fig. 2A) over the whole optical path and passive stabilization inside the interferometer (Fig. 2B) (25). For the active locking, a typical time trace of the observed phase stability is shown in the upper panel of Fig. 2B, which locks the phase of the 776 nm laser with a standard deviation of 0.04 rad [~5 nm, see (25)]. For the passive stabilization, the drift is controlled to be within λ/180 in 3.5 hours (see bottom panel of Fig. 2B). For the whole system, as shown in Fig. 2D, the high-frequency noise standard deviation is λ/350 and the low-frequency drift is λ/63 within 1 hour, a time sufficient for completing the sampling and characterizations. We estimate that the photon interference visibilities drop are less than 1% due to the phase instability.

Fig. 2Phase-locking from the photon sources to the interferometer.

(A) Schematic diagram of the active phase-locking system. A pump laser beam is used as a reference for all the squeezed states. After propagating through a ~2-m free space and 20-m optical fiber, a ~10 μW pump laser which shares the same propagation path as the down-converted photons is separated by a dichromatic mirror, which are then combined on a beam splitter with the reference laser pulse. A balanced detection scheme, which is insensitive to laser power fluctuation, is used to read out the phase information. To overcome the path length fluctuates, we wind 5-m-length optical fiber around a piezoelectric cylinder which has a sensitivity of 1.5 rad/V, a resonance frequency of 18.3 KHz and a dynamical range of 300 rad. (B) Phase stability tests. The upper (bottom) panel is a typical monitoring of phase fluctuation of active (passive) phase locking over 3.5 hours. The measured standard deviation of the phase is as small as 0.02 rad (λ/150) (0.017 rad (λ/180)). (C) We apply passive phase stabilization to the interferometer by adhering the devices onto an ultralow-expansion glass plate which is temperature stabilized within 0.02°C. The blue light paths are for the interference of the 25 pumping lasers with the reference laser. The red light paths are the input and output of the photonic network. (D) A typical phase stability measurement of the whole system in one hour. (E) The diagram of the measured 5000 amplitudes of the matrix. (F) The diagram of the measured 5000 phases of the matrix.

We make use of both the photons’ spatial and polarization degree of freedom to realize a 100×100 unitary transformation (1526). Here, the mode mapping is {1, 2, … 100} = {|H1|V1|H2|V2 … |H50|V50}, where H (V) denotes horizontal (vertical) polarization, and the subscripts denote the spatial mode in the interferometer. We develop a compact 3D design for the 50-spatial-mode interferometer, which simultaneously fulfills near-perfect phase stability and wave-packet overlap, full connectivity, random matrix, and near-unity transmission rate (Fig. 2C) (25). This optical network effectively consists of 300 beam splitters and 75 mirrors (see fig. S9). The transmission rate of the interferometer is measured to be 97.7%, and the average coupling efficiency in all the output ports is ~90%. We estimate the mode mismatch causes a ~0.2% drop of the interference visibility between independent photons.

Contrary to the Aaronson-Arkhipov boson sampling where the sampling matrix is given solely by the interferometer, the GBS matrix absorbs both the unitary transformation of the interferometer and the squeezing parameters and phases of the Gaussian input state. We reconstruct the corresponding unitary matrix of the spatial-polarization hybrid encoded 100 × 100 interferometer as plotted in Fig. 2, E and F for the elements of amplitudes and phases, respectively. Further analysis shows that the obtained matrix is unitary (see fig. S14) and Haar-random (see fig. S15).

We name our GBS machine Jiuzhang. We start describing the experimental results from the easy regime where we can obtain the full output distribution. We test with three pairs of input TMSSs and 2-photon click in the output. The obtained distribution is plotted in Fig. 3A. We use fidelity (F) and total variance distance (D) to characterize the obtained distribution, defined by:F=∑ipiqi−−−√F=∑ipiqi, and D = ∑i|pi – qi|/2 (pi and qi denote the theoretical and experimental probability of i-th basis, respectively). For a perfect boson-sampler, the fidelity should equal to 1 and the distance should be 0. The measured average fidelities and distances are 0.990(1) and 0.103(1). The data for all the 23 different input configurations are shown in Fig. 3B, which confirms that the GBS works properly.

Fig. 3Experimental validation of the GBS.

(A) Experimental (red) and theoretical (blue) two-photon distribution with three TMSSs input. (B) Summary of statistical fidelity and total variation distance of two-photon distribution for 23 different input sets. (C) The output photon number distribution with all 25 TMSSs in. The average detected photon number is 43, while the maximal detected photon number is 76. (D) Summary of the output state-space dimension. (E) The photon-number distributions of the experimental result (red), from thermal state (blue) and distinguishable SMSS (purple), respectively. The deviations of the line shape and peak positions indicate that our experiment is far from these two hypotheses. (F) Two-photon correlation statistics for all 2-mode combinations. The statistic of the experimental results (red) highly overlap with the theoretical predictions (orange), and deviate significantly from the thermal state hypothesis (blue) and the distinguishable SMSS hypothesis (purple). (G) Validation against thermal-state hypothesis with detected photon number ranging from 26 to 30. (H) Validation against uniform distribution.

Next we move to the sparse and intractable regime. Using 25 TMSSs input, the output photon number distribution using threshold detectors is plotted in Fig. 3C. The average click number is 43. Within 200 s, we obtain 3,097,810 events of 43-photon coincidence, and one 76-photon coincidence. The state-space dimension of our experiment is plotted in Fig. 3D, reaching up to 1030, which is 14 and 16 orders of magnitude larger than the previous experiments using superconducting qubits (8) and single photons (18).

While a full verification of the results in the large photon number regime is unlikely due to the nature of the sampling problem, we hope to provide strong evidence that the large-scale GBS continues to be governed by quantum mechanics when it reaches quantum advantage regime. The credibility of the certification processes (2732) relies on gathering circumstantial evidence while ruling out possible hypotheses plausibly to occur in this experiment. We validate the desired input TMSSs against input photons that are thermal states—which would result from excessive photon loss—and distinguishable—which would be caused by mode mismatch.

First, we compare the obtained output distribution with the hypotheses using thermal light and distinguishable SMSSs. Figure 3E shows evidently strong deviations in their line shapes and peak positions, which support that the obtain distribution indeed arises from genuine multi-photon quantum interference. Second, we investigate two-point correlation (32), which is derived from the Hanbury-Brown-Twiss experiment, to reveal the nonclassical properties of the output light field. Here, the two-point correlation between the mode i and the mode j is defined as: Ci,j=⟨Πi1Πj1⟩−⟨Πi1⟩⟨Πj1⟩Ci,j=〈Π1iΠ1j〉−〈Π1i〉〈Π1j〉, where Πi1=I−|0⟩i⟨0|iΠ1i=I−|0〉i〈0|i represent a click in mode i. We calculate the distribution of all Ci,j for the experimentally obtained samples, which is then compared with those from theoretical predictions, thermal states hypothesis and distinguishable SMSSs hypothesis. As shown in Fig. 3F, the statistics of experimental samples significantly diverges from the two hypotheses and agrees with the theoretical prediction.

Having studied the whole distribution, third, we closely look into each subspace with a specific photon click number. We develop a method called heavy output generation (HOG) ratio test (25). Figure 3G and fig. S23 shows typical examples of HOG analysis for photon clicks from 26 to 38, which show a stark difference between TMSS with thermal states. We emphasize that the tested 26-38 click regime—which shares the same setup as higher photon number—is in the post-selected subspace that effectively suffers from more photon loss than in the regime with a larger number of clicks which we deduce can be validated against the thermal state hypothesis with higher confidence.

Fourth, we continue to rule out another important hypothesis that boson sampling output would be operationally indistinguishable from a uniform random outcome, one of the earliest criticisms (27) to boson sampling. In stark contrast, due to constructive and destructive interference, an ideal boson-sampler is expected to generate samples with lognormal-like distribution (427). We develop a method (25) to reconstruct the theoretical probability distribution curve for the 40-photon case, as shown in Fig. 3H. We can match each obtained sample to the theoretical curve, as illustrated by the blue data points and vertical blue lines in Fig. 3H (see fig. S24 for more data). The frequency of occurrence of the blue lines is in a good agreement with the probability curve, which intuitively indicates that our results cannot be reproduced by a uniform sampler.

Finally, we estimate the classical computational cost to simulate an ideal GBS device. We have benchmarked the GBS on Sunway TaihuLight (21) using a highly optimized algorithm (33). The time cost to calculate one Torontonian scales exponentially as a function of output photon clicks. Moreover, to obtain one sample, one usually needs to calculate ~100 Torontonians of the candidate samples (13). The GBS simultaneously generates samples of different photon-number coincidences (Fig. 3C), which can be seen as a high-throughput sampling machine. For each output channel and the registered counts in Fig. 3C, we calculate the corresponding time cost for the supercomputer (Fig. 4). Summing over the data points in Fig. 4, we estimate that the required time cost for the TaihuLight (Fugaku) to generate the same amount of samples in 200 s with the GBS device would be 8 × 1016 s (2 × 1016 s), which is 2.5 (0.6) billion years. We hope this work will inspire new theoretical efforts to quantitatively characterize large-scale GBS, improve the classical simulation strategies optimized for the realistic parameters (3334), and challenge the observed quantum computational advantage of ~1014.

Fig. 4Classical computational cost.

The estimated time cost on Sunway TaihuLight supercomputer. The error bar is calculated from Poissonian counting statistics of the raw detected events.

References and Notes

  1. E. Bernstein, U. Vazirani, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing(1993). doi:10.1145/167088.167097Google Scholar
  2. P. W. Shor, in Proceedings of the 35th Annual Symposium on Foundations of Computer Science (1994).https://doi.org/10.1109/SFCS.1994.365700doi:doi:CrossRefPubMedWeb of ScienceGoogle Scholar
  3. B. M. Terhal, D. P. DiVincenzo, Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games. arXiv [quant-ph] (11 March 2004).pmid:0205133Google Scholar
  4. S. Aaronson, A. Arkhipov, in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing(2011). doi:10.1145/1993636.1993682Google Scholar
  5. S. Aaronson, L. Chen, in Proceedings of the 32nd Computational Complexity Conference (2017).
    1. M. J. Bremner, 
    2. A. Montanaro, 
    3. D. J. Shepherd, Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations. Phys. Rev. Lett. 117, 080501 (2016).doi:10.1103/PhysRevLett.117.080501pmid:27588839CrossRefPubMedGoogle Scholar
  6. J. Preskill, Rapporteur talk at the 25th Solvay Conference on Physics, Brussels (2012).
    1. F. Arute, 
    2. K. Arya, 
    3. R. Babbush, 
    4. D. Bacon, 
    5. J. C. Bardin, 
    6. R. Barends, 
    7. R. Biswas, 
    8. S. Boixo, 
    9. F. G. S. L. Brandao,
    10. D. A. Buell, 
    11. B. Burkett, 
    12. Y. Chen, 
    13. Z. Chen, 
    14. B. Chiaro, 
    15. R. Collins, 
    16. W. Courtney, 
    17. A. Dunsworth, 
    18. E. Farhi, 
    19. B. Foxen,
    20. A. Fowler, 
    21. C. Gidney, 
    22. M. Giustina, 
    23. R. Graff, 
    24. K. Guerin, 
    25. S. Habegger, 
    26. M. P. Harrigan, 
    27. M. J. Hartmann, 
    28. A. Ho, 
    29. M.Hoffmann, 
    30. T. Huang, 
    31. T. S. Humble, 
    32. S. V. Isakov, 
    33. E. Jeffrey, 
    34. Z. Jiang, 
    35. D. Kafri, 
    36. K. Kechedzhi, 
    37. J. Kelly, 
    38. P. V.Klimov, 
    39. S. Knysh, 
    40. A. Korotkov, 
    41. F. Kostritsa, 
    42. D. Landhuis, 
    43. M. Lindmark, 
    44. E. Lucero, 
    45. D. Lyakh, 
    46. S. Mandrà, 
    47. J. R.McClean, 
    48. M. McEwen, 
    49. A. Megrant, 
    50. X. Mi, 
    51. K. Michielsen, 
    52. M. Mohseni, 
    53. J. Mutus, 
    54. O. Naaman, 
    55. M. Neeley, 
    56. C.Neill, 
    57. M. Y. Niu, 
    58. E. Ostby, 
    59. A. Petukhov, 
    60. J. C. Platt, 
    61. C. Quintana, 
    62. E. G. Rieffel, 
    63. P. Roushan, 
    64. N. C. Rubin, 
    65. D. Sank,
    66. K. J. Satzinger, 
    67. V. Smelyanskiy, 
    68. K. J. Sung, 
    69. M. D. Trevithick, 
    70. A. Vainsencher, 
    71. B. Villalonga, 
    72. T. White, 
    73. Z. J. Yao,
    74. P. Yeh, 
    75. A. Zalcman, 
    76. H. Neven, 
    77. J. M. Martinis, Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019). doi:10.1038/s41586-019-1666-5pmid:31645734CrossRefPubMedGoogle Scholar
  7. E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, R. Wisnieff, Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits. arXiv 1910.09534 [quant-ph] (22 October 2019).
    1. A. W. Harrow, 
    2. A. Montanaro, Quantum computational supremacy. Nature 549, 203–209 (2017).doi:10.1038/nature23458pmid:28905912CrossRefPubMedGoogle Scholar
    1. C. S. Hamilton, 
    2. R. Kruse, 
    3. L. Sansoni, 
    4. S. Barkhofen, 
    5. C. Silberhorn, 
    6. I. Jex, Gaussian Boson Sampling. Phys. Rev. Lett. 119, 170501 (2017). doi:10.1103/PhysRevLett.119.170501pmid:29219463CrossRefPubMedGoogle Scholar
    1. N. Quesada, 
    2. J. M. Arrazola, 
    3. N. Killoran, Gaussian boson sampling using threshold detectors. Phys. Rev. A 98, 062322 (2018). doi:10.1103/PhysRevA.98.062322CrossRefGoogle Scholar
    1. A. Neville, 
    2. C. Sparrow, 
    3. R. Clifford, 
    4. E. Johnston, 
    5. P. M. Birchall, 
    6. A. Montanaro, 
    7. A. Laing, Classical boson sampling algorithms with superior performance to near-term experiments. Nat. Phys. 13, 1153–1157(2017). doi:10.1038/nphys4270CrossRefGoogle Scholar
  8. P. Clifford, R. Clifford, in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms(2018).
    1. M. A. Broome, 
    2. A. Fedrizzi, 
    3. S. Rahimi-Keshari, 
    4. J. Dove, 
    5. S. Aaronson, 
    6. T. C. Ralph, 
    7. A. G. White, Photonic boson sampling in a tunable circuit. Science 339, 794–798 (2013).doi:10.1126/science.1231440pmid:23258411Abstract/FREE Full TextGoogle Scholar
    1. J. B. Spring, 
    2. B. J. Metcalf, 
    3. P. C. Humphreys, 
    4. W. S. Kolthammer, 
    5. X.-M. Jin, 
    6. M. Barbieri, 
    7. A. Datta, 
    8. N.Thomas-Peter, 
    9. N. K. Langford, 
    10. D. Kundys, 
    11. J. C. Gates, 
    12. B. J. Smith, 
    13. P. G. R. Smith, 
    14. I. A. Walmsley, Boson sampling on a photonic chip. Science 339, 798–801 (2013).doi:10.1126/science.1231692pmid:23258407Abstract/FREE Full TextGoogle Scholar
    1. P. G. Kwiat, 
    2. K. Mattle, 
    3. H. Weinfurter, 
    4. A. Zeilinger, 
    5. A. V. Sergienko, 
    6. Y. Shih, New high-intensity source of polarization-entangled photon pairs. Phys. Rev. Lett. 75, 4337–4341 (1995).doi:10.1103/PhysRevLett.75.4337pmid:10059884CrossRefPubMedWeb of ScienceGoogle Scholar
    1. H. Wang, 
    2. J. Qin, 
    3. X. Ding, 
    4. M.-C. Chen, 
    5. S. Chen, 
    6. X. You, 
    7. Y.-M. He, 
    8. X. Jiang, 
    9. L. You, 
    10. Z. Wang, 
    11. C. Schneider, 
    12. J. J. Renema, 
    13. S. Höfling, 
    14. C.-Y. Lu, 
    15. J.-W. Pan, Boson Sampling with 20 Input Photons and a 60-Mode Interferometer in a 1014-Dimensional Hilbert Space. Phys. Rev. Lett. 123, 250503 (2019).doi:10.1103/PhysRevLett.123.250503pmid:31922765CrossRefPubMedGoogle Scholar
    1. J. M. Arrazola, 
    2. T. R. Bromley, Using Gaussian Boson Sampling to Find Dense Subgraphs. Phys. Rev. Lett.121, 030503 (2018). doi:10.1103/PhysRevLett.121.030503pmid:30085825CrossRefPubMedGoogle Scholar
    1. J. Huh, 
    2. G. G. Guerreschi, 
    3. B. Peropadre, 
    4. J. R. McClean, 
    5. A. Aspuru-Guzik, Boson sampling for molecular vibronic spectra. Nat. Photonics 9, 615–620 (2015). doi:10.1038/nphoton.2015.153CrossRefGoogle Scholar
  9. X. Li et al., Benchmarking 50-Photon Gaussian Boson Sampling on the Sunway TaihuLight. arXiv2009.01177 [cs.DC] (2 September 2020).
    1. H.-S. Zhong, 
    2. L.-C. Peng, 
    3. Y. Li, 
    4. Y. Hu, 
    5. W. Li, 
    6. J. Qin, 
    7. D. Wu, 
    8. W. Zhang, 
    9. H. Li, 
    10. L. Zhang, 
    11. Z. Wang, 
    12. L. You, 
    13. X.Jiang, 
    14. L. Li, 
    15. N.-L. Liu, 
    16. J. P. Dowling, 
    17. C.-Y. Lu, 
    18. J.-W. Pan, Experimental Gaussian Boson sampling. Sci. Bull. 64,511–515 (2019). doi:10.1016/j.scib.2019.04.007CrossRefGoogle Scholar
    1. S. Paesani, 
    2. Y. Ding, 
    3. R. Santagati, 
    4. L. Chakhmakhchyan, 
    5. C. Vigliar, 
    6. K. Rottwitt, 
    7. L. K. Oxenløwe, 
    8. J. Wang, 
    9. M. G. Thompson, 
    10. A. Laing, Generation and sampling of quantum states of light in a silicon chip. Nat. Phys. 15,925–929 (2019). doi:10.1038/s41567-019-0534-4CrossRefGoogle Scholar
    1. A. Christ, 
    2. K. Laiho, 
    3. A. Eckstein, 
    4. K. N. Cassemiro, 
    5. C. Silberhorn, Probing multimode squeezing with correlation functions. New J. Phys. 13, 033027 (2011). doi:10.1088/1367-2630/13/3/033027CrossRefGoogle Scholar
  10. See supplementary materials.
    1. I. Dhand, 
    2. S. K. Goyal, Realization of arbitrary discrete unitary transformations using spatial and internal modes of light. Phys. Rev. A 92, 043813 (2015). doi:10.1103/PhysRevA.92.043813CrossRefGoogle Scholar
    1. S. Aaronson, 
    2. A. Arkhipov, BosonSampling is far from uniform. Quantum Inf. Comput. 14, 1383 (2014).CrossRefPubMedGoogle Scholar
    1. M. C. Tichy, 
    2. K. Mayer, 
    3. A. Buchleitner, 
    4. K. Mølmer, Stringent and efficient assessment of boson-sampling devices. Phys. Rev. Lett. 113, 020502 (2014). doi:10.1103/PhysRevLett.113.020502pmid:25062152CrossRefPubMedGoogle Scholar
    1. M. Walschaers, 
    2. J. Kuipers, 
    3. J.-D. Urbina, 
    4. K. Mayer, 
    5. M. C. Tichy, 
    6. K. Richter, 
    7. A. Buchleitner, Statistical benchmark for BosonSampling. New J. Phys. 18, 032001 (2016). doi:10.1088/1367-2630/18/3/032001CrossRefGoogle Scholar
    1. N. Spagnolo, 
    2. C. Vitelli, 
    3. M. Bentivegna, 
    4. D. J. Brod, 
    5. A. Crespi, 
    6. F. Flamini, 
    7. S. Giacomini, 
    8. G. Milani, 
    9. R. Ramponi, 
    10. P.Mataloni, 
    11. R. Osellame, 
    12. E. F. Galvão, 
    13. F. Sciarrino, Experimental validation of photonic boson sampling. Nat. Photonics 8, 615–620 (2014). doi:10.1038/nphoton.2014.135CrossRefGoogle Scholar
    1. J. Carolan, 
    2. J. D. A. Meinecke, 
    3. P. J. Shadbolt, 
    4. N. J. Russell, 
    5. N. Ismail, 
    6. K. Wörhoff, 
    7. T. Rudolph, 
    8. M. G.Thompson, 
    9. J. L. O’Brien, 
    10. J. C. F. Matthews, 
    11. A. Laing, On the experimental verification of quantum complexity in linear optics. Nat. Photonics 8, 621–626 (2014). doi:10.1038/nphoton.2014.152CrossRefGoogle Scholar
    1. D. S. Phillips, 
    2. M. Walschaers, 
    3. J. J. Renema, 
    4. I. A. Walmsley, 
    5. N. Treps, 
    6. J. Sperling, Benchmarking of Gaussian boson sampling using two-point correlators. Phys. Rev. A 99, 023836 (2019).doi:10.1103/PhysRevA.99.023836CrossRefGoogle Scholar
    1. N. Quesada, 
    2. J. M. Arrazola, Exact simulation of Gaussian boson sampling in polynomial space and exponential time. Phys. Rev. Res. 2, 023005 (2020). doi:10.1103/PhysRevResearch.2.023005CrossRefPubMedGoogle Scholar
    1. H. Qi, 
    2. D. J. Brod, 
    3. N. Quesada, 
    4. R. García-Patrón, Regimes of Classical Simulability for Noisy Gaussian Boson Sampling. Phys. Rev. Lett. 124, 100502 (2020).doi:10.1103/PhysRevLett.124.100502pmid:32216428CrossRefPubMedGoogle Scholar
  11. S. M. Barnett, P. M. Radmore, Methods in Theoretical Quantum Optics (Oxford Science, 1997).
    1. W. P. Grice, 
    2. A. B. U’Ren, 
    3. I. A. Walmsley, Eliminating frequency and space-time correlations in multiphoton states. Phys. Rev. A 64, 063815 (2001). doi:10.1103/PhysRevA.64.063815CrossRefPubMedGoogle Scholar
    1. P. B. Dixon, 
    2. J. H. Shapiro, 
    3. F. N. C. Wong, Spectral engineering by Gaussian phase-matching for quantum photonics. Opt. Express 21, 5879–5890 (2013). doi:10.1364/OE.21.005879pmid:23482156CrossRefPubMedGoogle Scholar
    1. S. Rahimi-Keshari, 
    2. M. A. Broome, 
    3. R. Fickler, 
    4. A. Fedrizzi, 
    5. T. C. Ralph, 
    6. A. G. White, Direct characterization of linear-optical networks. Opt. Express 21, 13450–13458 (2013).doi:10.1364/OE.21.013450pmid:23736598CrossRefPubMedGoogle Scholar
    1. H. Wang, 
    2. Y. He, 
    3. Y.-H. Li, 
    4. Z.-E. Su, 
    5. B. Li, 
    6. H.-L. Huang, 
    7. X. Ding, 
    8. M.-C. Chen, 
    9. C. Liu, 
    10. J. Qin, 
    11. J.-P. Li, 
    12. Y.-M. He, 
    13. C.Schneider, 
    14. M. Kamp, 
    15. C.-Z. Peng, 
    16. S. Höfling, 
    17. C.-Y. Lu, 
    18. J.-W. Pan, High-efficiency multiphoton boson sampling.Nat. Photonics 11, 361–365 (2017). doi:10.1038/nphoton.2017.63CrossRefGoogle Scholar
    1. W. J. Zhang, 
    2. L. X. You, 
    3. H. Li, 
    4. J. Huang, 
    5. C. L. Lv, 
    6. L. Zhang, 
    7. X. Y. Liu, 
    8. J. J. Wu, 
    9. Z. Wang, 
    10. X. M. Xie, NbN superconducting nanowire single photon detector with efficiency over 90% at 1550 nm wavelength operational at compact cryocooler temperature. Sci. China Phys. Mech. Astron. 60, 120314 (2017).doi:10.1007/s11433-017-9113-4CrossRefPubMedGoogle Scholar
    1. S. Rahimi-Keshari, 
    2. A. P. Lund, 
    3. T. C. Ralph, What can quantum optics say about computational complexity theory? Phys. Rev. Lett. 114, 060501 (2015). doi:10.1103/PhysRevLett.114.060501pmid:25723196CrossRefPubMedWeb of ScienceGoogle Scholar
    1. M. Tillmann, 
    2. B. Dakić, 
    3. R. Heilmann, 
    4. S. Nolte, 
    5. A. Szameit, 
    6. P. Walther, Experimental boson sampling. Nat. Photonics 7, 540–544 (2013). doi:10.1038/nphoton.2013.102CrossRefWeb of ScienceGoogle Scholar
    1. A. Crespi, 
    2. R. Osellame, 
    3. R. Ramponi, 
    4. D. J. Brod, 
    5. E. F. Galvão, 
    6. N. Spagnolo, 
    7. C. Vitelli, 
    8. E. Maiorino, 
    9. P. Mataloni,
    10. F. Sciarrino, Integrated multimode interferometers with arbitrary designs for photonic boson sampling. Nat. Photonics 7, 545–549 (2013). doi:10.1038/nphoton.2013.112Abstract/FREE Full TextGoogle Scholar
    1. J. Carolan, 
    2. C. Harrold, 
    3. C. Sparrow, 
    4. E. Martín-López, 
    5. N. J. Russell, 
    6. J. W. Silverstone, 
    7. P. J. Shadbolt, 
    8. N.Matsuda, 
    9. M. Oguma, 
    10. M. Itoh, 
    11. G. D. Marshall, 
    12. M. G. Thompson, 
    13. J. C. F. Matthews, 
    14. T. Hashimoto, 
    15. J. L. O’Brien,
    16. A. Laing, Universal linear optics. Science 349, 711–716 (2015).doi:10.1126/science.aab3642pmid:26160375CrossRefPubMedGoogle Scholar
    1. Y. He, 
    2. X. Ding, 
    3. Z.-E. Su, 
    4. H.-L. Huang, 
    5. J. Qin, 
    6. C. Wang, 
    7. S. Unsleber, 
    8. C. Chen, 
    9. H. Wang, 
    10. Y.-M. He, 
    11. X.-L. Wang, 
    12. W.-J. Zhang, 
    13. S.-J. Chen, 
    14. C. Schneider, 
    15. M. Kamp, 
    16. L.-X. You, 
    17. Z. Wang, 
    18. S. Höfling, 
    19. C.-Y. Lu, 
    20. J.-W. Pan, Time-Bin-Encoded Boson Sampling with a Single-Photon Device. Phys. Rev. Lett. 118, 190501 (2017).doi:10.1103/PhysRevLett.118.190501pmid:28548532CrossRefPubMedGoogle Scholar
    1. J. C. Loredo, 
    2. M. A. Broome, 
    3. P. Hilaire, 
    4. O. Gazzano, 
    5. I. Sagnes, 
    6. A. Lemaitre, 
    7. M. P. Almeida, 
    8. P. Senellart, 
    9. A. G.White, Boson Sampling with Single-Photon Fock States from a Bright Solid-State Source. Phys. Rev. Lett.118, 130503 (2017). doi:10.1103/PhysRevLett.118.130503pmid:28409950CrossRefPubMedGoogle Scholar
    1. H. Wang, 
    2. W. Li, 
    3. X. Jiang, 
    4. Y.-M. He, 
    5. Y.-H. Li, 
    6. X. Ding, 
    7. M.-C. Chen, 
    8. J. Qin, 
    9. C.-Z. Peng, 
    10. C. Schneider, 
    11. M. Kamp, 
    12. W.-J. Zhang, 
    13. H. Li, 
    14. L.-X. You, 
    15. Z. Wang, 
    16. J. P. Dowling, 
    17. S. Höfling, 
    18. C.-Y. Lu, 
    19. J.-W. Pan, Toward Scalable Boson Sampling with Photon Loss. Phys. Rev. Lett. 120, 230502 (2018).doi:10.1103/PhysRevLett.120.230502pmid:29932715FREE Full TextGoogle Scholar
    1. M. Bentivegna, 
    2. N. Spagnolo, 
    3. C. Vitelli, 
    4. F. Flamini, 
    5. N. Viggianiello, 
    6. L. Latmiral, 
    7. P. Mataloni, 
    8. D. J. Brod, 
    9. E. F.Galvão, 
    10. A. Crespi, 
    11. R. Ramponi, 
    12. R. Osellame, 
    13. F. Sciarrino, Experimental scattershot boson sampling. Sci. Adv.1, e1400255 (2015). doi:10.1126/sciadv.1400255pmid:26601164CrossRefPubMedGoogle Scholar
    1. H.-S. Zhong, 
    2. Y. Li, 
    3. W. Li, 
    4. L.-C. Peng, 
    5. Z.-E. Su, 
    6. Y. Hu, 
    7. Y.-M. He, 
    8. X. Ding, 
    9. W. Zhang, 
    10. H. Li, 
    11. L. Zhang, 
    12. Z. Wang, 
    13. L.You, 
    14. X.-L. Wang, 
    15. X. Jiang, 
    16. L. Li, 
    17. Y.-A. Chen, 
    18. N.-L. Liu, 
    19. C.-Y. Lu, 
    20. J.-W. Pan, 12-Photon Entanglement and Scalable Scattershot Boson Sampling with Optimal Entangled-Photon Pairs from Parametric Down-Conversion. Phys. Rev. Lett. 121, 250505 (2018). doi:10.1103/PhysRevLett.121.250505pmid:30608840CrossRefPubMedGoogle Scholar
    1. I. Agresti, N. Viggianiello, F. Flamini, N. Spagnolo, A. Crespi, R. Osellame, N. Wiebe, F. Sciarrino, Pattern Recognition Techniques for Boson Sampling Validation. Phys. Rev. X 9, 011013 (2019).doi:10.1103/PhysRevX.9.011013CrossRefPubMedGoogle Scholar

Via https://science.sciencemag.org/content/early/2020/12/02/science.abe8770