Hitting times of quantum and classical random walks in potential spaces

The spatial search problem is an interesting and important problem in computer science and especially the area of algorithms. The objective is a marked site to be found in a finite physical space, that can be modeled as a finite lattice or a graph. Many approaches have been developed to address this problem. Classical random walks and quantum walks are efficient models that address the spatial search problem. Quantum walks is a universal model of quantum computation and can be mapped directly to quantum circuits and consequently executed on quantum computers. Quantum walks utilized for quantum search proved to achieve significantly lower hitting times than their classical counterpart, classical random walks. The evolution space for the quantum walks as well as the classical random walks is up until now a free space. In our approach, we introduce external electrical potentials to the evolution space. We study the evolution of discrete time quantum and classical random walks in such potential spaces and the probability — hitting time on finding marked sites. We considered the differences in applied potential among neighboring sites as weights for the lattice — graph. We introduce these weights to the evolution space as an operator for the discrete time quantum walk and as coin probabilities for the classical random walk. Our results show that quantum walks again, evolve faster in the evolution space with the applied potential. Quantum walks also achieve better probability — hitting time on finding the marked site in the potential space. With the introduction of electrical potentials, quantum walks evolving in potential spaces, can lead to the development of novel quantum algorithms, where input parameters can be introduced as external potentials.

Georgios D. Varsamis, Ioannis G. Karafyllidis, Georgios Ch. Sirakoulis