Procedure of Solving 3-SAT Problem by Combining Quantum Search Algorithm and DPLL Algorithm
DOI: 10.23977/cpcs.2020.41003 | Downloads: 18 | Views: 1522
Author(s)
Runkai Zhang 1, Jing Chen 2, Huiling Zhao 2
Affiliation(s)
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 Author
Huiling ZhaoABSTRACT
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.
KEYWORDS
3-SAT problems, Quantum search algorithm, DPLL algorithmCITE 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
REFERENCES
[1] S. Cook (1971) The complexity of theorem-proving procedures. 151–158.
[2] M. Davis, G. Logemann, and D. Loveland (1962) A machine program for theorem-proving, Commun. ACM, 5, (7), 394-397.
[3] A. Biere, M. Heule, H. Maaren, and T. Walsh (2009) Handbook of satisfifiability: Volume 185 frontiers in artifificial intelligence and applications.
[4] A. Leporati, and S. Felloni (2007) Three quantum algorithms to solve 3-sat. Theoretical Computer Science, 372, 218-241.
[5] J. Wang, J. Chen, C. Yu, and L. Wang (2012) A quantum method to test the satisfifiability of boolean functions. 1-5.
[6] L. Grover (1996) Fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on the Theory of Computing.
[7] J. C. Garcia-Escartin, P. Chamorro-Posada (2011) Equivalent quantum circuits.
[8] 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.
[9] Z. Diao, M. Zubairy, and G. Chen (2002) A quantum circuit design for grover’s algorithm. Zeitschrift f¨ur Naturforschung, A 57.
[10] 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.
[11] S.-T. Cheng, and M.-H. Tao (2007) Quantum cooperative search algorithm for 3- sat. Journal of Computer and System Sciences, 73, 123-136.
[12] A. Montanaro (2015) Quantum walk speedup of backtracking algorithms. Theory of Computing, 14.
[13] M. Jarret, and K. Wan (2018) Improved quantum backtracking algorithms using effective resistance estimates. Physical Review, A 97.
Downloads: | 1915 |
---|---|
Visits: | 97930 |
Sponsors, Associates, and Links
-
Power Systems Computation
-
Internet of Things (IoT) and Engineering Applications
-
Journal of Artificial Intelligence Practice
-
Advances in Computer, Signals and Systems
-
Journal of Network Computing and Applications
-
Journal of Web Systems and Applications
-
Journal of Electrotechnology, Electrical Engineering and Management
-
Journal of Wireless Sensors and Sensor Networks
-
Journal of Image Processing Theory and Applications
-
Mobile Computing and Networking
-
Vehicle Power and Propulsion
-
Frontiers in Computer Vision and Pattern Recognition
-
Knowledge Discovery and Data Mining Letters
-
Big Data Analysis and Cloud Computing
-
Electrical Insulation and Dielectrics
-
Crypto and Information Security
-
Journal of Neural Information Processing
-
Collaborative and Social Computing
-
International Journal of Network and Communication Technology
-
File and Storage Technologies
-
Frontiers in Genetic and Evolutionary Computation
-
Optical Network Design and Modeling
-
Journal of Virtual Reality and Artificial Intelligence
-
Natural Language Processing and Speech Recognition
-
Journal of High-Voltage
-
Programming Languages and Operating Systems
-
Visual Communications and Image Processing
-
Journal of Systems Analysis and Integration
-
Knowledge Representation and Automated Reasoning
-
Review of Information Display Techniques
-
Data and Knowledge Engineering
-
Journal of Database Systems
-
Journal of Cluster and Grid Computing
-
Cloud and Service-Oriented Computing
-
Journal of Networking, Architecture and Storage
-
Journal of Software Engineering and Metrics
-
Visualization Techniques
-
Journal of Parallel and Distributed Processing
-
Journal of Modeling, Analysis and Simulation
-
Journal of Privacy, Trust and Security
-
Journal of Cognitive Informatics and Cognitive Computing
-
Lecture Notes on Wireless Networks and Communications
-
International Journal of Computer and Communications Security
-
Journal of Multimedia Techniques
-
Automation and Machine Learning
-
Computational Linguistics Letters
-
Journal of Computer Architecture and Design
-
Journal of Ubiquitous and Future Networks