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.

arXiv comment20 pages, 15 figures

References in corpus (28)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A variational eigenvalue solver on a quantum processor
• Photonic quantum technologies
• Quantum computational advantage using photons
• Integrated Photonic Quantum Technologies
• Universal Linear Optics
• Boson Sampling on a Photonic Chip
• Quantum Computational Supremacy
• Experimental Boson Sampling
• Photonic quantum information processing: a review
• Experimental boson sampling in arbitrary integrated photonic circuits
• Photonic Boson Sampling in a Tunable Circuit
• Experimental Demonstration of Blind Quantum Computing
• 18-qubit entanglement with photon's three degrees of freedom
• A 2D Quantum Walk Simulation of Two-Particle Dynamics
• N-representability is QMA-complete
• Witnessing eigenstates for quantum simulation of Hamiltonian spectra
• The SWAP test and the Hong-Ou-Mandel effect are equivalent
• Quantum computing on encrypted data
• Experimental verification of quantum computations
• Experimental Quantum Fast Hitting on Hexagonal Graphs
• Robust architecture for programmable universal unitaries
• Quantum advantage for computations with limited space
• Experimental demonstration of quantum advantage for NP verification with limited information
• Improved Soundness for QMA with Multiple Provers
• Quantum superiority for verifying NP-complete problems with linear optics

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