Interactive Protocols for Classically-Verifiable Quantum Advantage

Abstract

Achieving quantum computational advantage requires solving a classically intractable problem on a quantum device. Natural proposals rely upon the intrinsic hardness of classically simulating quantum mechanics; however, verifying the output is itself classically intractable. On the other hand, certain quantum algorithms (e.g. prime factorization via Shor's algorithm) are efficiently verifiable, but require more resources than what is available on near-term devices. One way to bridge the gap between verifiability and implementation is to use "interactions" between a prover and a verifier. By leveraging cryptographic functions, such protocols enable the classical verifier to enforce consistency in a quantum prover's responses across multiple rounds of interaction. In this work, we demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer. We execute two complementary protocols -- one based upon the learning with errors problem and another where the cryptographic construction implements a computational Bell test. To perform multiple rounds of interaction, we implement mid-circuit measurements on a subset of trapped ion qubits, with subsequent coherent evolution. For both protocols, the performance exceeds the asymptotic bound for classical behavior; maintaining this fidelity at scale would conclusively demonstrate verifiable quantum advantage.

11 pages, 3 figures; supp. info 23 pages, 4 figures

References in corpus (9)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Strong quantum computational advantage using a superconducting quantum processor
• Manipulation and Detection of a Trapped Yb+ Ion Hyperfine Qubit
• Observation of measurement-induced quantum phases in a trapped-ion quantum computer
• Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer
• Classical Simulation of Quantum Supremacy Circuits
• Classically-Verifiable Quantum Advantage from a Computational Bell Test
• Depth-efficient proofs of quantumness

Cited by in corpus (13)

• Demonstration of fault-tolerant Steane quantum error correction
• Complexity-constrained quantum thermodynamics
• Traceable random numbers from a nonlocal quantum advantage
• Verifiable measurement-based quantum random sampling with trapped ions
• Snapshotting Quantum Dynamics at Multiple Time Points
• Lattice-Based Quantum Advantage from Rotated Measurements
• Entropy Accumulation under Post-Quantum Cryptographic Assumptions
• Secret extraction attacks against obfuscated IQP circuits
• Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security
• Robust and Parallel Control of Many Qubits
• Preliminary characterization of a surface electrode Paul trap for frequency metrology
• Low-Crosstalk, Silicon-Fabricated Optical Waveguides for Laser Delivery to Matter Qubits
• Non-invasive mid-circuit measurement and reset on atomic qubits