A Caltech Library Service

Non-interactive zero-knowledge arguments for QMA, with preprocessing

Coladangelo, Andrea and Vidick, Thomas and Zhang, Tina (2019) Non-interactive zero-knowledge arguments for QMA, with preprocessing. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


A non-interactive zero-knowledge (NIZK) proof system for a language L∈NP allows a prover (who is provided with an instance x∈L, and a witness w for x) to compute a classical certificate π for the claim that x∈L such that π has the following properties: 1) π can be verified efficiently, and 2) π does not reveal any information about w, besides the fact that it exists (i.e. that x∈L). NIZK proof systems have recently been shown to exist for all languages in NP in the common reference string (CRS) model and under the learning with errors (LWE) assumption. We initiate the study of NIZK arguments for languages in QMA. Our first main result is the following: if LWE is hard for quantum computers, then any language in QMA has an NIZK argument with preprocessing. The preprocessing in our argument system consists of (i) the generation of a CRS and (ii) a single (instance-independent) quantum message from verifier to prover. The instance-dependent phase of our argument system involves only a single classical message from prover to verifier. Importantly, verification in our protocol is entirely classical, and the verifier needs not have quantum memory; its only quantum actions are in the preprocessing phase. Our second contribution is to extend the notion of a classical proof of knowledge to the quantum setting. We introduce the notions of arguments and proofs of quantum knowledge (AoQK/PoQK), and we show that our non-interactive argument system satisfies the definition of an AoQK. In particular, we explicitly construct an extractor which can recover a quantum witness from any prover who is successful in our protocol. We also show that any language in QMA has an (interactive) proof of quantum knowledge.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Group:UNSPECIFIED, Institute for Quantum Information and Matter
Record Number:CaltechAUTHORS:20200110-140701565
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100630
Deposited By: Tony Diaz
Deposited On:11 Jan 2020 00:50
Last Modified:04 Jun 2020 10:14

Repository Staff Only: item control page