The Improvement And Application Of Quantum Search Algorithm

Quantum computing is a new type of computing model that relies on the principles of quantum mechanics to obtain a solution.Due to the parallel computing capabilities of quantum computing,quantum computing is more efficient than classical computing when solving certain problems.Grover quantum search algorithm is one of the most widely used algorithms in quantum algorithms.It can solve the search problem of size 2n with the quantum circuit complexity / O(2^n/2).In this paper,from the perspective of reducing the complexity of the quantum circuit of the Grover algorithm,two improved algorithms are proposed,and the improved algorithms are applied to the 3-SAT problem.1.In order to reduce quantum circuits,a variable input Grover algorithm is proposed.It uses the idea of time-space compromise to transform the original problem into multiple sub-problems,and uses the Grover algorithm to search for the target item in each sub-problem.The algorithm can find the solution of the original problem in the case of running time complexity /O(2^n/3) and quantum circuit complexity/O(2^n/3),when the running time complexity and quantum circuit complexity are balanced.Compared with the original Grover algorithm,this algorithm reduces the quantum circuit size from / O(2^n/2) to /O(2^n/3).2.After the variable input Grover algorithm is proposed,in order to further optimize the quantum circuit,for structured problems,according to the characteristics of the structured problem,a nested Grover algorithm with variable input is proposed.The algorithm mainly speeds up the operation by continuously expanding possible partial solutions and avoiding impossible partial solutions.The analysis results shows that the algorithm can find the solution of the original problem with running time complexity /O(2^n/3) and circuit complexity /O(2^n/3)?,where ? <1,and its value depends on the specific problem.Taking the 3-SAT problem as an example,then ? ?0.68.3.According to some common features between different non-solutions in the 3-SAT problem,the nested Grover algorithm with a variable input is combined with the classic Sch?ning's algorithm to solve the 3-SAT problem.The analysis results show that,compared with Sch?ning's algorithm and Grover algorithm,as the input variables n of 3-SAT problem increases,the advantages of our algorithm is more obvious.