  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 $\tilde{O}(\sqrt{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.
Our results open an essentially new route towards quantum advantages and extend
the computational capability of optical quantum computing.
