Characterizing the Relationship Between Unitary Quantum Walks and Non-Homogeneous Random Walks

• Matheus Guedes de Andrade UFRJ http://orcid.org/0000-0002-9968-0194
• Franklin de Lima Marquezino UFRJ https://orcid.org/0000-0001-9712-1930
• Daniel Ratton Figueiredo UFRJ https://orcid.org/0000-0001-9341-6619

DOI: https://doi.org/10.5753/ctd.2021.15756

Resumo

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.

Palavras-chave: Quantum walks, Random Walks, Markov Chains

Referências

Aharonov, D., Ambainis, A., Kempe, J., and Vazirani, U. (2001). Quantum walks on graphs. InACM STOC, pages 50–59.

Aharonov, Y., Davidovich, L., and Zagury, N. (1993). Quantum random walks.Phys.Rev. A, 48(2):1687.

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.

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.

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.

Childs, A. M. (2009).Universal computation by quantum walk.Phys. Rev. Lett.,102(18):180501.

Lubasch, M., Joo, J., Moinier, P., Kiffner, M., and Jaksch, D. (2020). Variational quantum algorithms for nonlinear problems.Phys. Rev. A, 101:010301.

Montero, M. (2017). Quantum and random walks as universal generators of probability distributions.Phys. Rev. A, 95(6):062326.

Portugal, R. (2013).Quantum walks and search algorithms. Springer.

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. InIEEE FOCS, pages 124–134.