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).
 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.
 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,.
 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.
 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.
 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.
 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.
 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.
 Joseph F Fitzsimons and Elham Kashefi. Unconditionally verifiable blind quantum computation. Physical Review A, 96(1):012303, 2017. 10.1103/physreva.96.012303.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 Andrea Coladangelo, Thomas Vidick, and Tina Zhang, Lecture Notes in Computer Science 12172, 799 (2020) ISBN:978-3-030-56876-4.
 Anne Broadbent and Alex B. Grilo, "Zero-Knowledge for QMA from Locally Simulatable Proofs", arXiv:1911.07782.
 Andrea Coladangelo, Thomas Vidick, and Tina Zhang, "Non-interactive zero-knowledge arguments for QMA, with preprocessing", arXiv:1911.07546.
 Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, and Shih-Han Hung, "Non-interactive classical verification of quantum computation", arXiv:1911.08101.
 Thomas Vidick and Tina Zhang, "Classical proofs of quantum knowledge", arXiv:2005.01691.
 Prabhanjan Ananth and Rolando L. La Placa, "Secure Quantum Extraction Protocols", arXiv:1911.07672.
The above citations are from Crossref's cited-by service (last updated successfully 2020-10-21 14:28:37) and SAO/NASA ADS (last updated successfully 2020-10-21 14:28:38). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.