Bartusek, James and Kalai, Yael Tauman and Lombardi, Alex and Ma, Fermi and Malavolta, Giulio and Vaikuntanathan, Vinod and Vidick, Thomas and Yang, Lisa (2022) Succinct Classical Verification of Quantum Computation. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20221221-004803338
![]() |
PDF
- Submitted Version
Creative Commons Attribution Share Alike. 786kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20221221-004803338
Abstract
We construct a classically verifiable succinct interactive argument for quantum computation (BQP) with communication complexity and verifier runtime that are poly-logarithmic in the runtime of the BQP computation (and polynomial in the security parameter). Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning with Errors (LWE). This is the first succinct argument for quantum computation in the plain model; prior work (Chia-Chung-Yamakawa, TCC '20) requires both a long common reference string and non-black-box use of a hash function modeled as a random oracle. At a technical level, we revisit the framework for constructing classically verifiable quantum computation (Mahadev, FOCS '18). We give a self-contained, modular proof of security for Mahadev's protocol, which we believe is of independent interest. Our proof readily generalizes to a setting in which the verifier's first message (which consists of many public keys) is compressed. Next, we formalize this notion of compressed public keys; we view the object as a generalization of constrained/programmable PRFs and instantiate it based on indistinguishability obfuscation. Finally, we compile the above protocol into a fully succinct argument using a (sufficiently composable) succinct argument of knowledge for NP. Using our framework, we achieve several additional results, including - Succinct arguments for QMA (given multiple copies of the witness), - Succinct non-interactive arguments for BQP (or QMA) in the quantum random oracle model, and - Succinct batch arguments for BQP (or QMA) assuming post-quantum LWE (without iO).
Item Type: | Report or Paper (Discussion Paper) | ||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||||||||||||||||||||||
ORCID: |
| ||||||||||||||||||||||||||||||||
Additional Information: | Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) AL is supported in part by a Charles M. Vest fellowship. GM is partially supported by the German Federal Ministry of Education and Research BMBF (grant 16K15K042, project 6GEM). TV is supported by AFOSR YIP award number FA9550-16-1-0495, a grant from the Simons Foundation (828076, TV), MURI Grant FA9550-18-1-0161, the NSF QLCI program through grant number OMA-2016245 and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). AL, VV, and LY are supported in part by DARPA under Agreement No. HR00112020023, a grant from MIT-IBM Watson AI, a grant from Analog Devices, a Microsoft Trustworthy AI grant and the Thornton Family Faculty Research Innovation Fellowship. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA. LY was supported in part by an NSF graduate research fellowship. | ||||||||||||||||||||||||||||||||
Group: | Institute for Quantum Information and Matter | ||||||||||||||||||||||||||||||||
Funders: |
| ||||||||||||||||||||||||||||||||
Record Number: | CaltechAUTHORS:20221221-004803338 | ||||||||||||||||||||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20221221-004803338 | ||||||||||||||||||||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||||||||||||||||||
ID Code: | 118567 | ||||||||||||||||||||||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||||||||||||||||||||||
Deposited By: | George Porter | ||||||||||||||||||||||||||||||||
Deposited On: | 21 Dec 2022 20:41 | ||||||||||||||||||||||||||||||||
Last Modified: | 21 Dec 2022 20:41 |
Repository Staff Only: item control page