Quantum verification of NP problems with single photons and linear optics

Quantum computing is seeking to realize hardware-optimized algorithms for application-related computational tasks. NP (nondeterministic-polynomial-time) is a complexity class containing many natural, important but intractable problems, in which the satisfiability of potentially conflict constraints (SAT) is a prominent problem being NP-complete. According to the exponential time hypothesis, SAT does not have sublinear verification algorithm, that is, verifying a SAT instance of size $n$ requires an $O(n)$-bit proof---generally the complete information about the solution. In contrast, quantum verification algorithms, which encode the solution into quantum bits rather than classical bit strings, can perform the verification task with quadratically reduced information about the solution in $\tilde{O}(\sqrt{n})$ qubits. Here we realize the quantum verification algorithm of SAT with single photons and linear optics. By using tunable optical setups, we test the completeness and soundness of the protocol in full cases and find high accuracies even in the presence of experimental imperfections. The two-prover protocol requires only unentangled photons, linear operations on multiple modes and at most two-photon interferences, which are suitable for photonic realization and scalable to large problem sizes. Our results open an essentially new route towards quantum advantages and give new insights on the capability of optical quantum computing.