Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security

Abstract

Sampling problems demonstrating beyond classical computing power with noisy intermediate scale quantum devices have been experimentally realized. In those realizations, however, our trust that the quantum devices faithfully solve the claimed sampling problems is usually limited to simulations of smaller-scale instances and is, therefore, indirect. The problem of verifiable quantum advantage aims to resolve this critical issue and provides us with greater confidence in a claimed advantage. Instantaneous quantum polynomial-time (IQP) sampling has been proposed to achieve beyond classical capabilities with a verifiable scheme based on quadratic-residue codes (QRC). Unfortunately, this verification scheme was recently broken by an attack proposed by Kahanamoku-Meyer. In this work, we revive IQP-based verifiable quantum advantage by making two major contributions. Firstly, we introduce a family of IQP sampling protocols called the stabilizer scheme, which builds on results linking IQP circuits, the stabilizer formalism, coding theory, and an efficient characterization of IQP circuit correlation functions. This construction extends the scope of existing IQP-based schemes while maintaining their simplicity and verifiability. Secondly, we introduce the Hidden Structured Code (HSC) problem as a well-defined mathematical challenge that underlies the stabilizer scheme. To assess classical security, we explore a class of attacks based on secret extraction, including the Kahanamoku-Meyer's attack as a special case. We provide evidence of the security of the stabilizer scheme, assuming the hardness of the HSC problem. We also point out that the vulnerability observed in the original QRC scheme is primarily attributed to inappropriate parameter choices, which can be naturally rectified with proper parameter settings.

37 pages, 5 figures. Accepted by PRX Quantum

References in corpus (20)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Improved Simulation of Stabilizer Circuits
• Characterizing Quantum Supremacy in Near-Term Devices
• Strong quantum computational advantage using a superconducting quantum processor
• Simulating quantum computation by contracting tensor networks
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Unconditionally verifiable blind computation
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Instantaneous Quantum Computation
• Post hoc verification of quantum computation
• Post hoc verification with a single prover
• Diagonal gates in the Clifford hierarchy
• Classically-Verifiable Quantum Advantage from a Computational Bell Test
• Interactive Protocols for Classically-Verifiable Quantum Advantage
• Simulating Quantum Computations with Tutte Polynomials
• Forging quantum data: classically defeating an IQP-based quantum test
• Secret extraction attacks against obfuscated IQP circuits

Cited by in corpus (1)

• Secret extraction attacks against obfuscated IQP circuits