{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:19:36Z","timestamp":1775816376694,"version":"3.50.1"},"reference-count":23,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T00:00:00Z","timestamp":1589414400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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).<\/jats:p>","DOI":"10.22331\/q-2020-05-14-266","type":"journal-article","created":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T15:02:22Z","timestamp":1589468542000},"page":"266","source":"Crossref","is-referenced-by-count":11,"title":["Classical zero-knowledge arguments for quantum computations"],"prefix":"10.22331","volume":"4","author":[{"given":"Thomas","family":"Vidick","sequence":"first","affiliation":[{"name":"Department of Computing and Mathematical Sciences, California Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tina","family":"Zhang","sequence":"additional","affiliation":[{"name":"Division of Physics, Mathematics and Astronomy, California Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2020,5,14]]},"reference":[{"key":"0","unstructured":"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\u2013469. Tsinghua University Press, 2010. URL https:\/\/conference.iiis.tsinghua.edu.cn\/ICS2010\/content\/papers\/35.html."},{"key":"1","unstructured":"Dorit Aharonov, Michael Ben-Or, Elad Eban, and Urmila Mahadev. Interactive proofs for quantum computations. arXiv preprint arXiv:1704.04487, 2017."},{"key":"2","doi-asserted-by":"crossref","unstructured":"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,.","DOI":"10.1007\/978-3-030-64381-2_6"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Gilles Brassard, David Chaum, and Claude Cr\u00e9peau. Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci., 37(2):156\u2013189, October 1988. 10.1016\/0022-0000(88)90005-0.","DOI":"10.1016\/0022-0000(88)90005-0"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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\u2013526. IEEE, 2009. 10.1109\/focs.2009.36.","DOI":"10.1109\/focs.2009.36"},{"key":"5","unstructured":"Anne Broadbent and Alex B Grilo. Zero-knowledge for QMA from locally simulatable proofs. arXiv preprint arXiv:1911.07782, 2019."},{"key":"6","doi-asserted-by":"publisher","unstructured":"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\u201340. IEEE, 2016. 10.1109\/focs.2016.13.","DOI":"10.1109\/focs.2016.13"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physreva.78.012352"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan H\u00e5stad, Joe Kilian, Silvio Micali, and Phillip Rogaway. Everything provable is provable in zero-knowledge. volume 403, pages 37\u201356, 08 1988. 10.1007\/0-387-34799-2_4.","DOI":"10.1007\/0-387-34799-2_4"},{"key":"9","unstructured":"Nir Bitansky and Omri Shmueli. Post-quantum zero knowledge in constant rounds. arXiv preprint arXiv:1912.04769, 2019."},{"key":"10","unstructured":"Andrea Coladangelo, Thomas Vidick, and Tina Zhang. Non-interactive zero-knowledge arguments for QMA, with preprocessing. arXiv preprint arXiv:1911.07546, 2019."},{"key":"11","doi-asserted-by":"publisher","unstructured":"Joseph F Fitzsimons and Elham Kashefi. Unconditionally verifiable blind quantum computation. Physical Review A, 96(1):012303, 2017. 10.1103\/physreva.96.012303.","DOI":"10.1103\/physreva.96.012303"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on computing, 18(1):186\u2013208, 1989. 10.1137\/0218012.","DOI":"10.1137\/0218012"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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\u2013728, July 1991. 10.1145\/116825.116852.","DOI":"10.1145\/116825.116852"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1090\/gsm\/047\/10"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Urmila Mahadev. Classical verification of quantum computations. In Foundations of Computer Science (FOCS), 2018 IEEE 59th Annual Symposium on, pages 259\u2013267, Oct 2018. 10.1109\/focs.2018.00033.","DOI":"10.1109\/focs.2018.00033"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.120.040501"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physreva.93.022326"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/978-3-642-29011-4_41"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Chris Marriott and John Watrous. Quantum arthur\u2013merlin games. Computational Complexity, 14(2):122\u2013152, 2005. 10.1109\/ccc.2004.1313850.","DOI":"10.1109\/ccc.2004.1313850"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/1568318.1568324"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Ben W Reichardt, Falk Unger, and Umesh Vazirani. Classical command of quantum systems. Nature, 496(7446):456, 2013. 10.1038\/nature12035.","DOI":"10.1038\/nature12035"},{"key":"22","doi-asserted-by":"publisher","unstructured":"John Watrous. Zero-knowledge against quantum attacks. SIAM Journal on Computing, 39(1):25\u201358, 2009. 10.1137\/060670997.","DOI":"10.1137\/060670997"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-05-14-266\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,3,14]],"date-time":"2021-03-14T10:29:04Z","timestamp":1615717744000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-05-14-266\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,14]]},"references-count":23,"URL":"https:\/\/doi.org\/10.22331\/q-2020-05-14-266","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,14]]},"article-number":"266"}}