Boson Sampling from a Gaussian State
Open accessThe DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
Abstract
We pose a randomized boson-sampling problem. Strong evidence exists that such a problem becomes intractable on a classical computer as a function of the number of bosons. We describe a quantum optical processor that can solve this problem efficiently based on a Gaussian input state, a linear optical network, and nonadaptive photon counting measurements. All the elements required to build such a processor currently exist. The demonstration of such a device would provide empirical evidence that quantum computers can, indeed, outperform classical computers and could lead to applications.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Quantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
Quantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 18,842
A scheme for efficient quantum computation with linear optics
Knill, E., Laflamme, R., & Milburn, G. J. (2001) · Nature · doi:10.1038/35051009 · Cited by 5,880
The complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705
Stockmeyer, L. J. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90061-x · Cited by 1,293
Quantum Walks of Correlated Photons
Peruzzo, A., Lobino, M., Matthews, J. C. F., Matsuda, N., Politi, A., Poulios, K., Zhou, X.-Q., Lahini, Y., Ismail, N., Wörhoff, K., et al. (2010) · Science · doi:10.1126/science.1193515 · Cited by 929
Self-citationBoson Sampling on a Photonic Chip
Spring, J. B., Metcalf, B. J., Humphreys, P. C., Kolthammer, W. S., Jin, X.-M., Barbieri, M., Datta, A., Thomas-Peter, N., Langford, N. K., Kundys, D., et al. (2013) · Science · doi:10.1126/science.1231692 · Cited by 837
A Guide to Experiments in Quantum Optics
(2004) · Wiley eBooks · doi:10.1002/9783527619238 · Cited by 760
Tillmann, M., Dakić, B., Heilmann, R., Nolte, S., Szameit, A., & Walther, P. (2013) · Nature Photonics · doi:10.1038/nphoton.2013.102 · Cited by 709
Integrated multimode interferometers with arbitrary designs for photonic boson sampling
Crespi, A., Osellame, R., Ramponi, R., Brod, D. J., Galvão, E. F., Spagnolo, N., Vitelli, C., Maiorino, E., Mataloni, P., & Sciarrino, F. (2013) · Nature Photonics · doi:10.1038/nphoton.2013.112 · Cited by 662
Cited by
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J. P., Degroote, M., Johnson, P. D., Kieferová, M., Kivlichan, I. D., Menke, T., Peropadre, B., Sawaya, N. P. D., et al. (2019) · Chemical Reviews · doi:10.1021/acs.chemrev.8b00803 · Cited by 1,560
Quantum information processing with superconducting circuits: a review
Wendin, G. (2017) · Reports on Progress in Physics · doi:10.1088/1361-6633/aa7e1a · Cited by 890
Photonic quantum information processing: a review
Flamini, F., Spagnolo, N., & Sciarrino, F. (2019) · Reports on Progress in Physics · doi:10.1088/1361-6633/aad5b2 · Cited by 770
Photonic quantum information processing: a concise review
Slussarenko, S., & Pryde, G. J. (2019) · Applied Physics Reviews · doi:10.1063/1.5115814 · Cited by 644
Quantum circuits with many photons on a programmable nanophotonic chip
Arrazola, J. M., Bergholm, V., Brádler, K., Bromley, T. R., Collins, M. J., Dhand, I., Fumagalli, A., Gerrits, T., Goussev, A., Helt, L. G., et al. (2021) · Nature · doi:10.1038/s41586-021-03202-1 · Cited by 567
Experimental Ten-Photon Entanglement
Wang, X.-L., Chen, L.-K., Li, W., Huang, H.-L., Liu, C., Chen, C., Luo, Y.-H., Su, Z.-E., Wu, D., Li, Z.-D., et al. (2016) · Physical Review Letters · doi:10.1103/physrevlett.117.210502 · Cited by 549
The potential and global outlook of integrated photonics for quantum technologies
Pelucchi, E., Fagas, G., Aharonovich, I., Englund, D., Figueroa, E., Gong, Q., Hannes, H., Liu, J., Lu, C.-Y., Matsuda, N., et al. (2021) · Nature Reviews Physics · doi:10.1038/s42254-021-00398-z · Cited by 533
Hamilton, C. S., Kruse, R., Sansoni, L., Barkhofen, S., Silberhorn, C., & Jex, I. (2017) · Physical Review Letters · doi:10.1103/physrevlett.119.170501 · Cited by 503
“This is fundamentally different to the selection process with single photons, where input and output pattern define the selection [1, 2, 5].”
BackgroundPhase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
Zhong, H.-S., Deng, Y.-H., Qin, J., Wang, H., Chen, M.-C., Peng, L.-C., Luo, Y.-H., Wu, D., Gong, S.-Q., Su, H., et al. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.180502 · Cited by 434
Zhong, H.-S., Li, Y., Li, W., Peng, L.-C., Su, Z.-E., Hu, Y., He, Y.-M., Ding, X., Zhang, W., Li, H., et al. (2018) · Physical Review Letters · doi:10.1103/physrevlett.121.250505 · Cited by 432
High-efficiency multiphoton boson sampling
Wang, H., He, Y., Li, Y.-H., Su, Z.-E., Li, B., Huang, H.-L., Ding, X., Chen, M.-C., Liu, C., Qin, J., et al. (2017) · Nature Photonics · doi:10.1038/nphoton.2017.63 · Cited by 418
Continuous-variable quantum neural networks
Killoran, N., Bromley, T. R., Arrazola, J. M., Schuld, M., Quesada, N., & Lloyd, S. (2019) · Physical Review Research · doi:10.1103/physrevresearch.1.033063 · Cited by 418
Boson sampling for molecular vibronic spectra
Huh, J., Guerreschi, G. G., Peropadre, B., McClean, J. R., & Aspuru-Guzik, A. (2015) · Nature Photonics · doi:10.1038/nphoton.2015.153 · Cited by 341
Strawberry Fields: A Software Platform for Photonic Quantum Computing
Killoran, N., Izaac, J., Quesada, N., Bergholm, V., Amy, M., & Weedbrook, C. (2019) · Quantum · doi:10.22331/q-2019-03-11-129 · Cited by 323
Experimental scattershot boson sampling
Bentivegna, M., Spagnolo, N., Vitelli, C., Flamini, F., Viggianiello, N., Latmiral, L., Mataloni, P., Brod, D. J., Galvão, E. F., Crespi, A., et al. (2015) · Science Advances · doi:10.1126/sciadv.1400255 · Cited by 239
Two-photon interference: the Hong–Ou–Mandel effect
Bouchard, F., Sit, A., Zhang, Y., Fickler, R., Miatto, F. M., Yao, Y., Sciarrino, F., & Karimi, E. (2021) · Reports on Progress in Physics · doi:10.1088/1361-6633/abcd7a · Cited by 232
“Because of the complexity of this topic and as well as the enormous attention and progress that has been done over the last few years [168–175], boson sampling would justify a review on its own and we refrain from discussing it in more detail.”
BackgroundOn the experimental verification of quantum complexity in linear optics
Carolan, J., Meinecke, J. D. A., Shadbolt, P. J., Russell, N. J., Ismail, N., Wörhoff, K., Rudolph, T., Thompson, M. G., O'Brien, J. L., Matthews, J. C. F., et al. (2014) · Nature Photonics · doi:10.1038/nphoton.2014.152 · Cited by 221
Self-citationGeneration and sampling of quantum states of light in a silicon chip
Paesani, S., Ding, Y., Santagati, R., Chakhmakhchyan, L., Vigliar, C., Rottwitt, K., Oxenløwe, L. K., Wang, J., Thompson, M. G., & Laing, A. (2019) · Nature Physics · doi:10.1038/s41567-019-0567-8 · Cited by 214
Self-citationApplications of single photons to quantum communication and computing
Couteau, C., Barz, S., Durt, T., Gerrits, T., Huwer, J., Prevedel, R., Rarity, J., Shields, A., & Weihs, G. (2023) · Nature Reviews Physics · doi:10.1038/s42254-023-00583-2 · Cited by 216
“Other variants are driven boson sampling 194 and Gaussian boson sampling 195–197 .”
BackgroundBoson Sampling with Single-Photon Fock States from a Bright Solid-State Source
Loredo, J. C., Broome, M. A., Hilaire, P., Gazzano, O., Sagnes, I., Lemaitre, A., Almeida, M. P., Senellart, P., & White, A. G. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.130503 · Cited by 194
Detailed study of Gaussian boson sampling
Kruse, R., Hamilton, C. S., Sansoni, L., Barkhofen, S., Silberhorn, C., & Jex, I. (2019) · Physical Review A · doi:10.1103/physreva.100.032326 · Cited by 180
Photonic implementation of boson sampling: a review
Brod, D. J., Galvão, E. F., Crespi, A., Osellame, R., Spagnolo, N., & Sciarrino, F. (2019) · Advanced Photonics · doi:10.1117/1.ap.1.3.034001 · Cited by 159
Computational advantage of quantum random sampling
Hangleiter, D., & Eisert, J. (2023) · Reviews of Modern Physics · doi:10.1103/revmodphys.95.035001 · Cited by 145
Gaussian boson sampling using threshold detectors
Quesada, N., Arrazola, J. M., & Killoran, N. (2018) · Physical Review A · doi:10.1103/physreva.98.062322 · Cited by 120
Integrated Source of Spectrally Filtered Correlated Photons for Large-Scale Quantum Photonic Systems
Harris, N. C., Grassani, D., Simbula, A., Pant, M., Galli, M., Baehr-Jones, T., Hochberg, M., Englund, D., Bajoni, D., & Galland, C. (2014) · Physical Review X · doi:10.1103/physrevx.4.041047 · Cited by 115
Chip-based array of near-identical, pure, heralded single-photon sources
Spring, J. B., Mennea, P. L., Metcalf, B. J., Humphreys, P. C., Gates, J. C., Rogers, H. L., Söller, C., Smith, B. J., Kolthammer, W. S., Smith, P. G. R., et al. (2017) · Optica · doi:10.1364/optica.4.000090 · Cited by 105
Partial indistinguishability theory for multiphoton experiments in multiport devices
Shchesnovich, V. S. (2015) · Physical Review A · doi:10.1103/physreva.91.013844 · Cited by 104
Classical simulation of photonic linear optics with lost particles
Oszmaniec, M., & Brod, D. J. (2018) · New Journal of Physics · doi:10.1088/1367-2630/aadfa8 · Cited by 89
The boundary for quantum advantage in Gaussian boson sampling
Bulmer, J. F. F., Bell, B. A., Chadwick, R. S., Jones, A. E., Moise, D., Rigazzi, A., Thorbecke, J., Haus, U.-U., Van Vaerenbergh, T., Patel, R. B., et al. (2022) · Science Advances · doi:10.1126/sciadv.abl9236 · Cited by 88
“D’Elía, MPI for Python: Performance improvements and MPI-2 extensions. J. Parallel Distrib. Comput. 68, 655–662 (2008).”
Self-citationRegimes of Classical Simulability for Noisy Gaussian Boson Sampling
Qi, H., Brod, D. J., Quesada, N., & García-Patrón, R. (2020) · Physical Review Letters · doi:10.1103/physrevlett.124.100502 · Cited by 87
Experimental Gaussian Boson sampling
Zhong, H.-S., Peng, L.-C., Li, Y., Hu, Y., Li, W., Qin, J., Wu, D., Zhang, W., Li, H., Zhang, L., et al. (2019) · Science Bulletin · doi:10.1016/j.scib.2019.04.007 · Cited by 73
Continuous-Variable Instantaneous Quantum Computing is Hard to Sample
Douce, T., Markham, D., Kashefi, E., Diamanti, E., Coudreau, T., Milman, P., van Loock, P., & Ferrini, G. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.070503 · Cited by 64
Huh, J., & Yung, M.-H. (2017) · Scientific Reports · doi:10.1038/s41598-017-07770-z · Cited by 63
Reconfigurable continuously-coupled 3D photonic circuit for Boson Sampling experiments
Hoch, F., Piacentini, S., Giordani, T., Tian, Z.-N., Iuliano, M., Esposito, C., Camillini, A., Carvacho, G., Ceccarelli, F., Spagnolo, N., et al. (2022) · npj Quantum Information · doi:10.1038/s41534-022-00568-6 · Cited by 51
Pattern Recognition Techniques for Boson Sampling Validation
Agresti, I., Viggianiello, N., Flamini, F., Spagnolo, N., Crespi, A., Osellame, R., Wiebe, N., & Sciarrino, F. (2019) · Physical Review X · doi:10.1103/physrevx.9.011013 · Cited by 50
Quadratic Speed-Up for Simulating Gaussian Boson Sampling
Quesada, N., Chadwick, R. S., Bell, B. A., Arrazola, J. M., Vincent, T., Qi, H., & García−Patrón, R. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.010306 · Cited by 48
Proposal for Microwave Boson Sampling
Peropadre, B., Guerreschi, G. G., Huh, J., & Aspuru-Guzik, A. (2016) · Physical Review Letters · doi:10.1103/physrevlett.117.140505 · Cited by 44
Seshadreesan, K. P., Olson, J. P., Motes, K. R., Rohde, P. P., & Dowling, J. P. (2015) · Physical Review A · doi:10.1103/physreva.91.022334 · Cited by 41
Efficient verification of boson sampling
Chabaud, U., Grosshans, F., Kashefi, E., & Markham, D. (2021) · Quantum · doi:10.22331/q-2021-11-15-578 · Cited by 37
“Similarly in the context of infinite-dimensional Hilbert spaces [39], which includes Boson Sampling and related sub-universal models [10, 40, 41, 42, 43, 44, 45], this minimal quantum capability corresponds to being only able to prepare single-mode Gaussian states, or to perform single-mode Gaussian measurements.”
BackgroundThe Capacity of Quantum Neural Networks
Wright, L. G., & McMahon, P. L. (2019) · arXiv · doi:10.48550/arxiv.1908.01364 · Cited by 35
Optimal photonic indistinguishability tests in multimode networks
Viggianiello, N., Flamini, F., Bentivegna, M., Spagnolo, N., Crespi, A., Brod, D. J., Galvão, E. F., Osellame, R., & Sciarrino, F. (2018) · Science Bulletin · doi:10.1016/j.scib.2018.10.009 · Cited by 18
Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
Rajakumar, J., Watson, J. D., & Liu, Y.-K. (2025) · Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611978322.30 · Cited by 7
Metadata
- Authors
- Lund, A. P., Laing, A., Rahimi-Keshari, S., Rudolph, T., O’Brien, J. L., & Ralph, T. C.
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2014-09-05
- Volume
- 113
- Issue
- 10
- Pages
- 100502-100502
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W1993797543
- Cited by
- 303
- References
- 17
- FWCI
- 26.08
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.