Efficient verification of Boson Sampling

Ulysse Chabaud1, Frédéric Grosshans1, Elham Kashefi1,2, and Damian Markham1,3

1Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
2School of Informatics, University of Edinburgh, 10 Crichton Street, Edinburgh, EH8 9AB
3JFLI, CNRS, National Institute of Informatics, University of Tokyo, Tokyo, Japan

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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.

Recording of conference talk at the 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), July 5-8, 2021, University of Latvia, Riga, Latvia.

We often hear that quantum computers will offer dramatic advantages over their classical counterparts, but how can we be so sure? Well, factoring integers is hard with a classical computer, but easy with a quantum computer, so let us factor large integers and prove that quantum computers are truly powerful! There is a catch, however: quantum computers are hard to build, and we do not (yet) have quantum computers powerful enough to convincingly run a factoring algorithm on large integers.
On the other hand, we can build simpler quantum machines, such as the so-called Boson Sampling interferometers, that already challenge classical processors. Then all we need to do is to verify that these machines do what they are supposed to do…
It turns out that verifying subuniversal quantum models such as Boson Sampling is highly non-trivial, due to the nature of the computational task performed. Here we give a solution to this long-standing open problem, where verification is performed using simple Gaussian measurements available in the lab. Our results also have applications for the efficient certification of multimode continuous-variable quantum states.

► BibTeX data

► References

[1] S. Wiesner, ``Conjugate coding,'' ACM Sigact News 15, 78–88 (1983).

[2] 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).

[3] C. H. Bennett and G. Brassard, ``Quantum cryptography: public key distribution and coin tossing.,'' Theorical Computer Science 560, 7–11 (1984).

[4] A. W. Harrow, A. Hassidim, and S. Lloyd, ``Quantum algorithm for linear systems of equations,'' Physical Review Letters 103, 150502 (2009).

[5] P. W. Shor, ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,'' SIAM Review 41, 303 (1999).

[6] J. Preskill, ``Quantum computing and the entanglement frontier,'' arXiv:1203.5813.

[7] A. W. Harrow and A. Montanaro, ``Quantum computational supremacy,'' Nature 549, 203–209 (2017).

[8] T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, and M. Troyer, ``Defining and detecting quantum speedup,'' Science 345, 420–424 (2014).

[9] T. Häner, M. Roetteler, and K. M. Svore, ``Factoring using 2n+ 2 qubits with Toffoli based modular multiplication,'' Quantum Information & Computation 17, 673–684 (2017), arXiv:1611.07995.

[10] S. Aaronson and A. Arkhipov, ``The computational Complexity of Linear Optics,'' Theory of Computing 9, 143 (2013).

[11] B. M. Terhal and D. P. DiVincenzo, ``Adptive quantum computation, constant depth quantum circuits and arthur-merlin games,'' Quantum Information & Computation 4, 134–145 (2004), https:/​/​arxiv.org/​abs/​quant-ph/​0205133.

[12] 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).

[13] M. J. Bremner, R. Jozsa, and D. J. Shepherd, ``Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 459–472 (2011).

[14] 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).

[15] 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.

[16] 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).

[17] H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, et al., ``Quantum computational advantage using photons,'' Science 370, 1460–1463 (2020).

[18] S. Aaronson and L. Chen, ``Complexity-theoretic foundations of quantum supremacy experiments,'' in Proceedings of the 32nd Computational Complexity Conference, pp. 1–67. 2017. arXiv:1612.05903.

[19] 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).

[20] B. Barak, C.-N. Chou, and X. Gao, ``Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits,'' arXiv:2005.02421.

[21] R. Renner, ``Symmetry of large physical systems implies independence of subsystems,'' Nature Physics 3, 645–649 (2007).

[22] A. Gheorghiu, T. Kapourniotis, and E. Kashefi, ``Verification of quantum computation: An overview of existing approaches,'' Theory of Computing Systems 4, 715–808 (2019).

[23] 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.

[24] U. Mahadev, ``Classical verification of quantum computations,'' in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 259–267, IEEE. 2018.

[25] D. Hangleiter, M. Kliesch, J. Eisert, and C. Gogolin, ``Sample complexity of device-independently certified ``quantum supremacy'','' Physical Review Letters 122, 210502 (2019).

[26] G. D. Kahanamoku-Meyer, ``Forging quantum data: classically defeating an IQP-based quantum test,'' arXiv:1912.05547.

[27] M.-H. Yung and B. Cheng, ``Anti-Forging Quantum Data: Cryptographic Verification of Quantum Cloud Computing,'' arXiv:2005.01510.

[28] 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.

[29] Z. Brakerski, V. Koppula, U. Vazirani, and T. Vidick, ``Simpler Proofs of Quantumness,'' arXiv:2005.04826.

[30] N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, et al., ``Experimental validation of photonic Boson Sampling,'' Nature Photonics 8, 615 (2014).

[31] P. D. Drummond, B. Opanchuk, and M. D. Reid, ``Simulating complex networks in phase space: Gaussian boson sampling,'' arXiv:2102.10341.

[32] S. Aaronson and A. Arkhipov, ``Boson Sampling is far from uniform,'' arXiv:1309.7460.

[33] S. Ferracin, T. Kapourniotis, and A. Datta, ``Accrediting outputs of noisy intermediate-scale quantum computing devices,'' New Journal of Physics 21, 113038 (2019).

[34] 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.

[35] C. A. Fuchs and J. Van De Graaf, ``Cryptographic distinguishability measures for quantum-mechanical states,'' IEEE Transactions on Information Theory 45, 1216–1227 (1999).

[36] 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.

[37] D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert, ``Direct certification of a class of quantum simulations,'' Quantum Science and Technology 2, 015004 (2017).

[38] T. Kapourniotis and A. Datta, ``Nonadaptive fault-tolerant verification of quantum supremacy with noise,'' Quantum 3, 164 (2019).

[39] Y. Takeuchi and T. Morimae, ``Verification of many-qubit states,'' Physical Review X 8, 021060 (2018).

[40] S. L. Braunstein and P. van Loock, ``Quantum information with continuous variables,'' Reviews of Modern Physics 77, 513–577 (2005).

[41] 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).

[42] 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).

[43] C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, ``Gaussian Boson Sampling,'' Physical review letters 119, 170501 (2017).

[44] 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).

[45] L. Chakhmakhchyan and N. J. Cerf, ``Boson Sampling with Gaussian measurements,'' Physical Review A 96, 032326 (2017).

[46] A. Lund, S. Rahimi-Keshari, and T. Ralph, ``Exact Boson Sampling using Gaussian continuous-variable measurements,'' Physical Review A 96, 022301 (2017).

[47] G. Adesso, S. Ragy, and A. R. Lee, ``Continuous variable quantum information: Gaussian states and beyond,'' Open Systems & Information Dynamics 21, 1440001 (2014).

[48] 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).

[49] A. Ferraro, S. Olivares, and M. G. Paris, ``Gaussian states in continuous variable quantum information,'' arXiv:quant-ph/​0503237.

[50] 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).

[51] 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).

[52] 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).

[53] F. Flamini, N. Spagnolo, and F. Sciarrino, ``Photonic quantum information processing: a review,'' Reports on Progress in Physics 82, 016001 (2018).

[54] 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).

[55] D. J. Brod, E. F. Galvão, A. Crespi, R. Osellame, N. Spagnolo, and F. Sciarrino, ``Photonic implementation of Boson Sampling: a review,'' Advanced Photonics 1, 034001 (2019).

[56] 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).

[57] M. Walschaers, ``Signatures of many-particle interference,'' Journal of Physics B: Atomic, Molecular and Optical Physics 53, 043001 (2020).

[58] 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).

[59] M. G. Paris, ``Quantum state measurement by realistic heterodyne detection,'' Physical Review A 53, 2658 (1996).

[60] 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.

[61] L. Aolita, C. Gogolin, M. Kliesch, and J. Eisert, ``Reliable quantum certification of photonic state preparations,'' Nature communications 6, 8498 (2015).

[62] 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).

[63] D. Menzies and R. Filip, ``Gaussian-optimized preparation of non-Gaussian pure states,'' Physical Review A 79, 012313 (2009).

[64] U. Chabaud, D. Markham, and F. Grosshans, ``Stellar representation of non-Gaussian quantum states,'' Physical Review Letters 124, 063605 (2020).

[65] A. Wünsche, ``Laguerre 2D-functions and their application in quantum optics,'' Journal of Physics A: Mathematical and General 31, 8267 (1998).

[66] W. Hoeffding, ``Probability inequalities for sums of bounded random variables,'' Journal of the American statistical association 58, 13–30 (1963).

[67] 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).

[68] 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).

[69] 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).

[70] 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).

[71] G. M. D'Ariano, M. G. Paris, and M. F. Sacchi, ``Quantum tomography,'' Advances in Imaging and Electron Physics 128, 206–309 (2003), arXiv:quant-ph/​0302028.

[72] L. G. Valiant, ``The complexity of computing the permanent,'' Theoretical computer science 8, 189–201 (1979).

[73] T. Jiang and Y. Ma, ``Distances between random orthogonal matrices and independent normals,'' Transactions of the American Mathematical Society 372, 1509–1553 (2019).

[74] U. Chabaud, ``Continuous Variable Quantum Advantages and Applications in Quantum Optics, Lemma 3.11,'' arXiv:2102.05227.

[75] R. A. Abrahao and A. P. Lund, ``Continuous-variables Boson Sampling: scaling and verification,'' arXiv:1812.08978.

[76] R. Kruse, C. S. Hamilton, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, ``Detailed study of Gaussian Boson Sampling,'' Physical Review A 100, 032326 (2019).

[77] N. Quesada, ``Franck-Condon factors by counting perfect matchings of graphs with loops,'' The Journal of chemical physics 150, 164113 (2019).

[78] U. Chabaud, G. Ferrini, F. Grosshans, and D. Markham, ``Classical simulation of Gaussian quantum circuits with non-Gaussian input states,'' arXiv:2010.14363. https:/​/​doi.org/​10.1103/​PhysRevResearch.3.033018.

[79] 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).

[80] R. García-Patrón, J. J. Renema, and V. Shchesnovich, ``Simulating Boson Sampling in lossy architectures,'' Quantum 3, 169 (2019).

[81] P. Clifford and R. Clifford, ``Faster classical Boson Sampling,'' arXiv:2005.04214.

[82] 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.

[83] 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).

[84] U. Chabaud, T. Douce, F. Grosshans, E. Kashefi, and D. Markham, ``Building trust for continuous variable quantum states,'' arXiv:1905.12700. https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2020.3.

Cited by

[1] Kazuki Akimoto, Shunji Tsuchiya, Ryosuke Yoshii, and Yuki Takeuchi, "Passive verification protocol for thermal graph states", Physical Review A 106 1, 012405 (2022).

[2] A. Dellios, Peter D. Drummond, Bogdan Opanchuk, Run Yan Teh, and Margaret D. Reid, "Simulating macroscopic quantum correlations in linear networks", Physics Letters A 429, 127911 (2022).

[3] Paulina Lewandowska, Aleksandra Krawiec, Ryszard Kukulski, Łukasz Pawela, and Zbigniew Puchała, "On the optimal certification of von Neumann measurements", Scientific Reports 11 1, 3623 (2021).

[4] Mattia Walschaers, "Non-Gaussian Quantum States and Where to Find Them", PRX Quantum 2 3, 030204 (2021).

[5] Michał Oszmaniec, Ninnat Dangniam, Mauro E. S. Morales, and Zoltán Zimborás, "Fermion Sampling: A Robust Quantum Computational Advantage Scheme Using Fermionic Linear Optics and Magic Input States", PRX Quantum 3 2, 020328 (2022).

[6] Ulysse Chabaud, Ganaël Roeland, Mattia Walschaers, Frédéric Grosshans, Valentina Parigi, Damian Markham, and Nicolas Treps, "Certification of Non-Gaussian States with Operational Measurements", PRX Quantum 2 2, 020333 (2021).

[7] Ninnat Dangniam, Yun-Guang Han, and Huangjun Zhu, "Optimal verification of stabilizer states", Physical Review Research 2 4, 043323 (2020).

[8] Ulysse Chabaud, Pierre-Emmanuel Emeriau, and Frédéric Grosshans, "Witnessing Wigner Negativity", arXiv:2102.06193.

[9] Pierre-Emmanuel Emeriau, "The Interplay between Quantum Contextuality and Wigner Negativity", arXiv:2204.08782.

[10] Ulysse Chabaud, "Continuous Variable Quantum Advantages and Applications in Quantum Optics", arXiv:2102.05227.

[11] Ya-Dong Wu, Ge Bai, Giulio Chiribella, and Nana Liu, "Efficient Verification of Continuous-Variable Quantum States and Devices without Assuming Identical and Independent Operations", Physical Review Letters 126 24, 240503 (2021).

[12] Sritam Kumar Satpathy, Vallabh Vibhu, Sudev Pradhan, Bikash K. Behera, and Prasanta K. Panigrahi, "Efficient Verification of Boson Sampling Using a Quantum Computer", arXiv:2108.03954.

[13] Ye-Chao Liu, Jiangwei Shang, and Xiangdong Zhang, "Efficient verification of entangled continuous-variable quantum states with local measurements", Physical Review Research 3 4, L042004 (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2022-09-24 15:35:54) and SAO/NASA ADS (last updated successfully 2022-09-24 15:35:55). The list may be incomplete as not all publishers provide suitable and complete citation data.