The sensitivity of a quantum PageRank
- PDF / 5,021,013 Bytes
- 36 Pages / 439.37 x 666.142 pts Page_size
- 10 Downloads / 162 Views
The sensitivity of a quantum PageRank Hirotada Honda1 Received: 3 August 2019 / Revised: 2 February 2020 © The JJIAM Publishing Committee and Springer Japan KK, part of Springer Nature 2020
Abstract In this study, we discuss the sensitivity of a quantum PageRank. By utilizing the finite-dimensional perturbation theory, we estimate the change of the quantum PageRank under a small analytical perturbation on the Google matrix. In addition, we will show the way to estimate the lower bound of the convergence radius and the error bound of the finite sum in the expansion of the perturbed PageRank. Keywords Quantum walk · PageRank · Perturbation theory Mathematics Subject Classification 81Q15 · 30E15 · 46B28
1 Introduction Quantum information has recently attracted numerous research attention. Particularly, quantum walks have been substantially discussed from both the theoretical and practical perspectives [1]. A major breakthrough has been the quadratic speedup in the search algorithms of quantum walks [2]. The study [3] extended the random walk concept on a graph to quantum walks on a directed graph. Based on the ideas presented in [4] and [5], the author introduced a unitary operator that works on a Hilbert space whose elements comprise pairs of edges and the components of the state transition matrix. Recently, studies on the mixing time of the quantum walk on the graph have also been conducted [6]. In parallel with these studies, the ranking process has been substantially discussed in classic network studies. A well-known ranking process is Google’s PageRank algorithm, which properly sorts web pages according to their importance and impact [7, 8]. A quantum walk study on PageRank was pioneered in [9, 10], who proposed a quantum version of the PageRank algorithm. Based on Szegedy’s ideas [3], the authors quantized the behavior of a random walker modeled in the Google matrix * Hirotada Honda [email protected] 1
Faculty of Information Networking for Innovation and Design, Toyo University, 1‑7‑11 Akabanedai, Kita‑ku, Tokyo 115‑0053, Japan
13
Vol.:(0123456789)
H. Honda
and defined the unitary operator. Additionally, they derived some interesting relationships between the quantum and original versions of PageRank. For instance, in the quantum PageRank, the eigenvalues and eigenvectors of the unitary operator can be represented by those of a matrix composed of the Google matrix elements. Besides, they also numerically computed some characteristics of the quantum PageRank as well as revealed its similarities to and differences from the classical PageRank. We previously studied the behavior of the classical PageRank subjected to small perturbations. Since the Perron–Frobenius theorem ensures good characteristics of the principal eigenvalue of the Google matrix, the PageRank could be analytically perturbed by perturbing the Google matrix. However, the perturbations of the quantum PageRank are less tractable since all the eigenvalues of the unitary operator have unity magnitude. Therefore, under a perturbatio
Data Loading...
