Experimental demonstration of quantum advantage for NP verification with limited information

Abstract

Most demonstrations of quantum advantages with optics rely on single photons, and are thus difficult to scale up. Here, the authors use coherent states to demonstrate a quantum advantage for the task of verifying the solution to a NP-complete problem when only partial information on the solution is available.