Paper Information | SBC BOOKS

Fill in your paper information

Language (*)

Title (*)

Keywords (*)

Abstract (*)

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 two 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 node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.

Pages (*)

File Link

English Information

Title

Keywords

Abstract

(*) To change the order drag the item to the new position.

Authors

#	Name
1	Matheus Guedes de Andrade(guedesm@cos.ufrj.br)
2	Franklin de Lima Marquezino(franklin@cos.ufrj.br)
3	Daniel Ratton Figueiredo(daniel@cos.ufrj.br)

(*) To change the order drag the item to the new position.

Reference

#	Reference
1	Aharonov, D., Ambainis, A., Kempe, J., and Vazirani, U. (2001). Quantum walks on graphs. InACM STOC, pages 50–59.
2	Aharonov, Y., Davidovich, L., and Zagury, N. (1993). Quantum random walks.Phys.Rev. A, 48(2):1687.
3	Andrade, M. G. (2020). Characterizing the Inherent Relationship Between Unitary Quan-tum Walks and Non-Homogeneous Random Walks on Finite Graphs. Master’s thesis,Federal University of Rio de Janeiro. Available athttps://www.cos.ufrj.br/index.php/pt-BR/publicacoes-pesquisa/details/15/2953.
4	Andrade, M. G., Marquezino, F. L., and Figueiredo, D. R. (2021). Quantum walks can unitarily match random walks on finite graphs. arXiv pre-print 2103.06463.
5	Andrade, M. G., Marquezino, F. L., and Figueiredo, D. R. (2020). On the equivalence between quantum and random walks on finite graphs.Quantum Inf. Process., 19(11):1–20.
6	Childs, A. M. (2009).Universal computation by quantum walk.Phys. Rev. Lett.,102(18):180501.
7	Lubasch, M., Joo, J., Moinier, P., Kiffner, M., and Jaksch, D. (2020). Variational quantum algorithms for nonlinear problems.Phys. Rev. A, 101:010301.
8	Montero, M. (2017). Quantum and random walks as universal generators of probability distributions.Phys. Rev. A, 95(6):062326.
9	Portugal, R. (2013).Quantum walks and search algorithms. Springer.
10	Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. InIEEE FOCS, pages 124–134.

Paper Registration

Fill in your paper information

English Information

Authors

Reference