A Generic Variable Inputs Quantum Algorithm for 3-SAT Problem
Ping Wang, Guangqiang Liu, Liyan Liu · 2020
The Grover's algorithm can find an item satisfying certain properties in a search space of size N with circuit complexity $O\left( {\sqrt N } \right)$, where the circuit are formed by the G operator one by one in series. The huge circuit scale is the main obstacle to the practical application of the Grover's algorithm. In this paper, we present a generic variable inputs quantum algorithm by time-space tradeoff to reduce the scale of the quantum circuit. We combine the proposed algorithm in the paper with the Schöning's algorithm to solve the 3-SAT problem which is a NP-complete problem. Compared with previous algorithms, as the input variables n of 3-SAT problem increases, the advantages of our algorithm is obvious.