Experimental demonstration of quantum advantage for NP verification with limited information

This paper presents an experimental demonstration of quantum computational advantage in verifying NP-complete problems. A verifier with limited information about the proof (in the form of unentangled quantum states) efficiently verifies the problem using a linear optical implementation. Strong evidence suggests a classical computer would require significantly more time (assuming exponential time to solve NP-complete problems). While the advantage is specific to this scenario, it paves the way for potential applications like server-client quantum computing.

Federico Centrone, Niraj Kumar, Eleni Diamanti, Iordanis Kerenidis