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.
 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).
 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).
 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.
 A. P. Lund, Michael J. Bremner, and T. C. Ralph. ``Quantum sampling problems, BosonSampling and quantum supremacy''. npj Quantum Information 3, 1–8 (2017).
 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).
 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).
 Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel. ``Quantum advantage with noisy shallow circuits''. Nature Physics 16, 1040–1045 (2020).
 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).
 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).
 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.
 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).
 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).
 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).
 Michael J. Bremner et al. ``Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations''. Physical Review Letters 117, 080501 (2016).
 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).
 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.
 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).
 Urmila Mahadev. ``Classical Verification of Quantum Computations''. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). Pages 259–267. (2018).
 Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel, "Quantum advantage with noisy shallow circuits", Nature Physics 16 10, 1040 (2020).
 Dominik Hangleiter and Jens Eisert, "Computational advantage of quantum random sampling", Reviews of Modern Physics 95 3, 035001 (2023).
 Zhenning Liu and Alexandru Gheorghiu, "Depth-efficient proofs of quantumness", Quantum 6, 807 (2022).
 Ulysse Chabaud, Frédéric Grosshans, Elham Kashefi, and Damian Markham, "Efficient verification of Boson Sampling", Quantum 5, 578 (2021).
 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).
The above citations are from SAO/NASA ADS (last updated successfully 2023-09-22 14:24:02). 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-22 14:24:00).
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.