A Caltech Library Service

Interactive Protocols for Classically-Verifiable Quantum Advantage

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

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Gheorghiu, Alexandru0000-0001-6225-7168
Vidick, Thomas0000-0002-6405-365X
Yao, Norman Y.0000-0003-0194-7266
Additional Information:The authors are grateful to Vivian Uhlir for the design of the verifier and prover figures. This work is supported by the ARO through the IARPA LogiQ program, the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers, Quantum Systems Accelerator (QSA), the AFOSR MURIs on Quantum Measurement/Verification and Quantum Interactive Protocols (FA9550-18-1-0161) and Dissipation Engineering in Open Quantum Systems, the NSF STAQ Program, the ARO MURI on Modular Quantum Circuits, the DoE ASCR Accelerated Research in Quantum Computing program (award No. DE-SC0020312), the AFOSR YIP award number FA9550-16-1-0495, the NSF QLCI program through grant number OMA-2016245, the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565), the Gordon and Betty Moore Foundation (GBMF-12500028), the Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich Foundation, the NSF award DMR-1747426, a Vannever Bush Faculty Fellowship, the Office of Advanced Scientific Computing Research, under the Accelerated Research in Quantum Computing (ARQC) program, the A. P. Sloan foundation and the David and Lucile Packard Foundation. Competing interests: C.M. is Chief Scientist for IonQ, Inc. and has a personal financial interest in the company.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Army Research Office (ARO)UNSPECIFIED
Department of Energy (DOE)DE-SC0020312
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0161
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Gordon and Betty Moore FoundationGBMF-12500028
Walter Haefner FoundationUNSPECIFIED
ETH Zürich FoundationUNSPECIFIED
Vannever Bush Faculty FellowshipUNSPECIFIED
Alfred P. Sloan FoundationUNSPECIFIED
David and Lucile Packard FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20220202-191905591
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:113224
Deposited By: George Porter
Deposited On:02 Feb 2022 19:35
Last Modified:02 Feb 2022 22:22

Repository Staff Only: item control page