  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.
