Research On Optimized Quantum Random-Walk Search Algorithm

The rapid development of quantum information technology has a huge impact on modern cryptography. Quantum search algorithm has become an important research direction in quantum computation with its powerful computing capacity. However, errors in the implementation of quantum algorithms are inevitable, which will affect the validity of quantum algorithms. Meanwhile, the search space can also contain multi-solution. Therefore, it has great theoretical significance and practical value to research the effects of errors on the quantum search algorithm and the quantum search algorithm under the condition of multi-solution. In recent years, quantum random walk has become one of the research topics in quantum algorithm. The main reason is that the search algorithms based on quantum random walks not only can search the unordered database but also solve other problems that Grover’s algorithm can not solve effectively, including spatial search and element distinctness. Therefore, the search algorithm based on quantum random walks has attracted great attention. In 2003,Shenvi, Kempe and Whaley proposed an algorithm based on quantum random walks on the hypercube, i.e., SKW algorithm. In 2008, Potocek proposed the optimized SKW algorithm. In this thesis, we have further researched on the optimized SKW algorithm. The main works and creations are as follows:1. The study of the systematic errors in the optimized SKW algorithm based on the Grover operator. Using the geometric description of this algorithm, a model of the algorithm with phase errors is established. For a given database size, the relationship between the success rate of the algorithm, the number of iterations, and the phase error is determined. For a given phase error, we obtain the maximum success rate of the algorithm, the required number of iterations and the error tolerance. Analysis and numerical simulations show that the success rate variation of the optimized SKW algorithm is smaller than that of Grover’s algorithm for the same phase error, meaning the optimized SKW algorithm is more robust against phase errors than Grover’s algorithm.2. The study of decoherence in the optimized SKW algorithm. The link in the hypercube will break randomly which leads to decoherence in the optimized SKW algorithm. Through introducing the shift operator which includes broken links, the optimized SKW algorithm with decoherence is proposed. For a given decoherence rate, we obtain the maximum success rate of the algorithm and the required number of iterations with simulations and sampling analysis. In view of decoherence will reduce the number of iterations, but also reduces the maximum success rate of the algorithm, we give the probability complexity when the algorithm is in the presence of decoherence. Then we obtain two critical values of the decoherence rate, and depict the relationship between the decoherence rate and the probability complexity when the decoherence rate varies in different intervals of the critical values.3. The study of multi-solution search of the optimized SKW algorithm. Using the mathematical induction, we obtain the method to get the computational complexity of the abstract search algorithm under the multi-solution case which solves the multi-solution search problem of the abstract search algorithm. Through proving that the SKW algorithm under the multi-solution case is just the abstract search algorithm on the hypercube, we obtain the computational complexity of the optimized SKW algorithm with multi-solution. We obtain a critical value of the proportion of solutions with simulations. When the given proportion of solutions is not more than the critical value, we depict the relationship between the success rate of the algorithm, the proportion of solutions, and the number of iterations.