Experimental Implementation of an Efficient Test of Quantumness

A test of quantum advantage is a protocol in which a quantum device succeeds in challenges issued to it by a classical challenger and in which no efficient classical algorithm can also succeed in those challenges, under certain cryptographic assumptions. However, with the limited number of qubits on current devices, a true demonstration of quantum advantage can be difficult to implement. A reasonable first step towards this ultimate goal is to instead consider protocols which certify non-classical behavior. Recent attempts to implement such tests on current quantum computers rely on either interactive challenges with efficient verification, or non-interactive challenges with inefficient (exponential time) verification. In this paper, we execute an efficient non-interactive test of quantumness on an ion-trap quantum computer. Specifically, we perform a proof-of-principle demonstration of the protocol from Brakerski, et al 2020, which uses cryptographic primitives to certify non-classical behavior. Our results significantly exceed the bound for the success of a classical device, illustrating the non-classical behavior required of the quantum device.