On the equivalence between quantum and random walks on finite graphs

被引:0
作者
Matheus G. Andrade
Franklin de Lima Marquezino
Daniel R. Figueiredo
机构
[1] Federal University of Rio de Janeiro (UFRJ),Department of Computer and System Engineering (PESC)
来源
Quantum Information Processing | 2020年 / 19卷
关键词
Quantum walks; Random walks; Markov chains;
D O I
暂无
中图分类号
学科分类号
摘要
Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given vertex of the graph and the probability that the random walk is at that same vertex , for all vertices and time steps. The result is given by the construction procedure of a matrix sequence for the random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. Interestingly, these matrices allow for a different simulation approach for quantum walks where vertex samples respect neighbor locality, and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial) sampling of quantum graph trajectories (paths). Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.
引用
收藏
相关论文
共 50 条
[41]   Clustering quantum Markov chains on trees associated with open quantum random walks [J].
Accardi, Luigi ;
Andolsi, Amenallah ;
Mukhamedov, Farrukh ;
Rhaima, Mohamed ;
Souissi, Abdessatar .
AIMS MATHEMATICS, 2023, 8 (10) :23003-23015
[42]   Szegedy quantum walks with memory on regular graphs [J].
Li, Dan ;
Liu, Ying ;
Yang, Yu-Guang ;
Xu, Juan ;
Yuan, Jia-Bin .
QUANTUM INFORMATION PROCESSING, 2020, 19 (01)
[43]   Random walks on graphs with interval weights and precise marginals [J].
Skulj, Damjan .
INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, 2016, 73 :76-86
[44]   Hitting times of quantum and classical random walks in potential spaces [J].
Varsamis, Georgios D. ;
Karafyllidis, Ioannis G. ;
Sirakoulis, Georgios Ch. .
PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2022, 606
[45]   REPRESENTATIONS OF CUNTZ ALGEBRAS ASSOCIATED TO RANDOM WALKS ON GRAPHS [J].
Christoffersen, Nicholas J. ;
Dutkay, Dorin Ervin .
JOURNAL OF OPERATOR THEORY, 2022, 88 (01) :141-172
[46]   Random Walks on Graphs for Salient Object Detection in Images [J].
Gopalakrishnan, Viswanath ;
Hu, Yiqun ;
Rajan, Deepu .
IEEE TRANSACTIONS ON IMAGE PROCESSING, 2010, 19 (12) :3232-3242
[47]   Discrete Green's functions and random walks on graphs [J].
Xu, Hao ;
Yau, Shing-Tung .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2013, 120 (02) :483-499
[48]   CRITICAL DENSITY OF ACTIVATED RANDOM WALKS ON TRANSITIVE GRAPHS [J].
Stauffer, Alexandre ;
Taggi, Lorenzo .
ANNALS OF PROBABILITY, 2018, 46 (04) :2190-2220
[49]   Random walks on a finite graph with congestion points [J].
Kang, MH .
APPLIED MATHEMATICS AND COMPUTATION, 2004, 153 (02) :601-610
[50]   OPEN QUANTUM RANDOM WALKS AND THE MEAN HITTING TIME FORMULA [J].
Lardizabal, Carlos F. .
QUANTUM INFORMATION & COMPUTATION, 2017, 17 (1-2) :79-105