Experimental demonstration of quantum advantage for NP verification

Abstract We show the first experimental demonstration of a computational quantum advantage (also referred to as quantum supremacy) with linear optics, by studying the computational task of the verification of an NP-complete problem by a verifier who only gets limited information about the proof. We provide a simple linear optical implementation that can perform this task efficiently (within a few seconds), while we also provide strong evidence that a classical computer would take time greater than the age of the universe (assuming only that classically it takes exponential time to solve an NP-complete problem). The verification of NP-complete problems with limited information brings us a step closer to real-world useful applications, such as server-client quantum computing.