Procedure of Solving 3-SAT Problem by Combining Quantum Search Algorithm and DPLL Algorithm
DOI: 10.23977/cpcs.2020.41003 | Downloads: 7 | Views: 258
Runkai Zhang 1, Jing Chen 2, Huiling Zhao 2
1 Miami college of Henan University, Henan University, Kaifeng, 475004, P. R. China
2 School of Physics and Electronics, Henan University, Kaifeng, 475004, P. R. China
Corresponding AuthorHuiling Zhao
Although some classical algorithms have been applied to solve the satisfiability problem, more effective methods are still explored because existing algorithms are constrained by inadequate computing capability of traditional computers. The parallelism of quantum computation makes quantum algorithms with promising potential to improve the computing ability, but existing quantum algorithms still require too large number of qubits to solve a simple problem effectively. In this paper, an optimized data structure was structured to solve Boolean satisfiability problem by utilizing Grover's algorithm, and then the corresponding formula was proposed to balance variables in consideration of complexity. With reasonable simplification, quantum circuits were built to decrease the number of qubits required in Grover's algorithm. The result of verification experiment further demonstrated that the proposed approach is simple, reliable and of a certain practical value.
KEYWORDS3-SAT problems, Quantum search algorithm, DPLL algorithm
CITE THIS PAPER
Runkai Zhang, Jing Chen and Huiling Zhao, Procedure of Solving 3-SAT Problem by Combining Quantum Search Algorithm and DPLL Algorithm Computing, Performance and Communication Systems (2020) Vol. 4: 14-24. DOI: http://dx.doi.org/10.23977/cpcs.2020.41003
 S. Cook (1971) The complexity of theorem-proving procedures. 151–158.
 M. Davis, G. Logemann, and D. Loveland (1962) A machine program for theorem-proving, Commun. ACM, 5, (7), 394-397.
 A. Biere, M. Heule, H. Maaren, and T. Walsh (2009) Handbook of satisfifiability: Volume 185 frontiers in artifificial intelligence and applications.
 A. Leporati, and S. Felloni (2007) Three quantum algorithms to solve 3-sat. Theoretical Computer Science, 372, 218-241.
 J. Wang, J. Chen, C. Yu, and L. Wang (2012) A quantum method to test the satisfifiability of boolean functions. 1-5.
 L. Grover (1996) Fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on the Theory of Computing.
 J. C. Garcia-Escartin, P. Chamorro-Posada (2011) Equivalent quantum circuits.
 C. Figgatt, D. Maslov, K. Landsman, N. Linke, S. Debnath, and C. Monroe (2017) Complete 3-qubit grover search on a programmable quantum computer. Nature Communications, 8.
 Z. Diao, M. Zubairy, and G. Chen (2002) A quantum circuit design for grover’s algorithm. Zeitschrift f¨ur Naturforschung, A 57.
 D. Fernandes, and I. Dutra (2019) Using grover’s search quantum algorithm to solve Boolean satisfiability problems: Part i, XRDS: Crossroads. The ACM Magazine for Students, 26, 64-66.
 S.-T. Cheng, and M.-H. Tao (2007) Quantum cooperative search algorithm for 3- sat. Journal of Computer and System Sciences, 73, 123-136.
 A. Montanaro (2015) Quantum walk speedup of backtracking algorithms. Theory of Computing, 14.
 M. Jarret, and K. Wan (2018) Improved quantum backtracking algorithms using effective resistance estimates. Physical Review, A 97.