Forging quantum data: classically defeating an IQP-based quantum test

Forging quantum data: classically defeating an IQP-based quantum test

Time Stamp: September 11, 2023 8:46 AM

Gregory D. Kahanamoku-Meyer

Department of Physics, University of California at Berkeley, Berkeley, CA 94720

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

Abstract

Recently, quantum computing experiments have for the first time exceeded the capability of classical computers to perform certain computations – a milestone termed “quantum computational advantage.” However, verifying the output of the quantum device in these experiments required extremely large classical computations. An exciting next step for demonstrating quantum capability would be to implement tests of quantum computational advantage with efficient classical verification, such that larger system sizes can be tested and verified. One of the first proposals for an efficiently-verifiable test of quantumness consists of hiding a secret classical bitstring inside a circuit of the class IQP, in such a way that samples from the circuit’s output distribution are correlated with the secret. The classical hardness of this protocol has been supported by evidence that directly simulating IQP circuits is hard, but the security of the protocol against other (non-simulating) classical attacks has remained an open question. In this work we demonstrate that the protocol is not secure against classical forgery. We describe a classical algorithm that can not only convince the verifier that the (classical) prover is quantum, but can in fact can extract the secret key underlying a given protocol instance. Furthermore, we show that the key extraction algorithm is efficient in practice for problem sizes of hundreds of qubits. Finally, we provide an implementation of the algorithm, and give the secret vector underlying the “$25 challenge” posted online by the authors of the original paper.

Forging quantum data: classically defeating an IQP-based quantum test PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Featured image: In this work, we show how a cheating classical computer (left) can masquerade as a quantum computer in its interactions with a classical “verifier” computer (right), in the context of a specific proof-of-quantumness protocol.

Popular summary

Recent quantum sampling experiments have demonstrated quantum computational advantage by performing computations that are infeasible to reproduce classically. However, classically checking the results is at least as hard, making direct verification infeasible for the largest experiments. A candidate for overcoming this challenge was a sampling protocol proposed in 2008, which promised efficient classical verification while maintaining the classical hardness of reproducing the quantum device’s behavior. In this work we give an efficient classical algorithm that passes the verification checks by extracting the underlying secret key, which is supposed to be hidden even from a real quantum device. Our algorithm invalidates the claim that only a quantum device could pass the checks, defeating the usefulness of the test as a demonstration of quantum capability.

â–º BibTeX data

â–º References

[1] Frank Arute et al. “Quantum supremacy using a programmable superconducting processor”. Nature 574, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[2] Han-Sen Zhong et al. “Quantum computational advantage using photons”. Science 370, 1460–1463 (2020).
https:/​/​doi.org/​10.1126/​science.abe8770

[3] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan. “Strong Quantum Computational Advantage Using a Superconducting Quantum Processor”. Physical Review Letters 127, 180501 (2021).
https:/​/​doi.org/​10.1103/​PhysRevLett.127.180501

[4] Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yulin Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan. “Quantum computational advantage via 60-qubit 24-cycle random circuit sampling”. Science Bulletin 67, 240–245 (2022).
https:/​/​doi.org/​10.1016/​j.scib.2021.10.017

[5] Scott Aaronson and Alex Arkhipov. “The computational complexity of linear optics”. In Proceedings of the forty-third annual ACM symposium on Theory of computing. Pages 333–342. STOC ’11New York, NY, USA (2011). Association for Computing Machinery.
https:/​/​doi.org/​10.1145/​1993636.1993682

[6] Edward Farhi and Aram W. Harrow. “Quantum Supremacy through the Quantum Approximate Optimization Algorithm” (2019). arXiv:1602.07674.
arXiv:1602.07674

[7] A. P. Lund, Michael J. Bremner, and T. C. Ralph. “Quantum sampling problems, BosonSampling and quantum supremacy”. npj Quantum Information 3, 1–8 (2017).
https:/​/​doi.org/​10.1038/​s41534-017-0018-2

[8] Aram W. Harrow and Ashley Montanaro. “Quantum computational supremacy”. Nature 549, 203–209 (2017).
https:/​/​doi.org/​10.1038/​nature23458

[9] Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven. “Characterizing quantum supremacy in near-term devices”. Nature Physics 14, 595–600 (2018).
https:/​/​doi.org/​10.1038/​s41567-018-0124-x

[10] Barbara M. Terhal. “Quantum supremacy, here we come”. Nature Physics 14, 530–531 (2018).
https:/​/​doi.org/​10.1038/​s41567-018-0131-y

[11] C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, A. Megrant, B. Chiaro, A. Dunsworth, K. Arya, R. Barends, B. Burkett, Y. Chen, Z. Chen, et al. “A blueprint for demonstrating quantum supremacy with superconducting qubits”. Science 360, 195–199 (2018).
https:/​/​doi.org/​10.1126/​science.aao4309

[12] Sergey Bravyi, David Gosset, and Robert Konig. “Quantum advantage with shallow circuits”. Science 362, 308–311 (2018).
https:/​/​doi.org/​10.1126/​science.aar3106

[13] Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel. “Quantum advantage with noisy shallow circuits”. Nature Physics 16, 1040–1045 (2020).
https:/​/​doi.org/​10.1038/​s41567-020-0948-z

[14] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. “On the complexity and verification of quantum random circuit sampling”. Nature Physics 15, 159–163 (2019).
https:/​/​doi.org/​10.1038/​s41567-018-0318-2

[15] Scott Aaronson and Sam Gunn. “On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking”. Theory of Computing 16, 1–8 (2020).
https:/​/​doi.org/​10.4086/​toc.2020.v016a011

[16] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. “A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device”. Journal of the ACM (JACM) (2021).
https:/​/​doi.org/​10.1145/​3441309

[17] Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick. “Simpler Proofs of Quantumness”. In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:14. Dagstuhl, Germany (2020). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2020.8

[18] Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, and Norman Y. Yao. “Classically-Verifiable Quantum Advantage from a Computational Bell Test”. Nature Physics 18, 918–924 (2022).
https:/​/​doi.org/​10.1038/​s41567-022-01643-7

[19] Dan Shepherd and Michael J. Bremner. “Temporally unstructured quantum computation”. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, 1413–1439 (2009).
https:/​/​doi.org/​10.1098/​rspa.2008.0443

[20] Michael J. Bremner et al. “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).
https:/​/​doi.org/​10.1098/​rspa.2010.0301

[21] Michael J. Bremner et al. “Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations”. Physical Review Letters 117, 080501 (2016).
https:/​/​doi.org/​10.1103/​PhysRevLett.117.080501

[22] Gregory D Kahanamoku-Meyer (2023). code: https:/​/​doi.org/​10.5281/​zenodo.7545881.
https:/​/​doi.org/​10.5281/​zenodo.7545881

[23] Yusuf Alnawakhtha, Atul Mantri, Carl A. Miller, and Daochen Wang. “Lattice-Based Quantum Advantage from Rotated Measurements” (2022). arXiv:2210.10143.
arXiv:2210.10143

[24] Takashi Yamakawa and Mark Zhandry. “Verifiable Quantum Advantage without Structure”. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). Pages 69–74. (2022).
https:/​/​doi.org/​10.1109/​FOCS54457.2022.00014

[25] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. “Quantum Advantage from Any Non-local Game”. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Pages 1617–1628. STOC 2023New York, NY, USA (2023). Association for Computing Machinery.
https:/​/​doi.org/​10.1145/​3564246.3585164

[26] Alexandru Gheorghiu and Thomas Vidick. “Computationally-Secure and Composable Remote State Preparation”. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). Pages 1024–1033. (2019).
https:/​/​doi.org/​10.1109/​FOCS.2019.00066

[27] Urmila Mahadev. “Classical Verification of Quantum Computations”. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). Pages 259–267. (2018).
https:/​/​doi.org/​10.1109/​FOCS.2018.00033

Cited by

[1] Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel, “Quantum advantage with noisy shallow circuits”, Nature Physics 16 10, 1040 (2020).

[2] Dominik Hangleiter and Jens Eisert, “Computational advantage of quantum random sampling”, Reviews of Modern Physics 95 3, 035001 (2023).

[3] Zhenning Liu and Alexandru Gheorghiu, “Depth-efficient proofs of quantumness”, Quantum 6, 807 (2022).

[4] Martin Kliesch and Ingo Roth, “Theory of quantum system certification: a tutorial”, arXiv:2010.05925, (2020).

[5] Ulysse Chabaud, Frédéric Grosshans, Elham Kashefi, and Damian Markham, “Efficient verification of Boson Sampling”, Quantum 5, 578 (2021).

[6] Michael J. Bremner, Bin Cheng, and Zhengfeng Ji, “IQP Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security”, arXiv:2308.07152, (2023).

[7] Sergey Bravyi, David Gosset, Daniel Grier, and Luke Schaeffer, “Classical algorithms for Forrelation”, arXiv:2102.06963, (2021).

[8] Dominik Hangleiter, “Sampling and the complexity of nature”, arXiv:2012.07905, (2020).

[9] Xi Chen, Bin Cheng, Zhaokai Li, Xinfang Nie, Nengkun Yu, Man-Hong Yung, and Xinhua Peng, “Experimental cryptographic verification for near-term quantum cloud computing”, Science Bulletin 66 1, 23 (2021).

[10] 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, (2021).

The above citations are from SAO/NASA ADS (last updated successfully 2023-09-12 13:11:52). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2023-09-12 13:11:50).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

Time Stamp:

More from Quantum Journal