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 [Formula: see text] qubits. Here we realize the quantum verification machine of SAT with single photons and linear optics. By usi

SUBMITTER: Zhang A 

PROVIDER: S-EPMC8373877 | biostudies-literature | 2021 Aug

REPOSITORIES: biostudies-literature