A quantum method to test the satisfiability of Boolean functions
Jin Qiang Wang, Jialin Chen, Chaofan Yu, Linli Wang · 2012
Satisfiability (SAT) problem is one of the NP-hard problems. General SAT problem can be solved in polynomial time when the given formula contains only binary clauses (2-SAT). Quantum computation possesses some virtues that exceeding classical computation in speed, therefore it has the potential ability to solve NP-complete problems better than with classical methods. This paper introduces a new method to test the satisfiability of Boolean functions based on quantum ETOF gates.