CaltechAUTHORS
  A Caltech Library Service

Classical proofs of quantum knowledge

Vidick, Thomas and Zhang, Tina (2020) Classical proofs of quantum knowledge. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20200728-145122122

[img] PDF - Submitted Version
See Usage Policy.

366Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200728-145122122

Abstract

We define the notion of a proof of knowledge in the setting where the verifier is classical, but the prover is quantum, and where the witness that the prover holds is in general a quantum state. We establish simple properties of our definition, including that nondestructive classical proofs of quantum knowledge are impossible for nontrivial states, and that, under certain conditions on the parameters in our definition, a proof of knowledge protocol for a hard-to-clone state can be used as a (destructive) quantum money verification protocol. In addition, we provide two examples of protocols (both inspired by private-key classical verification protocols for quantum money schemes) which we can show to be proofs of quantum knowledge under our definition. In so doing, we introduce new techniques for the analysis of such protocols which build on results from the literature on nonlocal games. Finally, we show that, under our definition, the verification protocol introduced by Mahadev (FOCS 2018) is a classical argument of quantum knowledge for QMA relations.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/2005.01691arXivDiscussion Paper
ORCID:
AuthorORCID
Vidick, Thomas0000-0002-6405-365X
Additional Information:We thank Andru Gheorghiu for useful feedback. Thomas Vidick is supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-1-0495, a CIFAR Azrieli Global Scholar award, MURI Grant FA9550-18-1-0161 and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028).
Group:Institute for Quantum Information and Matter
Funders:
Funding AgencyGrant Number
NSFCCF-1553477
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Canadian Institute for Advanced Research (CIFAR)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0161
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
NSFPHY-1125565
Gordon and Betty Moore FoundationGBMF-12500028
Record Number:CaltechAUTHORS:20200728-145122122
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200728-145122122
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104615
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:28 Jul 2020 22:43
Last Modified:28 Jul 2020 22:43

Repository Staff Only: item control page