Forging quantum data: classically defeating an IQP-based quantum test
- URL: http://arxiv.org/abs/1912.05547v3
- Date: Wed, 6 Sep 2023 02:22:21 GMT
- Title: Forging quantum data: classically defeating an IQP-based quantum test
- Authors: Gregory D. Kahanamoku-Meyer
- Abstract summary: 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recently, quantum computing experiments have for the first time exceeded the
capability of classical computers to perform certain computations -- a
milestone termed "quantum computational advantage." However, verifying the
output of the quantum device in these experiments required extremely large
classical computations. An exciting next step for demonstrating quantum
capability would be to implement tests of quantum computational advantage with
efficient classical verification, such that larger system sizes can be tested
and verified. One of the first proposals for an efficiently-verifiable test of
quantumness consists of hiding a secret classical bitstring inside a circuit of
the class IQP, in such a way that samples from the circuit's output
distribution are correlated with the secret (arXiv:0809.0847). The classical
hardness of this protocol has been supported by evidence that directly
simulating IQP circuits is hard, but the security of the protocol against other
(non-simulating) classical attacks has remained an open question. In this work
we demonstrate that the protocol is not secure against classical forgery. We
describe a classical algorithm that can not only convince the verifier that the
(classical) prover is quantum, but can in fact can extract the secret key
underlying a given protocol instance. Furthermore, we show that the key
extraction algorithm is efficient in practice for problem sizes of hundreds of
qubits. Finally, we provide an implementation of the algorithm, and give the
secret vector underlying the "$25 challenge" posted online by the authors of
the original paper.
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) - Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth [0.5188841610098435]
We show that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, the output distribution can be efficiently sampled by a classical computer.
We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit.
arXiv Detail & Related papers (2024-03-21T17:55:26Z) - 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) - Experimental Implementation of an Efficient Test of Quantumness [49.588006756321704]
A test of quantumness is a protocol where a classical user issues challenges to a quantum device to determine if it exhibits non-classical behavior.
Recent attempts to implement such tests on current quantum computers rely on either interactive challenges with efficient verification, or non-interactive challenges with inefficient (exponential time) verification.
arXiv Detail & Related papers (2022-09-28T18:00:04Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - An Optimized Quantum Implementation of ISD on Scalable Quantum Resources [2.274915755738124]
We show that Prange's ISD algorithm can be implemented rather efficiently on a quantum computer.
We leverage the idea of classical co-processors to design hybrid classical-quantum trade-offs.
arXiv Detail & Related papers (2021-12-12T06:01:10Z) - 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) - Test of Quantumness with Small-Depth Quantum Circuits [1.90365714903665]
Recently, we have shown how to construct a test of quantumness based on the learning with errors (LWE) assumption.
This test has lead to several cryptographic applications.
In this paper, we show that this test of quantumness, and essentially all the above applications, can actually be implemented by a very weak class of quantum circuits.
arXiv Detail & Related papers (2021-05-12T08:16:20Z) - 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.