Abstract
Recently, for the first time, two quantum computing experiments have surpassed the simulation capabilities of the world's top supercomputers. The computations performed by these experiments (random circuit sampling and boson sampling) have a caveat, however: there is no efficient way to classically verify that the results are correct. Thus, at the largest problem sizes that are out of reach of classical machines, correctness must be inferred. For a stronger demonstration of quantum computational advantage, experiments may perform a "proof of quantumness" in which passing the test classically is super-polynomially hard, but verifying the results is efficient (poly-time). In this talk, I will present a novel proof of quantumness that mirrors the structure of a Bell test, but replaces correlations between two qubits with a correlation between one qubit and a cryptographically protected secret. After describing the protocol, I will focus on innovations that significantly improve the practicality of implementing the test on NISQ devices.