Features of Quantum Random Walks on Multiplex Networks and Other Topologies

Abstract

Quantum random walks are the quantum analogs of classical random walks and appear to be promising tools to design fast quantum algorithms. Therefore it is important to study their time-related features and see how these differ compared to the classical case. For the discrete-time quantum walk on the line it has been shown that the probability to be absorbed by an absorbing boundary equals 2/π in contrast to the classical case where this probability equals 1, hence a quantum walk may continue forever without getting absorbed. It is also shown that mixing times of discrete-time quantum walks on the hypercube scale with n, the dimension of the hypercube, which is faster than O(n log(n)) for the classical random walk. So the quantum walk might offer a slight speed-up compared to the classical case. Finally, it is shown that the mixing times of the continuous-time quantum walk on a 2-layer multiplex graph depend on the eigenvalue gaps of the corresponding Laplacian matrix L. When the strength of the connections between the layers of a multiplex graph becomes very large, the eigenvalues of the Laplacian matrix converge. Thus the mixing times of the continuous-time quantum walk on 2-layer multiplex graphs converge.