Quantum verification of NP problems with single photons and linear optics

Area of Science:

• Quantum Information Science
• Computational Complexity Theory
• Photonic Quantum Computing

Background:

• Nondeterministic-polynomial-time (NP) problems, such as the satisfiability of constraints (SAT), are computationally intractable for classical computers.
• Verifying NP problems classically requires a complete O(n)-bit proof for an instance of size n, based on the exponential time hypothesis.
• Quantum computing offers a potential pathway to efficiently verify NP problems by encoding solutions in qubits.

Purpose of the Study:

• To realize a quantum verification machine for SAT instances using photonic technology.
• To demonstrate the feasibility of quantum verification for both satisfiable and unsatisfiable SAT instances.
• To explore the potential for quantum advantage in solving complex computational problems.

Main Methods:

• Implementation of a quantum verification machine utilizing single photons and linear optics.
• Employment of tunable optical setups for efficient verification of SAT instances.
• Utilization of unentangled photons, linear optical operations, and two-photon joint measurements.

Main Results:

• Successful verification of both satisfiable and unsatisfiable SAT instances using the photonic quantum machine.
• Achievement of a distinct completeness-soundness gap, even with experimental imperfections.
• Demonstration of a protocol suitable for photonic realization and scalable with technological advancements.

Conclusions:

• The developed photonic quantum verification machine offers a novel approach to tackling NP-hard problems like SAT.
• The protocol's reliance on unentangled photons and linear optics makes it practical for current and future photonic quantum computing systems.
• This work represents a significant step towards achieving quantum advantage and expanding the computational power of optical quantum computers.