Research On The Quantum Search Algorithms

Grover's quantum search algorithm is an exhaustive algorithm on quantum computer, which is concerned because of its quadratic speed and broad utility. This paper will analyze the quantum search algorithms deeply and thereby study some methods to improve the probability of success and reduce the computational complexity in some specific situations. Our contributions mainly include the following three parts:1. Research on quantum search algorithm based on phase shifts. We will concentrate on the relation among the success probability of the algorithm, the phase shifts, the number of target items and the number of iterations via replacing theÏ€phase shift of Grover's quantum algorithm by phase shifts of an arbitraryΦ=φ(0≤Φ,φ≤2Ï€). Then, we will find out the optimal phase shifts and the minimum of the success probability when the number of iterations is given in advance, which can help us design a new quantum search algorithm. Additionally, we will present two new quantum search algorithms based on the optimal phase shifts of 1.018 and 0.062 after(?)and(?) iterations respectively, which can search a database containingarbitrary target items with the probability of success at least 93.43% and 99.96% respectively.2. Research on quantum partial search algorithm. We will research on the case of partial search algorithm that the number of target items is arbitrary in each target block. And we depict the change of amplitude of items under operating Grover's iteration in different target blockes. Then we will give a condition to guarantee that the partial search algorithm can be finished with the minimal number of queries to oracle and certainty. Finally, by further numerical computing we will come to the relation between the distribution of target items and the number of queries.3. Research on quantum mechanical meet-in-the-middle algorithm. Aiming at the key-divisible cipher, we will present a quantum mechanical meet-in-the-middle algorithm by inosculating meet-in-the-middle attack and Grover's quantum algorithm, which can reduce the computational complexity by increasing the memory complexity. Moreover, we present an attack algorithm on the three-key triple-DES, of which the computational complexity is O(56×2⁵⁶) andthe memory complexity is O(2⁵⁶).