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

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.

%8 12/9/2021 %G eng %U https://arxiv.org/abs/2112.05156 %0 Journal Article %D 2019 %T Quantum Computer Systems for Scientific Discovery %A Yuri Alexeev %A Dave Bacon %A Kenneth R. Brown %A Robert Calderbank %A Lincoln D. Carr %A Frederic T. Chong %A Brian DeMarco %A Dirk Englund %A Edward Farhi %A Bill Fefferman %A Alexey V. Gorshkov %A Andrew Houck %A Jungsang Kim %A Shelby Kimmel %A Michael Lange %A Seth Lloyd %A Mikhail D. Lukin %A Dmitri Maslov %A Peter Maunz %A Christopher Monroe %A John Preskill %A Martin Roetteler %A Martin Savage %A Jeff Thompson %A Umesh Vazirani %X

The great promise of quantum computers comes with the dual challenges of building them and finding their useful applications. We argue that these two challenges should be considered together, by co-designing full stack quantum computer systems along with their applications in order to hasten their development and potential for scientific discovery. In this context, we identify scientific and community needs, opportunities, and significant challenges for the development of quantum computers for science over the next 2-10 years. This document is written by a community of university, national laboratory, and industrial researchers in the field of Quantum Information Science and Technology, and is based on a summary from a U.S. National Science Foundation workshop on Quantum Computing held on October 21-22, 2019 in Alexandria, VA.

%8 12/16/2019 %G eng %U https://arxiv.org/abs/1912.07577 %0 Journal Article %D 2018 %T Quantum Supremacy and the Complexity of Random Circuit Sampling %A Adam Bouland %A Bill Fefferman %A Chinmay Nirkhe %A Umesh Vazirani %X

A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS satisfies an anti-concentration property, making it the first supremacy proposal with both average-case hardness and anti-concentration. 

%G eng %U https://arxiv.org/abs/1803.04402