Succinct Classical Verification of Quantum Computation

• URL: http://arxiv.org/abs/2206.14929v1
• Date: Wed, 29 Jun 2022 22:19:12 GMT
• Title: Succinct Classical Verification of Quantum Computation
• Authors: James Bartusek, Yael Tauman Kalai, Alex Lombardi, Fermi Ma, Giulio Malavolta, Vinod Vaikuntanathan, Thomas Vidick, and Lisa Yang
• Abstract summary: We construct a classically succinct interactive argument for quantum computation (BQP) Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning Errors (LWE)
• Score: 30.91621630752802
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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).

Related papers

• Single-Round Proofs of Quantumness from Knowledge Assumptions [41.94295877935867]
  A proof of quantumness is an efficiently verifiable interactive test that an efficient quantum computer can pass. Existing single-round protocols require large quantum circuits, whereas multi-round ones use smaller circuits but require experimentally challenging mid-circuit measurements. We construct efficient single-round proofs of quantumness based on existing knowledge assumptions.
  arXiv  Detail & Related papers  (2024-05-24T17:33:10Z)
• Succinct arguments for QMA from standard assumptions via compiled nonlocal games [1.6124402884077915]
  We construct a succinct classical argument system for QMA from generic and standard cryptographic assumptions. Our main technical contribution is to analyze the soundness of this transformation when it is applied to a succinct self-test for Pauli measurements.
  arXiv  Detail & Related papers  (2024-04-30T17:58:06Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Commitments to Quantum States [11.217084610985674]
  A commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. Commitments to quantum states open the door to many new cryptographic possibilities.
  arXiv  Detail & Related papers  (2022-10-11T04:34:36Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
  We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $epsilon$-zero-knowledge against quantum attacks. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier.
  arXiv  Detail & Related papers  (2020-11-05T05:40:05Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Simpler Proofs of Quantumness [16.12500804569801]
  A proof of quantumness is a method for provably demonstrating that a quantum device can perform computational tasks that a classical device cannot. There are currently three approaches for exhibiting proofs of quantumness. We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function.
  arXiv  Detail & Related papers  (2020-05-11T01:31:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.