Classical zero-knowledge arguments for quantum computations

Thomas Vidick1 and Tina Zhang2

1Department of Computing and Mathematical Sciences, California Institute of Technology, USA
2Division of Physics, Mathematics and Astronomy, California Institute of Technology, USA

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

Abstract

We show that every language in QMA admits a classical-verifier, quantum-prover zero-knowledge argument system which is sound against quantum polynomial-time provers and zero-knowledge for classical (and quantum) polynomial-time verifiers. The protocol builds upon two recent results: a computational zero-knowledge proof system for languages in QMA, with a quantum verifier, introduced by Broadbent et al. (FOCS 2016), and an argument system for languages in QMA, with a classical verifier, introduced by Mahadev (FOCS 2018).

► BibTeX data

► References

[1] Dorit Aharonov, Michael Ben-Or, and Elad Eban. Interactive proofs for quantum computations. In Andrew Chi-Chih Yao, editor, Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, pages 453–469. Tsinghua University Press, 2010. URL https:/​/​conference.iiis.tsinghua.edu.cn/​ICS2010/​content/​papers/​35.html.
https:/​/​conference.iiis.tsinghua.edu.cn/​ICS2010/​content/​papers/​35.html

[2] Dorit Aharonov, Michael Ben-Or, Elad Eban, and Urmila Mahadev. Interactive proofs for quantum computations. arXiv preprint arXiv:1704.04487, 2017.
arXiv:1704.04487

[3] Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, and Shih-Han Hung. Non-interactive classical verification of quantum computation. arXiv e-prints, page arXiv:1911.08101, November 2019,.
arXiv:1911.08101

[4] Gilles Brassard, David Chaum, and Claude Crépeau. Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci., 37(2):156–189, October 1988. 10.1016/​0022-0000(88)90005-0.
https:/​/​doi.org/​10.1016/​0022-0000(88)90005-0

[5] Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. Universal blind quantum computation. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 517–526. IEEE, 2009. 10.1109/​focs.2009.36.
https:/​/​doi.org/​10.1109/​focs.2009.36

[6] Anne Broadbent and Alex B Grilo. Zero-knowledge for QMA from locally simulatable proofs. arXiv preprint arXiv:1911.07782, 2019.
arXiv:1911.07782

[7] Anne Broadbent, Zhengfeng Ji, Fang Song, and John Watrous. Zero-knowledge proof systems for QMA. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 31–40. IEEE, 2016. 10.1109/​focs.2016.13.
https:/​/​doi.org/​10.1109/​focs.2016.13

[8] Jacob D. Biamonte and Peter J. Love. Realizable Hamiltonians for universal adiabatic quantum computers. Physical Review A, 78:012352, July 2008, 10.1103/​physreva.78.012352.
https:/​/​doi.org/​10.1103/​physreva.78.012352

[9] Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, and Phillip Rogaway. Everything provable is provable in zero-knowledge. volume 403, pages 37–56, 08 1988. 10.1007/​0-387-34799-2_4.
https:/​/​doi.org/​10.1007/​0-387-34799-2_4

[10] Nir Bitansky and Omri Shmueli. Post-quantum zero knowledge in constant rounds. arXiv preprint arXiv:1912.04769, 2019.
arXiv:1912.04769

[11] Andrea Coladangelo, Thomas Vidick, and Tina Zhang. Non-interactive zero-knowledge arguments for QMA, with preprocessing. arXiv preprint arXiv:1911.07546, 2019.
arXiv:1911.07546

[12] Joseph F Fitzsimons and Elham Kashefi. Unconditionally verifiable blind quantum computation. Physical Review A, 96(1):012303, 2017. 10.1103/​physreva.96.012303.
https:/​/​doi.org/​10.1103/​physreva.96.012303

[13] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on computing, 18(1):186–208, 1989. 10.1137/​0218012.
https:/​/​doi.org/​10.1137/​0218012

[14] Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems. J. ACM, 38(3):690–728, July 1991. 10.1145/​116825.116852.
https:/​/​doi.org/​10.1145/​116825.116852

[15] Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi, and Mikhail N Vyalyi. Classical and quantum computation. Number 47. American Mathematical Soc., 2002. 10.1090/​gsm/​047/​10.
https:/​/​doi.org/​10.1090/​gsm/​047/​10

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

[17] Tomoyuki Morimae and Joseph F. Fitzsimons. Post hoc verification with a single prover. arXiv e-prints, March 2016, https:/​/​arxiv.org/​pdf/​1603.06046.pdf. 10.1103/​PhysRevLett.120.040501.
https:/​/​doi.org/​10.1103/​PhysRevLett.120.040501
https:/​/​arxiv.org/​pdf/​1603.06046.pdf

[18] Tomoyuki Morimae, Daniel Nagaj, and Norbert Schuch. Quantum proofs can be verified using only single-qubit measurements. Physical Review A, 93:022326, February 2016, 10.1103/​physreva.93.022326.
https:/​/​doi.org/​10.1103/​physreva.93.022326

[19] Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. Cryptology ePrint Archive, Report 2011/​501, 2011. 10.1007/​978-3-642-29011-4_41. https:/​/​eprint.iacr.org/​2011/​501.
https:/​/​doi.org/​10.1007/​978-3-642-29011-4_41
https:/​/​eprint.iacr.org/​2011/​501

[20] Chris Marriott and John Watrous. Quantum arthur–merlin games. Computational Complexity, 14(2):122–152, 2005. 10.1109/​ccc.2004.1313850.
https:/​/​doi.org/​10.1109/​ccc.2004.1313850

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

[22] Ben W Reichardt, Falk Unger, and Umesh Vazirani. Classical command of quantum systems. Nature, 496(7446):456, 2013. 10.1038/​nature12035.
https:/​/​doi.org/​10.1038/​nature12035

[23] John Watrous. Zero-knowledge against quantum attacks. SIAM Journal on Computing, 39(1):25–58, 2009. 10.1137/​060670997.
https:/​/​doi.org/​10.1137/​060670997

Cited by

[1] Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, and Shih-Han Hung, Lecture Notes in Computer Science 12552, 153 (2020) ISBN:978-3-030-64380-5.

[2] Jose Carrasco, Andreas Elben, Christian Kokail, Barbara Kraus, and Peter Zoller, "Theoretical and Experimental Perspectives of Quantum Verification", PRX Quantum 2 1, 010102 (2021).

[3] Prabhanjan Ananth and Rolando L. La Placa, Lecture Notes in Computer Science 12552, 123 (2020) ISBN:978-3-030-64380-5.

[4] Andrea Coladangelo, Thomas Vidick, and Tina Zhang, Lecture Notes in Computer Science 12172, 799 (2020) ISBN:978-3-030-56876-4.

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

[6] Prabhanjan Ananth, Kai-Min Chung, and Rolando L. La Placa, Lecture Notes in Computer Science 12825, 346 (2021) ISBN:978-3-030-84241-3.

[7] Thomas Vidick and Tina Zhang, Lecture Notes in Computer Science 12697, 630 (2021) ISBN:978-3-030-77885-9.

[8] Anne Broadbent and Alex Bredariol Grilo, "QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge", SIAM Journal on Computing 51 4, 1400 (2022).

[9] Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, and Shih-Han Hung, "Non-interactive classical verification of quantum computation", arXiv:1911.08101, (2019).

[10] Honghao Fu, Daochen Wang, and Qi Zhao, "Parallel self-testing of EPR pairs under computational assumptions", arXiv:2201.13430, (2022).

[11] Andrea Coladangelo, Thomas Vidick, and Tina Zhang, "Non-interactive zero-knowledge arguments for QMA, with preprocessing", arXiv:1911.07546, (2019).

[12] Prabhanjan Ananth and Rolando L. La Placa, "Secure Quantum Extraction Protocols", arXiv:1911.07672, (2019).

[13] Anne Broadbent, Arthur Mehta, and Yuming Zhao, "Quantum delegation with an off-the-shelf device", arXiv:2304.03448, (2023).

[14] Eric Culf and Arthur Mehta, "New Approaches to Complexity via Quantum Graphs", arXiv:2309.12887, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-03-28 19:05:34) and SAO/NASA ADS (last updated successfully 2024-03-28 19:05:35). The list may be incomplete as not all publishers provide suitable and complete citation data.