Efficient verification of boson sampling
Open accessAbstract
The demonstration of quantum speedup, also known as quantum computational supremacy, that is the ability of quantum computers to outperform dramatically their classical counterparts, is an important milestone in the field of quantum computing. While quantum speedup experiments are gradually escaping the regime of classical simulation, they still lack efficient verification protocols and rely on partial validation. Here we derive an efficient protocol for verifying with single-mode Gaussian measurements the output states of a large class of continuous-variable quantum circuits demonstrating quantum speedup, including Boson Sampling experiments, thus enabling a convincing demonstration of quantum speedup with photonic computing. Beyond the quantum speedup milestone, our results also enable the efficient and reliable certification of a large class of intractable continuous-variable multimode quantum states.
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?
In [60], a protocol is given to use single-mode Gaussian measurements to verify a class of continuous variable quantum states, including Boson Sampling states.
“For example, in [60] a protocol is given to use single-mode Gaussian measurements to verify a class of continuous variable quantum states, including Boson Sampling states.”
From Towards violations of Local Friendliness with quantum computers (2025) · cites this paper as [60]
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
Quantum Algorithm for Linear Systems of Equations
Harrow, A. W., Hassidim, A., & Lloyd, S. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.150502 · Cited by 3,325 · see citing works
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
Defining and detecting quantum speedup
Rønnow, T. F., Wang, Z., Job, J., Boixo, S., Isakov, S. V., Wecker, D., Martinis, J. M., Lidar, D. A., & Troyer, M. (2014) · Science · doi:10.1126/science.1252319 · Cited by 601 · cited 1× · see citing works
“The ability of quantum computers to greatly outperform their classical counterparts is referred to as “quantum computational supremacy” [6, 7], or quantum speedup [8].”
BackgroundExperimental validation of photonic boson sampling
Spagnolo, N., Vitelli, C., Bentivegna, M., Brod, D. J., Crespi, A., Flamini, F., Giacomini, S., Milani, G., Ramponi, R., Mataloni, P., et al. (2014) · Nature Photonics · doi:10.1038/nphoton.2014.135 · Cited by 312 · see citing works
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Bremner, M. J., Jozsa, R., & Shepherd, D. J. (2011) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2010.0301 · Cited by 308 · see citing works
Quantum computing and the entanglement frontier
Preskill, J. (2012) · arXiv · doi:10.48550/arxiv.1203.5813 · Cited by 308 · 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
Complexity-Theoretic Foundations of Quantum Supremacy Experiments
Aaronson, S., & Chen, L. (2016) · arXiv · doi:10.48550/arxiv.1612.05903 · Cited by 218
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
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 · cited 1× · see citing works
“However, there is no efficient verification protocol using single-mode Gaussian state preparation nor single-mode Gaussian measurements for Boson Sampling with input single photons: current methods used for the validation of Boson sampling are either not scalable or only provide partial certificates on the tested prob…”
MethodAdaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games
Terhal, B. M., & Divincenzo, D. P. (2004) · Quantum Information and Computation · doi:10.26421/qic4.2-5 · Cited by 124 · see citing works
Factoring using $2n+2$ qubits with Toffoli based modular multiplication
Haner, T., Roetteler, M., & Svore, K. M. (2017) · Quantum Information and Computation · doi:10.26421/qic17.7-8-7 · Cited by 90 · cited 1× · see citing works
“com compelling evidence of quantum speedup, the experimental requirements associated with such a demonstration preclude its realisation in the near future [9].”
BackgroundContinuous Variable Quantum Advantages and Applications in Quantum OpticsPreprint
Chabaud, U. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.05227 · Cited by 1 · see citing works
Self-citationBosonSampling Is Far From UniformPreprint
Aaronson, S., & Arkhipov, A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1309.7460
D'Ariano, G. M., Paris, M. G. A., & Sacchi, M. F. (2003) · arXiv · doi:10.48550/arxiv.quant-ph/0302028
Factoring using 2n+2 qubits with Toffoli based modular multiplication
Häner, T., Roetteler, M., & Svore, K. M. (2016) · arXiv · doi:10.48550/arxiv.1611.07995
Simulating complex networks in phase space: Gaussian boson sampling
Drummond, P. D., Opanchuk, B., Dellios, A., & Reid, M. D. (2021) · arXiv · doi:10.48550/arxiv.2102.10341
Boson Sampling with Gaussian input states: toward efficient scaling and certification
Abrahao, R. A., Mansouri, A., & Lund, A. P. (2018) · arXiv · doi:10.48550/arxiv.1812.08978
Flagged first, then by citations
Research works printed but not linked: 67
- S. Wiesner, "Conjugate coding," ACM Sigact News 15, 78-88 (1983). · DOI · Paper page
- C. H. Bennett and S. J. Wiesner, "Communication via one-and two-particle operators on Einstein-Podolsky-Rosen states," Physical Review Letters 69, 2881 (1992). · DOI · Paper page
- C. H. Bennett and G. Brassard, "Quantum cryptography: public key distribution and coin tossing.," Theorical Computer Science 560, 7-11 (1984). · DOI · Paper page
- P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," SIAM Review 41, 303 (1999). · DOI · Paper page
- A. W. Harrow and A. Montanaro, "Quantum computational supremacy," Nature 549, 203-209 (2017). · DOI
- S. Aaronson and A. Arkhipov, "The computational Complexity of Linear Optics," Theory of Computing 9, 143 (2013). · DOI · Paper page
- D. Shepherd and M. J. Bremner, "Temporally unstructured quantum computation," Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, 1413-1439 (2009). · DOI
- S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, "Characterizing quantum supremacy in near-term devices," Nature Physics 14, 595-600 (2018). · DOI · Paper page
- R. Mezher, J. Ghalbouni, J. Dgheim, and D. Markham, "Efficient approximate unitary t-designs from partially invertible universal sets and their application to quantum speedup," arXiv:1905.01504. · arXiv
- F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al., "Quantum supremacy using a programmable superconducting processor," Nature 574, 505-510 (2019). · DOI · Paper page
- A. M. Dalzell, A. W. Harrow, D. E. Koh, and R. L. La Placa, "How many qubits are needed for quantum computational supremacy?," Quantum 4, 264 (2020). · DOI · Paper page
- B. Barak, C.-N. Chou, and X. Gao, "Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits," arXiv:2005.02421. · arXiv
- R. Renner, "Symmetry of large physical systems implies independence of subsystems," Nature Physics 3, 645-649 (2007). · DOI
- A. Gheorghiu, T. Kapourniotis, and E. Kashefi, "Verification of quantum computation: An overview of existing approaches," Theory of Computing Systems 4, 715-808 (2019). · DOI
- A. Broadbent, J. Fitzsimons, and E. Kashefi, "Universal blind quantum computation," in 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 517-526, IEEE. 2009. · DOI · Paper page
- U. Mahadev, "Classical verification of quantum computations," in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 259-267, IEEE. 2018. · DOI
- D. Hangleiter, M. Kliesch, J. Eisert, and C. Gogolin, "Sample complexity of device-independently certified "quantum supremacy"," Physical Review Letters 122, 210502 (2019). · DOI
- G. D. Kahanamoku-Meyer, "Forging quantum data: classically defeating an IQP-based quantum test," arXiv:1912.05547. · arXiv
- M.-H. Yung and B. Cheng, "Anti-Forging Quantum Data: Cryptographic Verification of Quantum Cloud Computing," arXiv:2005.01510. · arXiv
- Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, and T. Vidick, "A cryptographic test of quantumness and certifiable randomness from a single quantum device," in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 320-331, IEEE. 2018. · DOI
- Z. Brakerski, V. Koppula, U. Vazirani, and T. Vidick, "Simpler Proofs of Quantumness," arXiv:2005.04826. · arXiv
- S. Ferracin, T. Kapourniotis, and A. Datta, "Accrediting outputs of noisy intermediate-scale quantum computing devices," New Journal of Physics 21, 113038 (2019). · DOI
- M. A. Nielsen and I. L. Chuang, "Quantum Computation and Quantum Information: 10th Anniversary Edition,". Cambridge University Press, New York, NY, USA, 10th ed., 2011. · DOI · Paper page
- C. A. Fuchs and J. Van De Graaf, "Cryptographic distinguishability measures for quantum-mechanical states," IEEE Transactions on Information Theory 45, 1216-1227 (1999). · DOI
- D. Mills, A. Pappa, T. Kapourniotis, and E. Kashefi, "Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation," in EPTCS 266, 2018, pp. 209-221, vol. 266, pp. 209-221, EPTCS. · DOI
- D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert, "Direct certification of a class of quantum simulations," Quantum Science and Technology 2, 015004 (2017). · DOI
- T. Kapourniotis and A. Datta, "Nonadaptive fault-tolerant verification of quantum supremacy with noise," Quantum 3, 164 (2019). · DOI
- Y. Takeuchi and T. Morimae, "Verification of many-qubit states," Physical Review X 8, 021060 (2018). · DOI
- S. L. Braunstein and P. van Loock, "Quantum information with continuous variables," Reviews of Modern Physics 77, 513-577 (2005). · DOI · Paper page
- A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O'Brien, and T. C. Ralph, "Boson Sampling from a Gaussian State," Phys.ical Review Letters 113, 100502 (2014). · DOI
- J. P. Olson, K. P. Seshadreesan, K. R. Motes, P. P. Rohde, and J. P. Dowling, "Sampling arbitrary photon-added or photon-subtracted squeezed states is in the same complexity class as Boson Sampling," Physical Review A 91, 022317 (2015). · DOI
- C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, "Gaussian Boson Sampling," Physical review letters 119, 170501 (2017). · DOI · Paper page
- U. Chabaud, T. Douce, D. Markham, P. Van Loock, E. Kashefi, and G. Ferrini, "Continuous-variable sampling from photon-added or photon-subtracted squeezed states," Physical Review A 96, 062307 (2017). · DOI
- L. Chakhmakhchyan and N. J. Cerf, "Boson Sampling with Gaussian measurements," Physical Review A 96, 032326 (2017). · DOI
- A. Lund, S. Rahimi-Keshari, and T. Ralph, "Exact Boson Sampling using Gaussian continuous-variable measurements," Physical Review A 96, 022301 (2017). · DOI
- G. Adesso, S. Ragy, and A. R. Lee, "Continuous variable quantum information: Gaussian states and beyond," Open Systems & Information Dynamics 21, 1440001 (2014). · DOI · Paper page
- S. D. Bartlett, B. C. Sanders, S. L. Braunstein, and K. Nemoto, "Efficient classical simulation of continuous variable quantum information processes," Physical Review Letters 88, 097904 (2002). · DOI · Paper page
- S. Yokoyama, R. Ukai, S. C. Armstrong, C. Sornphiphatphong, T. Kaji, S. Suzuki, J.-i. Yoshikawa, H. Yonezawa, N. C. Menicucci, and A. Furusawa, "Ultra-large-scale continuous-variable cluster states multiplexed in the time domain," Nature Photonics 7, 982 (2013). · DOI
- J.-i. Yoshikawa, S. Yokoyama, T. Kaji, C. Sornphiphatphong, Y. Shiozawa, K. Makino, and A. Furusawa, "Invited article: Generation of one-million-mode continuous-variable cluster state by unlimited time-domain multiplexing," APL Photonics 1, 060801 (2016). · DOI · Paper page
- B. Opanchuk, L. Rosales-Zárate, M. D. Reid, and P. D. Drummond, "Simulating and assessing boson sampling experiments with phase-space representations," Physical Review A 97, 042304 (2018). · DOI
- F. Flamini, N. Spagnolo, and F. Sciarrino, "Photonic quantum information processing: a review," Reports on Progress in Physics 82, 016001 (2018). · DOI
- I. Agresti, N. Viggianiello, F. Flamini, N. Spagnolo, A. Crespi, R. Osellame, N. Wiebe, and F. Sciarrino, "Pattern recognition techniques for Boson Sampling validation," Physical Review X 9, 011013 (2019). · DOI
- H. Wang, J. Qin, X. Ding, M.-C. Chen, S. Chen, X. You, Y.-M. He, X. Jiang, L. You, Z. Wang, et al., "Boson Sampling with 20 Input Photons and a 60-Mode Interferometer in a 10 14 -Dimensional Hilbert Space," Physical Review Letters 123, 250503 (2019). · DOI
- M. Walschaers, "Signatures of many-particle interference," Journal of Physics B: Atomic, Molecular and Optical Physics 53, 043001 (2020). · DOI
- H. Yuen and J. Shapiro, "Optical communication with two-photon coherent states-Part III: Quantum measurements realizable with photoemissive detectors," IEEE Transactions on Information Theory 26, 78-92 (1980). · DOI
- M. G. Paris, "Quantum state measurement by realistic heterodyne detection," Physical Review A 53, 2658 (1996). · DOI
- U. Chabaud, T. Douce, F. Grosshans, E. Kashefi, and D. Markham, "Building Trust for Continuous Variable Quantum States," in 15th Conference on the Theory of Quantum Computation, Communication and Cryptography. 2020. · DOI
- L. Aolita, C. Gogolin, M. Kliesch, and J. Eisert, "Reliable quantum certification of photonic state preparations," Nature communications 6, 8498 (2015). · DOI
- C. Weedbrook, S. Pirandola, R. García-Patrón, N. J. Cerf, T. C. Ralph, J. H. Shapiro, and S. Lloyd, "Gaussian quantum information," Reviews of Modern Physics 84, 621-669 (2012). · DOI
- D. Menzies and R. Filip, "Gaussian-optimized preparation of non-Gaussian pure states," Physical Review A 79, 012313 (2009). · DOI
- U. Chabaud, D. Markham, and F. Grosshans, "Stellar representation of non-Gaussian quantum states," Physical Review Letters 124, 063605 (2020). · DOI
- A. Wünsche, "Laguerre 2D-functions and their application in quantum optics," Journal of Physics A: Mathematical and General 31, 8267 (1998). · DOI
- W. Hoeffding, "Probability inequalities for sums of bounded random variables," Journal of the American statistical association 58, 13-30 (1963). · DOI
- U. Chabaud, G. Roeland, M. Walschaers, F. Grosshans, V. Parigi, D. Markham, and N. Treps, "Certification of non-Gaussian states with operational measurements," PRX Quantum 2, 020333 (2021). · DOI
- R. Renner and J. I. Cirac, "de Finetti representation theorem for infinite-dimensional quantum systems and applications to quantum cryptography," Physical Review Letters 102, 110504 (2009). · DOI
- Y. Ouyang, S.-H. Tan, J. Fitzsimons, and P. P. Rohde, "Homomorphic encryption of linear optics quantum computation on almost arbitrary states of light with asymptotically perfect security," Physical Review Research 2, 013332 (2020). · DOI
- A. Leverrier, R. García-Patrón, R. Renner, and N. J. Cerf, "Security of continuous-variable quantum key distribution against general attacks," Physical Review Letters 110, 030502 (2013). · DOI
- L. G. Valiant, "The complexity of computing the permanent," Theoretical computer science 8, 189-201 (1979). · DOI · Paper page
- T. Jiang and Y. Ma, "Distances between random orthogonal matrices and independent normals," Transactions of the American Mathematical Society 372, 1509-1553 (2019). · DOI
- N. Quesada, "Franck-Condon factors by counting perfect matchings of graphs with loops," The Journal of chemical physics 150, 164113 (2019). · DOI
- U. Chabaud, G. Ferrini, F. Grosshans, and D. Markham, "Classical simulation of Gaussian quantum circuits with non-Gaussian input states," arXiv:2010.14363. · arXiv
- A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro, and A. Laing, "Classical Boson Sampling algorithms with superior performance to near-term experiments," Nature Physics 13, 1153-1157 (2017). · DOI
- R. García-Patrón, J. J. Renema, and V. Shchesnovich, "Simulating Boson Sampling in lossy architectures," Quantum 3, 169 (2019). · DOI
- P. Clifford and R. Clifford, "Faster classical Boson Sampling," arXiv:2005.04214. · arXiv
- C. Huang, F. Zhang, M. Newman, J. Cai, X. Gao, Z. Tian, J. Wu, H. Xu, H. Yu, B. Yuan, et al., "Classical Simulation of Quantum Supremacy Circuits," arXiv:2005.06787. · arXiv
- J. Eisert, D. Hangleiter, N. Walk, I. Roth, D. Markham, R. Parekh, U. Chabaud, and E. Kashefi, "Quantum certification and benchmarking," Nature Reviews Physics 2, 382-390 (2020). · DOI
- U. Chabaud, T. Douce, F. Grosshans, E. Kashefi, and D. Markham, "Building trust for continuous variable quantum states," arXiv:1905.12700. · arXiv
Cited by
Sorted by citations
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
Towards violations of Local Friendliness with quantum computers
Zeng, W. J., Labib, F., & Russo, V. (2025) · Quantum · doi:10.22331/q-2025-09-05-1851
“For example, in [60] a protocol is given to use single-mode Gaussian measurements to verify a class of continuous variable quantum states, including Boson Sampling states.”
- Authors
- Chabaud, U., Grosshans, F., Kashefi, E., & Markham, D.
- Affiliations
- Centre National de la Recherche Scientifique (FR)
- Venue
- Quantum
- Published
- 2021-11-15
- Volume
- 5
- Pages
- 578
- ISSN
- 2521-327X (ISSN-L)
- OpenAlex
- W3033190048
- Cited by
- 37
- References
- 18
- Citations by year
- 2026: 3 · 2025: 10 · 2024: 7 · 2023: 5 · 2022: 4 · 2021: 6 · 2020: 2
- FWCI
- 1.94
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- Quantum (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- HAL (submittedVersion, other-oa)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- arXiv (Cornell University) (cc-by)
- Funders
- European Union’s Horizon 2020 Research and Innovation Program (820445)
- Agence Nationale de la Recherche (ANR-17-CE24-0035)
- 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
- boson sampling, quantum verification, quantum advantage, optical computing, quantum state certification, multimode quantum states
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
