The Improvement And Application Of Grover's Algorithm

Quantum computing is a new interdisciplinary subject that uses particles for information processing and storage.The research shows that quantum computing with powerful quantum parallelism is superior to classical computing in some aspects.For example,the Grover algorithm can solve the inverse function problem with O(N^1/2).Thus this quantum algorithm achieves a quadratic speedup over classical algorithm.The Grover algorithm not only has powerful parallel computing capabilities,but also has broad application prospects,so it has been paid attention to by researchers.In this paper,the improvement and application of the Grover algorithm are studied.From the perspective of reducing the quantum circuit of the Grover algorithm,based on the previous research,the Grover algorithm is deeply analyzed.Two improved algorithms are proposed in the paper.The main contributions are summarized as follows:?1?Based on the Grover algorithm,this paper combines classical verification with the quantum algorithm and proposes a probabilistic Grover algorithm?called PGA?.In order to reduce the quantum circuit complexity of the Grover algorithm,this paper first designs a classical verification function.Then the PGA quantum circuit,algorithm step and algorithm geometry process are designed.Finally,the performance of the algorithm is analyzed from three aspects:quantum circuit,geometric process and algorithm process.And the four algorithms is compared.The analysis results show that the PGA applies multiple measurements and classical function verification.After O(?N^1/2/8) iterations,the solution can be found with a probability greater than 1/2.The quantum circuit of PGA is less than the Grover algorithm,and its quantum circuit complexity is O(?N^1/2/8).?2?The subset sum problem is a NP-complete problem,which is also an important class of difficult mathematical problems in cryptography.Applying the probabilistic Grover algorithm?PGA?to subset sum problem,combined with meet-in-the-middle algorithm?called CMMA?,this paper proposes a probabilistic quantum meet-in-the-middle algorithm?called PQMMA?to solve the subset sum problem.First,the CMMA idea is used to divide the elements in the subset sum problem.Then the CMMA idea is applied to design a new oracle function.Finally,the new oracle function is applied to the PGA,and PQMMA is designed from the aspects of algorithm step and geometric process.The analysis results show that PQMMA applies multiple measurements and classical verification,reducing the quantum circuit at the cost of the algorithm's success probability.The quantum circuit complexity of PQMMA is O(?2^?n-1?/3/8).