Classical verification of quantum computational advantage

An important milestone on the path to application-ready quantum computing is the demonstration of quantum computational advantage: solving some problem faster on a quantum computer than would be possible on any classical computer. Excitingly, several experiments have already performed sampling problems which are believed to be intractable for even the world's top supercomputers. But a challenge arises in the verification of these experiments: checking the quantum computer's output requires exponential classical resources, so correctness can be verified for only moderate problem sizes. Here we present protocols for efficiently-verifiable quantum advantage, through cryptographic "proofs of quantumness." These protocols have the combined advantages of polynomial-time classical verification, and security against even adversarial classical impostors via well-studied cryptographic hardness assumptions. After discussion of the protocols we present progress toward their implementation on near-term quantum devices.