Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems

Abstract

We present an exact quantum algorithm for solving the Exact Satisfiability problem, which belongs to the important NP-complete complexity class. The algorithm is based on an intuitive approach that can be divided into two parts: the first step consists in the identification and efficient characterization of a restricted subspace that contains all the valid assignments of the Exact Satisfiability; while the second part performs a quantum search in such restricted subspace. The quantum algorithm can be used either to find a valid assignment (or to certify that no solution exists) or to count the total number of valid assignments. The query complexities for the worst-case are respectively bounded by $O(\sqrt{{2}^{n-{M}^{\prime }}})$ and $O({2}^{n-{M}^{\prime }})$ , where n is the number of variables and ${M}^{\prime }$ the number of linearly independent clauses. Remarkably, the proposed quantum algorithm results to be faster than any known exact classical algorithm to solve dense formulas of Exact Satisfiability. As a concrete application, we provide the worst-case complexity for the Hamiltonian cycle problem obtained after mapping it to a suitable Occupation problem. Specifically, we show that the time complexity for the proposed quantum algorithm is bounded by $O({2}^{n/4})$ for 3-regular undirected graphs, where n is the number of nodes. The same worst-case complexity holds for $(3,3)$ -regular bipartite graphs. As a reference, the current best classical algorithm has a (worst-case) running time bounded by $O({2}^{31n/96})$ . Finally, when compared to heuristic techniques for Exact Satisfiability problems, the proposed quantum algorithm is faster than the classical WalkSAT and Adiabatic Quantum Optimization for random instances with a density of constraints close to the satisfiability threshold, the regime in which instances are typically the hardest to solve. The proposed quantum algorithm can be straightforwardly extended to the generalized version of the Exact Satisfiability known as Occupation problem. The general version of the algorithm is presented and analyzed.

Keywords

• quantum algorithm
• exact satisfiability
• NP-complete problem
• computational complexity