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.

arXiv comment11 pages, 3 figures; supp. info 23 pages, 4 figures

References in corpus (25)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Experimental loophole-free violation of a Bell inequality using entangled electron spins separated by 1.3 km
• Quantum computational advantage using photons
• Significant-loophole-free test of Bell's theorem with entangled photons
• Quantum Convolutional Neural Networks
• A strong loophole-free test of local realism
• Characterizing Quantum Supremacy in Near-Term Devices
• Strong quantum computational advantage using a superconducting quantum processor
• Multi-particle entanglement of hot trapped ions
• Programmable Quantum Simulations of Spin Systems with Trapped Ions
• Quantum Computational Supremacy
• Demonstration of a small programmable quantum computer with atomic qubits
• Quantum Zeno Effect and the Many-body Entanglement Transition
• Demonstration of the trapped-ion quantum-CCD computer architecture
• Manipulation and Detection of a Trapped Yb+ Ion Hyperfine Qubit
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Observation of measurement-induced quantum phases in a trapped-ion quantum computer
• Hyper-optimized tensor network contraction
• Optimal quantum control of multi-mode couplings between trapped ion qubits for scalable entanglement
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Quantum gate teleportation between separated qubits in a trapped-ion processor
• 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