Quantum verification of NP problems with single photons and linear optics

Abstract

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.

20 pages, 15 figures

References in corpus (9)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Photonic quantum technologies
• Quantum computational advantage using photons
• Integrated Photonic Quantum Technologies
• Photonic Boson Sampling in a Tunable Circuit
• A 2D Quantum Walk Simulation of Two-Particle Dynamics
• N-representability is QMA-complete
• Quantum advantage for computations with limited space
• Experimental demonstration of quantum advantage for NP verification with limited information

Cited by in corpus (6)

• A robust approach for time-bin encoded photonic quantum information protocols
• Experimental benchmarking of quantum state overlap estimation strategies with photonic systems
• Quantum optical classifier with superexponential speedup
• Efficient Light Propagation Algorithm using Quantum Computers
• Verification of single-photon path entanglement using a nitrogen vacancy center
• Quantum optical shallow networks