Investigations On Quantum Random-Walk Search Algorithm

The studies of quantum computation and quantum information can be traced back to several decades ago. A large progress occurred in the middle of 90s, 20th century, during which Shor's fast algorithm for factoring and Grover search algorithm were found. Those two kinds of algorithm suggest that, indeed, quantum computers might have computational powers exceeding those of classical computers. In recent years, the quantum random-walk (QRW) is receiving significant attention, because it is a natural generalization of classical random walks to quantum systems, and because quantum random walks could be useful in constructing efficient quantum algorithms.In this paper, we investigate a quantum search algorithm based on the quantum random-walk, i.e., the quantum random-walk search algorithm, which has nearly the same speed as the Grover search algorithm. Then, we study how varieties of noise affect such algorithm. We set up two different noise models. First, we assume that the Grover diffusion operator used in the algorithm is not applied perfectly, i.e., there is a noise in phase inversions. As is well known, any phase inversion operation is imperfect, so there is an uncertainty. We study the effect of such phase noise and demonstrate how it acts on the result of the search algorithm. The corresponding work of gate imperfection in the Grover search algorithm has been already studied. Nevertheless, our studies show notable differences, as well as similarities, in the response of the two algorithms to noise. Second, we investigate the white noise in the QRW search algorithm. In any search algorithm, decoherence will occur in each step, and therefore it may inevitably alter the probabilities of the states in the final output. We model such kind of noise by assuming that in each step of the algorithm, a white or Gaussian noise modifies the state of the whole database. We show the corresponding numerical calculations and analytical approximations.Our works are useful to make a profound comparison between the Grover search algorithm and the QRW search algorithm, and are helpful for investigating the application of the quantum search algorithm.