Depth-efficient proofs of quantumness

Zhenning Liu1 and Alexandru Gheorghiu2

1Department of Physics, ETH Zürich, Switzerland
2Institute for Theoretical Studies, ETH Zürich, Switzerland

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

Abstract

A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify the $\textit{quantum advantage}$ of an untrusted prover. That is, a quantum prover can correctly answer the verifier's challenges and be accepted, while any polynomial-time classical prover will be rejected with high probability, based on plausible computational assumptions. To answer the verifier's challenges, existing proofs of quantumness typically require the quantum prover to perform a combination of polynomial-size quantum circuits and measurements.
In this paper, we give two proof of quantumness constructions in which the prover need only perform $\textit{constant-depth quantum circuits}$ (and measurements) together with log-depth classical computation. Our first construction is a generic compiler that allows us to translate all existing proofs of quantumness into constant quantum depth versions. Our second construction is based around the $\textit{learning with rounding}$ problem, and yields circuits with shorter depth and requiring fewer qubits than the generic construction. In addition, the second construction also has some robustness against noise.

► BibTeX data

► References

[1] 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, 2011.
https:/​/​doi.org/​10.1145/​1993636.1993682

[2] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, 2019.
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[3] MD SAJID ANIS, Abby-Mitchell, Héctor Abraham, AduOffei, et al. Qiskit: An open-source framework for quantum computing, 2021.

[4] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.

[5] Scott Aaronson and Lijie Chen. Complexity-Theoretic Foundations of Quantum Supremacy Experiments. In Proceedings of the 32nd Computational Complexity Conference, CCC '17, pages 1–67, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https:/​/​doi.org/​10.48550/​arXiv.1612.05903

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

[7] B. Applebaum, Y. Ishai, and E. Kushilevitz. Cryptography in ${NC}^0$. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 166–175, 2004.
https:/​/​doi.org/​10.1109/​FOCS.2004.20

[8] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak, and Daniel Wichs. Learning with Rounding, Revisited. In Advances in Cryptology – CRYPTO 2013, pages 57–74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1007/​978-3-642-40041-4_4

[9] David A Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in ${NC}^1$. Journal of Computer and System Sciences, 38(1):150–164, 1989.
https:/​/​doi.org/​10.1016/​0022-0000(89)90037-8

[10] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas 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), pages 320–331. IEEE, 2018.
https:/​/​doi.org/​10.1145/​3441309

[11] Colin D. Bruzewicz, John Chiaverini, Robert McConnell, and Jeremy M. Sage. Trapped-ion quantum computing: Progress and challenges. Applied Physics Reviews, 2019.
https:/​/​doi.org/​10.1063/​1.5088164

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

[13] 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(6):595–600, 2018.
https:/​/​doi.org/​10.1038/​s41567-018-0124-x

[14] Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick. Simpler Proofs of Quantumness. In 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 für Informatik.
https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2020.8

[15] Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom Functions and Lattices. In Advances in Cryptology – EUROCRYPT 2012, pages 719–737. Springer Berlin Heidelberg, 2012.
https:/​/​doi.org/​10.1007/​978-3-642-29011-4_42

[16] John F Clauser, Michael A Horne, Abner Shimony, and Richard A Holt. Proposed experiment to test local hidden-variable theories. Physical Review Letters, 23(15):880, 1969.
https:/​/​doi.org/​10.1103/​PhysRevLett.23.880

[17] Matthew Coudron, Jalex Stark, and Thomas Vidick. Trading locality for time: certifiable randomness from low-depth circuits. Communications in Mathematical Physics, 382(1):49–86, 2021.
https:/​/​doi.org/​10.1007/​s00220-021-03963-w

[18] Richard Cleve and John Watrous. Fast parallel circuits for the quantum Fourier transform. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 526–536. IEEE, 2000.
https:/​/​doi.org/​10.1109/​SFCS.2000.892140

[19] Pierre Dusart. Autour de la fonction qui compte le nombre de nombres premiers. PhD thesis, Université de Limoges, 1998.
https:/​/​www.unilim.fr/​laco/​theses/​1998/​T1998_01.pdf

[20] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland. Surface codes: Towards practical large-scale quantum computation. Physical Review A, 86(3):032324, 2012.
https:/​/​doi.org/​10.1103/​PhysRevA.86.032324

[21] François Le Gall. Private correspondence, 2022.

[22] Craig Gidney and Martin Ekerå. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5:433, 2021.
https:/​/​doi.org/​10.22331/​q-2021-04-15-433

[23] Alexandru Gheorghiu and Matty J Hoban. Estimating the entropy of shallow circuit outputs is hard. arXiv preprint arXiv:2002.12814, 2020.
https:/​/​doi.org/​10.48550/​arXiv.2002.12814
arXiv:2002.12814

[24] Shuichi Hirahara and François Le Gall. Test of Quantumness with Small-Depth Quantum Circuits. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of Leibniz International Proceedings in Informatics (LIPIcs), pages 59:1–59:15, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https:/​/​doi.org/​10.4230/​LIPIcs.MFCS.2021.59

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

[26] Peter Høyer and Robert Špalek. Quantum Fan-out is Powerful. Theory of Computing, 1(5):81–103, 2005.
https:/​/​doi.org/​10.4086/​toc.2005.v001a005

[27] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, and Jianxin Chen. Classical Simulation of Quantum Supremacy Circuits. arXiv preprint arXiv:2005.06787, 2020.
https:/​/​doi.org/​10.48550/​arXiv.2005.06787
arXiv:2005.06787

[28] Gregory D Kahanamoku-Meyer. Forging quantum data: classically defeating an IQP-based quantum test. arXiv preprint arXiv:1912.05547, 2019.
https:/​/​doi.org/​10.48550/​arXiv.1912.05547
arXiv:1912.05547

[29] 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(8):918–924, 2022.
https:/​/​doi.org/​10.1038/​s41567-022-01643-7

[30] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 1–23. Springer, 2010.
https:/​/​doi.org/​10.1145/​2535925

[31] Urmila Mahadev. Classical verification of quantum computations. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 259–267. IEEE, 2018.
https:/​/​doi.org/​10.1109/​FOCS.2018.00033

[32] Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.

[33] A. S. Popova and A.N. Rubtsov. Cracking the Quantum Advantage Threshold for Gaussian Boson Sampling. In Quantum 2.0 Conference and Exhibition, page QW2A.15. Optica Publishing Group, 2022.
https:/​/​doi.org/​10.1364/​QUANTUM.2022.QW2A.15

[34] John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2:79, 2018.
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[35] Michael O Rabin. Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1):128–138, 1980.
https:/​/​doi.org/​10.1016/​0022-314X(80)90084-0

[36] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009.
https:/​/​doi.org/​10.1145/​1568318.1568324

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

[38] Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. IEEE, 1994.
https:/​/​doi.org/​10.1109/​SFCS.1994.365700

[39] 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. Phys. Rev. Lett., 127:180501, 2021.
https:/​/​doi.org/​10.1103/​PhysRevLett.127.180501

[40] K Wright, KM Beck, Sea Debnath, JM Amini, Y Nam, N Grzesiak, J-S Chen, NC Pisenti, M Chmielewski, C Collins, et al. Benchmarking an 11-qubit quantum computer. Nature communications, 10(1):1–6, 2019.
https:/​/​doi.org/​10.1038/​s41467-019-13534-2

[41] G Wendin. Quantum information processing with superconducting circuits: a review. Reports on Progress in Physics, 80(10):106001, 2017.
https:/​/​doi.org/​10.1088/​1361-6633/​aa7e1a

[42] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 515–526, 2019.
https:/​/​doi.org/​10.1145/​3313276.3316404

[43] Andrew Chi-Chih Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 162–167. IEEE, 1986.
https:/​/​doi.org/​10.1109/​SFCS.1986.25

[44] 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(3):240–245, 2022.
https:/​/​doi.org/​10.1016/​j.scib.2021.10.017

[45] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidick, Umesh Vazirani, Norman Y. Yao, Marko Cetina, and Christopher Monroe. Interactive Protocols for Classically-Verifiable Quantum Advantage. arXiv preprint arXiv:2112.05156, 2021.
https:/​/​doi.org/​10.48550/​arXiv.2112.05156
arXiv:2112.05156

[46] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. Quantum computational advantage using photons. Science, 370(6523):1460–1463, 2020.
https:/​/​doi.org/​10.1126/​science.abe8770

Cited by

[1] Nathanan Tantivasadakarn, Ashvin Vishwanath, and Ruben Verresen, "A hierarchy of topological order from finite-depth unitaries, measurement and feedforward", arXiv:2209.06202.

[2] Sergey Bravyi, Isaac Kim, Alexander Kliesch, and Robert Koenig, "Adaptive constant-depth circuits for manipulating non-abelian anyons", arXiv:2205.01933.

[3] Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Alexandru Gheorghiu, Yunseong Nam, Thomas Vidick, Umesh Vazirani, Norman Y. Yao, Marko Cetina, and Christopher Monroe, "Interactive Protocols for Classically-Verifiable Quantum Advantage", arXiv:2112.05156.

[4] 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 8, 918 (2022).

[5] Vipin Singh Sehrawat, Foo Yee Yeo, and Dmitriy Vassilyev, "Star-specific Key-homomorphic PRFs from Linear Regression and Extremal Set Theory", arXiv:2205.00861.

[6] Nai-Hui Chia and Shih-Han Hung, "Classical verification of quantum depth", arXiv:2205.04656.

[7] Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, and Avishay Tal, "On Certified Randomness from Quantum Advantage Experiments", arXiv:2111.14846.

[8] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa, and Seiichiro Tani, "Computational self-testing for entangled magic states", Physical Review A 106 1, L010601 (2022).

[9] Yihui Quek, Mark M. Wilde, and Eneet Kaur, "Multivariate trace estimation in constant quantum depth", arXiv:2206.15405.

[10] Laura Lewis, Daiwei Zhu, Alexandru Gheorghiu, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, Laird Egan, Thomas Vidick, Marko Cetina, and Christopher Monroe, "Experimental Implementation of an Efficient Test of Quantumness", arXiv:2209.14316.

The above citations are from SAO/NASA ADS (last updated successfully 2022-10-01 13:22: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 2022-10-01 13:22:50).