Classically-Verifiable Quantum Advantage from a Computational Bell Test
- URL: http://arxiv.org/abs/2104.00687v2
- Date: Tue, 16 Aug 2022 18:09:07 GMT
- Title: Classically-Verifiable Quantum Advantage from a Computational Bell Test
- Authors: Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, Norman
Y. Yao
- Abstract summary: We propose and analyze a novel interactive protocol for demonstrating quantum computational advantage.
Our protocol relies upon the cryptographic hardness of trapdoor claw-free functions (TCFs)
We describe two independent innovations which improve the efficiency of our protocol's implementation.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose and analyze a novel interactive protocol for demonstrating quantum
computational advantage, which is efficiently classically verifiable. Our
protocol relies upon the cryptographic hardness of trapdoor claw-free functions
(TCFs). Through a surprising connection to Bell's inequality, our protocol
avoids the need for an adaptive hardcore bit, with essentially no increase in
the quantum circuit complexity and no extra cryptographic assumptions.
Crucially, this expands the set of compatible TCFs, and we propose two new
constructions: one based upon the decisional Diffie-Hellman problem and the
other based upon Rabin's function, $x^2 \bmod N$. We also describe two
independent innovations which improve the efficiency of our protocol's
implementation: (i) a scheme to discard so-called "garbage bits", thereby
removing the need for reversibility in the quantum circuits, and (ii) a natural
way of performing post-selection which significantly reduces the fidelity
needed to demonstrate quantum advantage. These two constructions may also be of
independent interest, as they may be applicable to other TCF-based quantum
cryptography such as certifiable random number generation. Finally, we design
several efficient circuits for $x^2 \bmod N$ and describe a blueprint for their
implementation on a Rydberg-atom-based quantum computer.
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) - 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) - 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) - 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) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems.
By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z) - 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) - Variational Quantum Cloning: Improving Practicality for Quantum
Cryptanalysis [2.064612766965483]
We propose variational quantum cloning (VQC), a machine learning based cryptanalysis algorithm.
VQC allows an adversary to obtain optimal (approximate) cloning strategies with short depth quantum circuits.
We derive attacks on two protocols as examples, based on quantum cloning and facilitated by VQC.
arXiv Detail & Related papers (2020-12-21T15:28:09Z) - 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) - Forging quantum data: classically defeating an IQP-based quantum test [0.0]
We describe a classical algorithm that can convince the verifier that the (classical) prover is quantum.
We show that the key extraction algorithm is efficient in practice for problem sizes of hundreds of qubits.
arXiv Detail & Related papers (2019-12-11T19:00:00Z)
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.