Secret extraction attacks against obfuscated IQP circuits

Abstract

Quantum computing devices can now perform sampling tasks which, according to complexity-theoretic and numerical evidence, are beyond the reach of classical computers. This raises the question of how one can efficiently verify that a quantum computer operating in this regime works as intended. In 2008, Shepherd and Bremner proposed a protocol in which a verifier constructs a unitary from the comparatively easy-to-implement family of so-called IQP circuits, and challenges a prover to execute it on a quantum computer. The challenge problem is designed to contain an obfuscated secret, which can be turned into a statistical test that accepts samples from a correct quantum implementation. It was conjectured that extracting the secret from the challenge problem is NP-hard, so that the ability to pass the test constitutes strong evidence that the prover possesses a quantum device and that it works as claimed. Unfortunately, about a decade later, Kahanamoku-Meyer found an efficient classical secret extraction attack. Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol. Their IQP Stabilizer Scheme has been explicitly designed to circumvent the known weakness. They also suggested that the original construction can be made secure by adjusting the problem parameters. In this work, we develop a number of secret extraction attacks which are effective against both new approaches in a wide range of problem parameters. In particular, we find multiple ways to recover the 300-bit secret hidden in a challenge data set published by Bremner, Cheng, and Ji. The important problem of finding an efficient and reliable verification protocol for sampling-based proofs of quantum supremacy thus remains open.

24 pages, 4 figures

References in corpus (17)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Characterizing Quantum Supremacy in Near-Term Devices
• Strong quantum computational advantage using a superconducting quantum processor
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Instantaneous Quantum Computation
• Computational advantage of quantum random sampling
• Solving the sampling problem of the Sycamore quantum circuits
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Phase transition in Random Circuit Sampling
• Classically-Verifiable Quantum Advantage from a Computational Bell Test
• Interactive Protocols for Classically-Verifiable Quantum Advantage
• Verifiable Quantum Advantage without Structure
• Forging quantum data: classically defeating an IQP-based quantum test
• Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security

Cited by in corpus (2)

• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security