Classical proofs of quantum knowledge
- URL: http://arxiv.org/abs/2005.01691v2
- Date: Tue, 19 Jan 2021 13:40:48 GMT
- Title: Classical proofs of quantum knowledge
- Authors: Thomas Vidick, Tina Zhang
- Abstract summary: We define the notion of a proof of knowledge in the setting where the verifier is classical.
We show that, if a nondestructive classical proof of quantum knowledge exists for some state, then that state can be cloned by an adversary.
- Score: 10.432041176720842
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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, if a nondestructive classical proof of
quantum knowledge exists for some state, then that state can be cloned by an
unbounded adversary, 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
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. In all cases, we construct an explicit
quantum extractor that is able to produce a quantum witness given black-box
quantum (rewinding) access to the prover, the latter of which includes the
ability to coherently execute the prover's black-box circuit controlled on a
superposition of messages from the verifier.
Related papers
- Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process.
We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable.
Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs.
We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
arXiv Detail & Related papers (2024-05-12T09:05:13Z) - Quantum process tomography of continuous-variable gates using coherent
states [49.299443295581064]
We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit.
We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
arXiv Detail & Related papers (2023-03-02T18:08:08Z) - 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) - Quantifying protocol efficiency: a thermodynamic figure of merit for
classical and quantum state-transfer protocols [0.0]
We focus on classical and quantum protocols transferring a state across a double-well potential.
The classical protocols are achieved by deforming the potential, while the quantum ones are assisted by a counter-diabatic driving.
We show that quantum protocols perform more quickly and accurately.
arXiv Detail & Related papers (2022-12-20T09:19:51Z) - 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) - Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
"Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation.
We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
arXiv Detail & Related papers (2021-12-09T19:00:00Z) - 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) - 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) - Using Quantum Metrological Bounds in Quantum Error Correction: A Simple
Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates.
Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
arXiv Detail & Related papers (2020-04-24T17:58:10Z)
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.