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.
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.Attached Files
Submitted - 2112.05156.pdf
Files
2112.05156.pdf
Additional details
Identifiers
- Eprint ID
- 113224
- Resolver ID
- CaltechAUTHORS:20220202-191905591
Related works
- Describes
- http://arxiv.org/abs/2112.05156 (URL)
Funding
- Army Research Office (ARO)
- 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
- NSF
- OMA-2016245
- NSF
- PHY-1125565
- Gordon and Betty Moore Foundation
- GBMF-12500028
- Dr. Max Rössler
- Walter Haefner Foundation
- ETH Zürich Foundation
- NSF
- DMR-1747426
- Vannever Bush Faculty Fellowship
- Alfred P. Sloan Foundation
- David and Lucile Packard Foundation
Dates
- Created
-
2022-02-02Created from EPrint's datestamp field
- Updated
-
2023-06-02Created from EPrint's last_modified field
Caltech Custom Metadata
- Caltech groups
- Institute for Quantum Information and Matter