Forging quantum data: classically defeating an IQP-based quantum test

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.

8 pages, 2 figures. v2: revisions to exposition and discussion; references updated; no changes to main results. v3: update DOIs of references

References in corpus (7)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Strong quantum computational advantage using a superconducting quantum processor
• Quantum Computational Supremacy
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Quantum advantage with noisy shallow circuits in 3D
• Classically-Verifiable Quantum Advantage from a Computational Bell Test

Cited by in corpus (6)

• Efficient verification of Boson Sampling
• Depth-efficient proofs of quantumness
• Secret extraction attacks against obfuscated IQP circuits
• Sampling and the complexity of nature
• Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security
• Classical algorithms for Forrelation