Interactive Test for Classically-Verifiable Quantum Advantage

An interactive test of quantum advantage is a protocol in which a verifier issues challenges constructed from cryptographic functions to a prover, so as to verify whether the prover’s computational capability is beyond the classical limit. Since the prover’s responses to these challenges can be efficiently tested by the verifier with only classical computation, these protocols provide a scalable approach for the demonstration of quantum advantage.

We present the first implementation of an interactive test of quantum advantage on an ion-trap quantum computer; we execute two complementary protocols---one where the cryptographic construction implements a modified Bell test and another based on the learning with errors problem. To perform multiple rounds of interaction, we use a split-and-shuttle approach to realize mid-circuit measurements on a subsystem, with subsequent coherent evolution. For both protocols, the fidelities exceed the asymptotic bound for classical behavior; maintaining this fidelity at scale would conclusively demonstrate verifiable quantum advantage.