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 important but intractable problems like the satisfiability of potentially conflict constraints(SAT).According to the well-founded exponential time hypothesis,verifying an SAT instance of size n requires generally the complete solution in an O(n)-bit proof.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 O~(Õ−−√n)qubits.Here we realize the quantum verification machine of SAT with single photons and linear optics.By using tunable optical setups,we efficiently verify satisfiable and unsatisfiable SAT instances and achieve a clear completeness-soundness gap even in the presence of experimental imperfections.The protocol requires only unentangled photons,linear operations on multiple modes and at most two-photon joint measurements.These features make the protocol suitable for photonic realization and scalable to large problem sizes with the advances in high-dimensional quantum information manipulation and large scale linear-optical systems.Our results open an essentially new route toward quantum advantages and extend the computational capability of optical quantum computing.