Classical verification of quantum depth
- URL: http://arxiv.org/abs/2205.04656v1
- Date: Tue, 10 May 2022 03:55:24 GMT
- Title: Classical verification of quantum depth
- Authors: Nai-Hui Chia, Shih-Han Hung
- Abstract summary: We present two protocols for classical verification of quantum depth.
Our first protocol certifies the depth of the target machine with information theoretic security and nearly optimal separation.
Our second protocol certifies the quantum depth of a single device based on quantum hardness of learning with errors.
- Score: 1.8613536568358358
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present two protocols for classical verification of quantum depth. Our
protocols allow a purely classical verifier to distinguish devices with
different quantum circuit depths even in the presence of classical computation.
We show that a device with quantum circuit depth at most d will be rejected by
the verifier even if the prover applies additional polynomial-time classical
computation to cheat. On the other hand, the verifier accepts a device which
has quantum circuit depth d' for some d'>d. In our first protocol, we introduce
an additional untrusted quantum machine which shares entanglements with the
target machine. Applying a robust self-test, our first protocol certifies the
depth of the target machine with information theoretic security and nearly
optimal separation. The protocol relies on the oracle separation problem for
quantum depth by Chia, Chung and Lai [STOC 2020] and a transformation from an
oracle separation problem to a two-player non-local game. Our second protocol
certifies the quantum depth of a single device based on quantum hardness of
learning with errors. The protocol relies on the noisy trapdoor claw-free
function family and the idea of pointer chasing to force the prover to keep
quantum coherence until all preceding message exchanges are completed. To our
knowledge, we give the first constructions for distinguishing hybrid
quantum-classical computers with different circuit depths in unrelativized
models.
Related papers
- On the Power of Oblivious State Preparation [14.520515990983897]
Oblivious State Preparation (OSP) is a cryptographic primitive that unifies techniques developed in the context of a quantum server interacting with a classical client.
Results help to ''explain'' the use of public-key cryptography in approaches to establishing a ''classical leash'' on a quantum server.
arXiv Detail & Related papers (2024-11-06T19:58:53Z) - 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) - 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) - Oblivious Quantum Computation and Delegated Multiparty Quantum
Computation [61.12008553173672]
We propose a new concept, oblivious computation quantum computation, where secrecy of the input qubits and the program to identify the quantum gates are required.
Exploiting quantum teleportation, we propose a two-server protocol for this task.
Also, we discuss delegated multiparty quantum computation, in which, several users ask multiparty quantum computation to server(s) only using classical communications.
arXiv Detail & Related papers (2022-11-02T09:01:33Z) - Efficient Bipartite Entanglement Detection Scheme with a Quantum
Adversarial Solver [89.80359585967642]
Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits.
We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
arXiv Detail & Related papers (2022-03-15T09:46:45Z) - Quantum computation capability verification protocol for NISQ devices
with dihedral coset problem [0.4061135251278187]
We propose an interactive protocol for one party (the verifier) holding a quantum computer to verify the quantum computation power of another party's (the prover) device via a one-way quantum channel.
We conduct a 4-qubit experiment on one of IBM Q devices.
arXiv Detail & Related papers (2022-02-14T19:00:58Z) - Probably approximately correct quantum source coding [0.0]
Holevo's and Nayak's bounds give an estimate of the amount of classical information that can be stored in a quantum state.
We show two novel applications in quantum learning theory and delegated quantum computation with a purely classical client.
arXiv Detail & Related papers (2021-12-13T17:57:30Z) - 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)
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.