Succinct classical verification of quantum computation
From MaRDI portal
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).
Recommendations
- Interactive oracle arguments in the QROM and applications to succinct verification of quantum computation
- Non-interactive classical verification of quantum computation
- Classical verification of quantum computations with efficient verifier
- Classical verification of quantum computations
- How to Verify a Quantum Computation
Cites work
- A Framework for Efficient and Composable Oblivious Transfer
- Classical proofs of quantum knowledge
- Classical verification of quantum computations with efficient verifier
- Computationally binding quantum commitments
- Constant-round blind classical verification of quantum sampling
- How to use indistinguishability obfuscation
- scientific article; zbMATH DE number 1256635 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- Leveled fully homomorphic signatures from standard lattices
- Lossy trapdoor functions and their applications
- Non-deterministic exponential time has two-prover interactive protocols
- Non-interactive classical verification of quantum computation
- Quantum Complexity Theory
- The knowledge complexity of interactive proof-systems
- Verifying quantum computations at scale: a cryptographic leash on quantum devices
Cited in
(15)- Verification of quantum computation: an overview of existing approaches
- How to Verify a Quantum Computation
- Classical verification of quantum proofs
- Lattice-based succinct arguments for NP with polylogarithmic-time verification
- Obfuscation of pseudo-deterministic quantum circuits
- Commitments to quantum states
- Quantum advantage from any non-local game
- Interactive oracle arguments in the QROM and applications to succinct verification of quantum computation
- Compiled nonlocal games from any trapdoor claw-free function
- Succinct arguments for \textsf{BatchQMA} and friends under 8 rounds
- On the power of oblivious state preparation
- Quantum interactive oracle proofs
- Quantum rewinding for IOP-based succinct arguments
- A modular approach to succinct arguments for QMA
- Robustness verification of quantum classifiers
This page was built for publication: Succinct classical verification of quantum computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6104334)
