Gaussian Boson Sampling
Open accessAbstract
Boson sampling has emerged as a tool to explore the advantages of quantum over classical computers as it does not require universal control over the quantum system, which favors current photonic experimental platforms. Here, we introduce Gaussian Boson sampling, a classically hard-to-solve problem that uses squeezed states as a nonclassical resource. We relate the probability to measure specific photon patterns from a general Gaussian state in the Fock basis to a matrix function called the Hafnian, which answers the last remaining question of sampling from Gaussian states. Based on this result, we design Gaussian Boson sampling, a #P hard problem, using squeezed states. This demonstrates that Boson sampling from Gaussian states is possible, with significant advantages in the photon generation probability, compared to existing protocols.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Gaussian states have the advantage that they can be created deterministically.
“Gaussian states have the advantage that they can be created deterministically (Hamilton et al. , 2017; Kruse et al. , 2019).”
From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Hamilton et al., 2017
GBS is computationally equivalent to sampling from the Hafnian function of a matrix.
“Where boson sampling is equivalent to sampling from the permanent of a matrix, GBS is computationally equivalent to sampling from the Hafnian function of a matrix.”
From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Hamilton et al., 2017
Gaussian boson sampling is a variant of boson sampling in which Gaussian states are used as inputs to the optical circuit.
“Gaussian boson sampling (GBS) is a variant of boson sampling, in which instead of photon states as inputs to the optical circuit, Gaussian states are used as inputs (Hamilton et al. , 2017).”
From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Hamilton et al., 2017
Gaussian boson sampling is a special-purpose photonic platform to perform sampling tasks that are classically intractable.
“Gaussian boson sampling, however, is a special-purpose photonic platform to perform sampling tasks that are classically intractable [186].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [186]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Negative Binomial Regression: Index
Hilbe, J. (2007) · Cambridge University Press eBooks · doi:10.1017/cbo9780511973420 · Cited by 3,253 · see citing works
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 · see citing works
Boson 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 · see citing works
Tillmann, M., Dakić, B., Heilmann, R., Nolte, S., Szameit, A., & Walther, P. (2013) · Nature Photonics · doi:10.1038/nphoton.2013.102 · Cited by 709 · see citing works
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 · see citing works
Photonic Boson Sampling in a Tunable Circuit
Broome, M. A., Fedrizzi, A., Rahimi-Keshari, S., Dove, J., Aaronson, S., Ralph, T. C., & White, A. G. (2013) · Science · doi:10.1126/science.1231440 · Cited by 634 · see citing works
Quantum-noise matrix for multimode systems: U(n) invariance, squeezing, and normal forms
Simon, R., Mukunda, N., & Dutta, B. (1994) · Physical Review A · doi:10.1103/physreva.49.1567 · Cited by 466 · see citing works
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 421 · see citing works
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 · see citing works
Boson Sampling from a Gaussian State
Lund, A. P., Laing, A., Rahimi-Keshari, S., Rudolph, T., O’Brien, J. L., & Ralph, T. C. (2014) · Physical Review Letters · doi:10.1103/physrevlett.113.100502 · Cited by 301 · see citing works
Gaussian states in continuous variable quantum informationPreprint
Ferraro, A., Olivares, S., & Paris, M. G. A. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0503237 · Cited by 238 · see citing works
Boson Sampling with Single-Photon Fock States from a Bright Solid-State Source
Loredo, J. C., Broome, M. A., Hilaire, P., Gazzano, O., Sagnes, I., Lemaître, A., de Almeida, M. P., Senellart, P., & White, A. G. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.130503 · Cited by 202 · see citing works
Time-Bin-Encoded Boson Sampling with a Single-Photon Device
He, Y., Ding, X., Su, Z.-E., Huang, H.-L., Qin, J., Wang, C., Unsleber, S., Chen, C., Wang, H., He, Y.-M., et al. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.190501 · Cited by 174 · see citing works
Caianiello, E. R. (1953) · Il Nuovo Cimento · doi:10.1007/bf02781659 · Cited by 136 · see citing works
From moments of sum to moments of product
Kan, R. (2007) · Journal of Multivariate Analysis · doi:10.1016/j.jmva.2007.01.013 · Cited by 131 · see citing works
Combinatorics and Renormalization in Quantum Field Theory
Caianiello, E. R. (1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 128 · see citing works
Photon distribution for one-mode mixed light with a generic Gaussian Wigner function
Dodonov, V. V., Man’ko, O. V., & Man’ko, V. I. (1994) · Physical Review A · doi:10.1103/physreva.49.2993 · Cited by 111 · see citing works
Multidimensional Hermite polynomials and photon distribution for polymode mixed light
Dodonov, V. V., Man’ko, O. V., & Man’ko, V. I. (1994) · Physical Review A · doi:10.1103/physreva.50.813 · Cited by 104 · see citing works
Two Algorithmic Results for the Traveling Salesman Problem
Barvinok, A. I. (1996) · Mathematics of Operations Research · doi:10.1287/moor.21.1.65 · Cited by 103 · see citing works
Permanents in linear optical networks
Scheel, S. (2004) · arXiv · doi:10.48550/arxiv.quant-ph/0406127 · Cited by 94 · see citing works
What Can Quantum Optics Say about Computational Complexity Theory?
Rahimi-Keshari, S., Lund, A. P., & Ralph, T. C. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.060501 · Cited by 87 · see citing works
BosonSampling with lost photons
Aaronson, S., & Brod, D. J. (2016) · Physical Review A · doi:10.1103/physreva.93.012335 · Cited by 78 · see citing works
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 · see citing works
Olson, J. P., Seshadreesan, K. P., Motes, K. R., Rohde, P. P., & Dowling, J. P. (2015) · Physical Review A · doi:10.1103/physreva.91.022317 · Cited by 48 · see citing works
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 · see citing works
Multiboson correlation interferometry with multimode thermal sources
Tamma, V., & Laibacher, S. (2014) · Physical Review A · doi:10.1103/physreva.90.063836 · Cited by 31 · see citing works
Barkhofen, S., Bartley, T. J., Sansoni, L., Kruse, R., Hamilton, C. S., Jex, I., & Silberhorn, C. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.020502 · Cited by 31 · see citing works
Self-citationEvidence for the conjecture that sampling generalized cat states with linear optics is hard
Rohde, P. P., Motes, K. R., Knott, P., Fitzsimons, J. F., Munro, W. J., & Dowling, J. P. (2015) · Physical Review A · doi:10.1103/physreva.91.012342 · Cited by 28 · see citing works
Exact boson sampling using Gaussian continuous-variable measurements
Lund, A. P., Rahimi-Keshari, S., & Ralph, T. C. (2017) · Physical Review A · doi:10.1103/physreva.96.022301 · Cited by 28 · see citing works
The entries of circular orthogonal ensembles
Jiang, T. (2009) · Journal of Mathematical Physics · doi:10.1063/1.3152217 · Cited by 17 · see citing works
Multi-photon boson-sampling machines beating early classical computersPreprint
Hui, W., He, Y., Li, Y.-H., Su, Z.-E., Li, B., Huang, H.-L., Ding, X., Chen, M.-C., Chang, L., Qin, J., et al. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1612.06956 · Cited by 9 · see citing works
Scalable boson sampling with a single-photon devicePreprint
He, Y., Su, Z.-E., Huang, H.-L., Ding, X., Qin, J., Wang, C., Unsleber, S., Chen, C., Wang, H., He, Y.-M., et al. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1603.04127 · Cited by 3 · see citing works
Flagged first, then by citations
Research works printed but not linked: 25
- [1]1. S. Aaronson and A. Arkhipov, Theory of Comput. 9, 143 (2013).
- [2]2. L. Valiant, Theoretical computer science 8, 189 (1979).
- [3]3. M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White, Science 339, 794 (2013).
- [4]4. M. Tillmann, B. Dakić, R. Heilmann, S. Nolte, A. Sza- meit, and P. Walther, Nature Photon 7, 540 (2013).
- [5]5. J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X.-M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walm- sley, Science 339, 798 (2013).
- [6]6. A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. G. ao, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino, Nature Photonics 7, 545 (2013).
- [9]9. J. Loredo, M. Broome, P. Hilaire, O. Gazzano, I. Sagnes, A. Lemaitre, M. Almeida, P. Senellart, and A. White, Physical Review Letters 118, 130503 (2017).
- [10]10. A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O'Brien, and T. C. Ralph, Physical Review Letters 113, 100502 (2014).
- [11]11. S. Barkhofen, T. J. Bartley, L. Sansoni, R. Kruse, C. S. Hamilton, I. Jex, and C. Silberhorn, Physical Review Letters 118, 020502 (2017).
- [12]12. J. Huh, G. G. Guerreschi, B. Peropadre, J. R. Mcclean, and A. Aspuru-Guzik, Nature Photonics 9, 615 (2015).
- [13]13. S. Rahimi-Keshari, A. P. Lund, and T. C. Ralph, Phys- ical Review Letters 114, 060501 (2015).
- [14]14. V. Tamma and S. Laibacher, Physical Review A 90, 063836 (2014).
- [18]18. V. V. Dodonov, O. V. Man'ko, and V. I. Man'ko, Phys- ical Review A 49, 2993 (1994).
- [19]19. V. V. Dodonov, O. V. Man'ko, and V. I. Man'ko, Phys- ical Review A 50, 813 (1994).
- [20]20. D. Callan, arXiv math.CO (2009), 0906.1317v1.
- [22]22. E. R. Caianiello, Il Nuovo Cimento 10, 1 (1953).
- [24]24. H. Minc, Permanents (Addison-Wesley, 1978).
- [25]25. P. Sankowski, in Annual Symposium on Theoretical As- pects of Computer Science (Springer, 2003) pp. 427-438.
- [28]28. R. Simon, N. Mukunda, and B. Dutta, Physical Review A 49, 1567 (1994).
- [30]30. M. L. Mehta, Random Matrices (Elsevier, 2004).
- [32]32. J. M. Hilbe, Negative Binomial Regression (Cambridge University Press, 2011).
- [33]33. P. P. Rohde, K. R. Motes, P. A. Knott, J. Fitzsimons, W. J. Munro, and J. P. Dowling, Physical Review A 91, 012342 (2015).
- [34]34. J. P. Olson, K. P. Seshadreesan, K. R. Motes, P. P. Ro- hde, and J. P. Dowling, Physical Review A 91, 022317 (2015).
- [35]35. K. P. Seshadreesan, J. P. Olson, K. R. Motes, P. P. Ro- hde, and J. P. Dowling, Physical Review A 91, 022334 (2015).
- [36]36. S. Aaronson and D. J. Brod, Physical Review A 93, 012335 (2016).
Cited by
Sorted by citations
Quantum computational advantage using photons
Zhong, H.-S., Wang, H., Deng, Y.-H., Chen, M.-C., Peng, L.-C., Luo, Y.-H., Qin, J., Wu, D., Ding, X., Hu, Y., et al. (2020) · Science · doi:10.1126/science.abe8770 · Cited by 2,405 · see citing works
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 1,726 · see citing works
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 · see citing works
Quantum computational advantage with a programmable photonic processor
Madsen, L. S., Laudenbach, F., Askarani, M. F., Rortais, F., Vincent, T., Bulmer, J. F. F., Miatto, F. M., Neuhaus, L., Helt, L. G., Collins, M. J., et al. (2022) · Nature · doi:10.1038/s41586-022-04725-x · Cited by 1,031 · see citing works
Phase-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 · see citing works
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 · see citing works
Generation 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 · see citing works
Applications 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 · see citing works
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 · see citing works
Self-citationPhotonic 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 · see citing works
Computational advantage of quantum random sampling
Hangleiter, D., & Eisert, J. (2023) · Reviews of Modern Physics · doi:10.1103/revmodphys.95.035001 · Cited by 145 · see citing works
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 · see citing works
Applications of near-term photonic quantum computers: software and algorithms
Bromley, T. R., Arrazola, J. M., Jahangiri, S., Izaac, J., Quesada, N., Gran, A. D., Schuld, M., Swinarton, J., Zabaneh, Z., & Killoran, N. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8504 · Cited by 128 · see citing works
Regimes 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 · see citing works
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 · see citing works
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 · see citing works
Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study
Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F. (2024) · ACM Computing Surveys · doi:10.1145/3620668 · Cited by 22 · see citing works
“Gaussian boson sampling, however, is a special-purpose photonic platform to perform sampling tasks that are classically intractable [186].”
BackgroundError mitigation on a near-term quantum photonic device
Su, D., Israel, R., Sharma, K., Qi, H., Dhand, I., & Brádler, K. (2021) · Quantum · doi:10.22331/q-2021-05-04-452 · Cited by 19 · see citing works
- Authors
- Hamilton, C. S., Kruse, R., Sansoni, L., Barkhofen, S., Silberhorn, C., & Jex, I.
- Affiliations
- Czech Technical University in Prague (CZ)
- Paderborn University (DE)
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2017-10-23
- Volume
- 119
- Issue
- 17
- Pages
- 170501-170501
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W2560356194
- Cited by
- 503
- References
- 33
- Citations by year
- 2026: 44 · 2025: 76 · 2024: 86 · 2023: 79 · 2022: 63 · 2021: 52 · 2020: 45 · 2019: 35 · 2018: 17 · 2017: 4 · 2016: 1 · 2014: 1
- FWCI
- 16.48
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review Letters (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Grantová Agentura ?eské Republiky (GAČR 17-00844S)
- Ministerstvo Školství, Mládeže a T?lovýchovy (MŠMT RVO 68407700)
- Horizon 2020 Framework Programme (641039)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
- Keywords
- Gaussian boson sampling, boson sampling, squeezed states, hafnian, quantum advantage, Gaussian states, photonic quantum computing, sample complexity
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
