Comparing Grover's Quantum Search Algorithm with Classical Algorithm on Solving Satisfiability Problem
Abstract:
The emergence of quantum computing provides us the possibility of solving tasks that might take years classically in just a few minutes. For certain problems, quantum computing exhibits quantum supremacy, meaning that the quantum solution runs exponentially faster than classical algorithms and is able to completely take over classical computers. This high efficiency of quantum computing comes not only from the hardware but also the software, quantum algorithms. The algorithms utilize the qubits to make calculations in order to fulfill specific tasks with the lowest time complexity possible. One such algorithm is named the Grover's algorithm, which is able to perform database search in O(sqrt(N)), and it runs much faster than the traditional algorithm that takes O(N) time. For example, when the task is to find the even integers from N integers, traditional computation will need to run through all of the N integers one by one, making at least N steps of calculation, while by using Grover’s algorithm only around sqrt(N) calculations are needed. This exponential speed-up makes Grover's algorithm one of the most important quantum algorithms. Grover's algorithm has a wide application in many fields and is able to improve the time complexity exponentially. One area that can be solved using Grover's algorithm is the satisfiability problem. This type of problem asks the computer to find a set of values (commonly true or false) for several variables such that they satisfy certain constraints. We use k-SAT problems to refer to satisfiability problems with k boolean variables to be determined. Grover’s algorithm can effectively solve the k-SAT problem by performing the database search on 2^N possible states of the variables. The algorithm’s square root optimization on searching helps to improve the efficiency of this solution significantly. Furthermore, this optimization of Grover's algorithm may play a more important role when k grows larger, and consequently the efficiency of the quantum solution could improve faster relative to the traditional solution. Yet this hypothesis is never tested due to the lack of a general k-SAT quantum algorithm. No quantum algorithms solving k-SAT problems where k is greater than 3 have been proposed, thus no test has been performed to compare the quantum solution and the classical solution on more general k-SAT problems. In this research, we formulate a general quantum solution for k-SAT problem and compare such solution with the best classical algorithm to determine whether and when the quantum algorithm performs better on satisfiability problems. The comparison will be done through both theoretical deduction as well as real-world implementation. At the end of this research, we will determine whether the proposed quantum algorithm outperforms the classical algorithm on solving k-satisfiability problems.Bibliography/Citations:
D. Monroe, "Bouncing Balls and Quantum Computing," ''Communications of the ACM'', vol. 63, no. 10, Oct., pp. 10-12, 2020.
Ashley Montanaro, "Quantum algorithms: an overview," Nature, Jan. 12, 2016. [Online]. Available: https://www.nature.com/articles/npjqi201523. [Accessed Oct.7, 2020]
Srinivasan K, Satyajit S, Behera BK, Panigrahi PK. Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience. arXiv preprint arXiv:1805.10928. 2018 May 28.
Fernandes, Diogo, and Inês Dutra. "Using Grover's search quantum algorithm to solve Boolean satisfiability problems: Part I." XRDS: Crossroads, The ACM Magazine for Students 26.1 (2019): 64-66.
Fernandes, Diogo, Carla Silva, and Inês Dutra. "Using Grover's search quantum algorithm to solve Boolean satisfiability problems, part 2." XRDS: Crossroads, The ACM Magazine for Students 26.2 (2019): 68-71.
Ambainis, Andris, et al. "Quantum speedups for exponential-time dynamic programming algorithms." Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2019.
Srinivasan, Karthik, Bikash K. Behera, and Prasanta K. Panigrahi. "Solving linear systems of equations by gaussian elimination method using Grover’s search algorithm: an IBM quantum experience." arXiv preprint arXiv:1801.00778 (2018).
Additional Project Information
Project files
Research Plan:
A. Addressed Question
The purpose of this research is to determine whether and when quantum algorithm performs better than traditional algorithm on solving k-satisfiability problem where k grows larger. The quantum solution using Grover's algorithm can have a square root of N optimization when compared with traditional algorithms, and this difference will be magnified when k become larger. Therefore, it is worth investigating for what k values will the quantum algorithm outperforms the traditional ones.
B. Goal & Hypothesis
The goal is to determine whether and when quantum algorithm performs better than traditional algorithm on solving k-satisfiability problem where k grows larger. I hypothesize that the quantum solution will gradually exceeds the traditional solution on computational complexity when k grows larger.
C. Methodology
First, I will study the traditional algorithms and determine the optimal existing solution for general SAT problem. Then, I will investigate in a quantum solution for 3-SAT problem and device a quantum circuit on a quantum simulator that can successfully solve 3-SAT problem. Then, I will extend this solution to more general cases of k-SAT problem, and calculate the theoretical computational complexity for any given k. Afterwards, I will run the quantum solution on a real quantum computer and optimal traditional solution on classical computer to compare their run time.
For data analysis, I will compare the two theoretical complexities and map them together across different k values. This way I can achieve the theoretical comparison and determine whether in theory the quantum method performs better. Then, I will use the real-world testing result to compare with the theoretical predictions to further enhance the strength of my conclusion.
D. Bibliography
D. Monroe, "Bouncing Balls and Quantum Computing," ''Communications of the ACM'', vol. 63, no. 10, Oct., pp. 10-12, 2020.
Ashley Montanaro, "Quantum algorithms: an overview," Nature, Jan. 12, 2016. [Online]. Available: https://www.nature.com/articles/npjqi201523. [Accessed Oct.7, 2020]
Srinivasan K, Satyajit S, Behera BK, Panigrahi PK. Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience. arXiv preprint arXiv:1805.10928. 2018 May 28.
Fernandes, Diogo, and Inês Dutra. "Using Grover's search quantum algorithm to solve Boolean satisfiability problems: Part I." XRDS: Crossroads, The ACM Magazine for Students 26.1 (2019): 64-66.
Fernandes, Diogo, Carla Silva, and Inês Dutra. "Using Grover's search quantum algorithm to solve Boolean satisfiability problems, part 2." XRDS: Crossroads, The ACM Magazine for Students 26.2 (2019): 68-71.
Ambainis, Andris, et al. "Quantum speedups for exponential-time dynamic programming algorithms." Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2019.
Srinivasan, Karthik, Bikash K. Behera, and Prasanta K. Panigrahi. "Solving linear systems of equations by gaussian elimination method using Grover’s search algorithm: an IBM quantum experience." arXiv preprint arXiv:1801.00778 (2018).
Questions and Answers
1. What was the major objective of your project and what was your plan to achieve it?
Satisfiability problem is a fundamental problem in computer science, and can be applied in areas including combinatorial equivalence checking, automatic test pattern generation, model checking, AI planning, and haplotyping. The traditional solution often requires extensive memory and computation time. Quantum computing has a huge advantage over classical computation due to its parallel computing ability. One of the few existing quantum algorithms is the Grover’s algorithm, which performs database searching much faster than classical algorithms. Since Grover’s algorithm can be used to solve the satisfiability problem, it is possible that when the data becomes large, the quantum solution will be able to out-perform the classical algorithm. Thus, the goal of this research is to determine whether and when a quantum algorithm performs better than a traditional algorithm on solving k-satisfiability problems where k grows larger. I hypothesize that the quantum solution will gradually exceed the traditional solution on computational complexity when k grows larger. First, I will study the traditional algorithms and determine the optimal existing solution for the general SAT problem. Then, I will investigate a quantum solution for the 3-SAT problem and device a quantum circuit on a quantum simulator that can successfully solve the 3-SAT problem. Then, I will extend this solution to more general cases of k-SAT problem, and calculate the theoretical computational complexity for any given k. Afterwards, I will run the quantum solution on a real quantum computer and optimal traditional solution on a classical computer to compare their run time
a. Was that goal the result of any specific situation, experience, or problem you encountered?
Yes. I was extremely interested in Grover's quantum algorithm, and this research topic was determined based on my interest.
When our school announced a research program, my field was, without question, computer science; I chose this because of my interest in the algorithm itself. Grover’s algorithm can perform database searches with a square root optimization. This is so fascinating largely because of my previous experiences with classical algorithms. Traditionally, the search must be done with at least N steps, but with the introduction of quantum computing, solutions with time complexity of the square root of N can be easily implemented. This captured me immediately. How can something that is nearly a rule for a traditional computer be broken down? Nothing but quantum computing can provide an answer. The distinct differences of quantum computing versus classical are the novel approaches of solving problems, and the possibilities of new systems of computation are why I am eager to leap into further research opportunities.
b. Were you trying to solve a problem, answer a question, or test a hypothesis?
My research is trying to answer whether and when the quantum satisfiability problem solution performs better than the classical one. The hypothesis is that the quantum solution will gradually exceed the traditional one when k in k-SAT grows larger. If this is eventually proved, then this algorithm can be applied in many fields and be used to solve existing problems that are based on satisfiability problem.
2. What were the major tasks you had to perform in order to complete your project?
The major tasks involve to device a quantum solution for general satisfiability problem, to calculate the quantum solution's computational complexity, to find the optimal classical solution, and to compare these two solutions theoretically and in real world.
a. For teams, describe what each member worked on.
N/A.
3. What is new or novel about your project?
a. Is there some aspect of your project's objective, or how you achieved it that you haven't done before?
The existing research only proposed a limited quantum solution for 3-SAT problem, and my research aims at a general solution for all SAT problems and adds a comparison of the proposed quantum solution against classical solution.
b. Is your project's objective, or the way you implemented it, different from anything you have seen?
No research have focused on this objective previously.
c. If you believe your work to be unique in some way, what research have you done to confirm that it is?
I have searched for satisfiability problem papers and Grover's algorithm solutions, and none of the resulting papers completed my objective. The closest one I discovered was a solution using Grover's algorithm on 3-SAT problem.
4. What was the most challenging part of completing your project?
a. What problems did you encounter, and how did you overcome them?
One problem was the mathematical foundation required for doing quantum computing. Most parts of quantum computing require the use of linear algebra for description and analysis, but I did not learn linear algebra when I started the research. Therefore, I had to study myself about this subject and related mathematical tools.
b. What did you learn from overcoming these problems?
I learned self-studying skills and how to better prepare the related background knowledge in future research.
5. If you were going to do this project again, are there any things you would you do differently the next time?
Yes. I would organize the papers I encountered during literature review more thoroughly and in more details to make it more convenient later.
6. Did working on this project give you any ideas for other projects?
Yes. In the future, I will be working on Grover's algorithm even more deeply because I realized that the potential of this algorithm is more than solving satisfiability problems. I might also dive deeper into the solution that I have proposed and extend it to real life problems to optimize them. The results from this reseach can be used to develop more complicated satisfiability problem and thus can be applied to many areas in our life, and this might be a future direction for me.
7. How did COVID-19 affect the completion of your project?
The pandemic separated me and my mentor, which results in limited contact and restricted conversations because of the time zone difference. This reduced our communication opportunities.