TY - JOUR T1 - Interactive Protocols for Classically-Verifiable Quantum Advantage Y1 - 2021 A1 - Daiwei Zhu A1 - Gregory D. Kahanamoku-Meyer A1 - Laura Lewis A1 - Crystal Noel A1 - Or Katz A1 - Bahaa Harraz A1 - Qingfeng Wang A1 - Andrew Risinger A1 - Lei Feng A1 - Debopriyo Biswas A1 - Laird Egan A1 - Alexandru Gheorghiu A1 - Yunseong Nam A1 - Thomas Vidick A1 - Umesh Vazirani A1 - Norman Y. Yao A1 - Marko Cetina A1 - Christopher Monroe AB -

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.

UR - https://arxiv.org/abs/2112.05156 ER -