A Quantum-Classical Hybrid Algorithm for Solving Satisfiability Problems

We design and test a hybrid algorithm to solve Boolean Satisfiability Problems (SAT). SAT problems are NP-complete and the algorithms used to solve them require exponential time at worst case. A quadratic speedup over classical algorithms can be obtained by using Quantu Amplitude Amplification. The algorithm we consider is built with IBM Quantum lab and Qiskit.