Hitting times of quantum and classical random walks in potential spaces

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

Physica A: Statistical Mechanics and its Applications, 2022, vol. 606, issue C

Abstract: 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.

Keywords: Quantum walks; Random walks; Spatial search; Applied potentials; Hitting time (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437122006938
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:606:y:2022:i:c:s0378437122006938

DOI: 10.1016/j.physa.2022.128119

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().