Research On Quantum Search Algorithms

Communication has been important to human societies. However, on many occasions, information needs to be kept secret from others. In order to solve the problem, cryptography is invented and becomes more and more consummate with the improvement of society and development of science. The appearance of computer especially makes the cryptography more perfect, but also brings convenience to the deciphering.Early in the last century, there came into being a great theory, quantum mechanics. In recent years, scientists make use of the theory and combine it with information and computer science, which brings into being a new interdiscipline, quantum information. In quantum information, there exist many unbelievable miracles, such as "absolutely secure quantum cryptography" and "quantum teleportation". People also construct a series of quantum algorithms, such as "a quantum algorithm for large prime factorization" and "an unsettled database searching algorithm", which are actually beyond the corresponding classical algorithms.In classical computation, the steps searching the target exponentially increase with n, which is a great restriction for classical algorithms. It needs O(N) steps to search one target item when there are N (N=2~n) items in the database, where n denotes the number of bits of the database. In the nineties of last century, Grover presented a quantum search algorithm for randomly distributed database, that is, "an unsettled database searching algorithm" named after Grover, which makes sufficiently use of the superposition of quantum states in Hilbert space successfully decreasing the searching steps to polynomial order and obviously beyond classical algorithms.In this paper, we investigate the problem of "quantum partial search" basing on Graver's searching algorithm . Specifically, the partial search containing two target blocks are deeply researched. We begin with three targets randomly distributed in two blocks and further discuss t targets's databases are separated into K blocks, two of which are target blocks where there is one target in one target block. We get one equationwhich will give the optimal distribution of number of queries of Step 1 and 2 of the partialsearch.Secondly, we consider the influence caused by the difference of target numbers between twotarget blocks when t is definite and one of the two target blocks contains z targets. So thedifferent of target numbers between two target blocks is t - 2z . We obtain the equation(2zK -2t) cos(2α(?)) + (2(t- z)K- 2t) cos(2α(?)) -t(K-4) = 0 which will give the optimal distribution of number of queries of Step 1 and 2 of the partial search, and the optimal distributing ways by investigating the relation between the search steps and distributing ways.At last, we apply Grover's algorithm to impossible differential attack to grouping ciphers, which helps to get keys quickly.