arXiv:1907.01641

Sensitivity of quantum PageRank

Hirotada Honda

Published Jun 27, 2019• 0 citations

Abstract

In this paper, we discuss the sensitivity of quantum PageRank. By using 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 as well as the error bound of the finite sum in the expansion of the perturbed PageRank.

DOI: 10.48550/arxiv.1907.01641

Related papers

Google Search by Quantum Computation Method

Bhawani Shankar Leelar, E. S. Shivaleela, T. Srinivas

The PageRank of a web page denotes popularity of a web page, higher the PageRank wider the popularity. The explosion of the number of web pages propel us to fasten the search time. The quantum version of Google PageRank has recently been investigated by various groups [1], [2] and shown to be quadratically faster in time than the classical PageRank algorithm. In this paper, we follow Quantum PageRank Class defined in [2]. We have modelled the web pages as quantum states and the search as a quantum stochastic walk. The evolution of the density matrix is computed using the Kossakowski-Lindblad master equation, which has reversible and irreversible evolution terms. The reversible term gives the coherent evolution, while the irreversible term adds noise to the system. The stochastic convergence of the diagonal elements of the density matrix gives the Quantum PageRank values, and to observe this it is essential to get consistent PageRank ordering, after the quantum fluctuations have been stabilized (insignificant). In our paper, we propose a method for faster convergence of the Quantum PageRanks by adding limited quantity of noise values during computation of the Kossakowski-Lindblad master equation, and the results obtained are an improvement over [2], where the quantum fluctuations do not stabilize and the ordering of PageRanks is not consistent. Addition of noise in limited amount during computation helps in limiting quantum fluctuations and in convergence of the Quantum PageRanks.

International Conference on Advanced Computing and Communications (ADCOM)Sep 1, 20162 citations

Quantum algorithm for PageRank computation through multistep quantum resonant transitions

Chuqing Wang, Hefeng Wang, Hua Xiang

We present a quantum algorithm for obtaining a quantum state that encodes the PageRank vector of the Google matrix through multistep quantum resonant transition (mQRT). In the algorithm, the PageRank vector is encoded in the ground state of a problem Hamiltonian associated with the Google matrix. By dividing the web graph corresponding to the Google matrix into a series of subgraphs with nested structure, we construct a sequence of Hamiltonians based on the subgraphs to form a Hamiltonian evolution path from a simple initial Hamiltonian to the problem Hamiltonian. The ground state of the problem Hamiltonian is obtained by going through ground states of the intermediate Hamiltonians via QRT step by step. This algorithm requires only one ancillary qubit, and the runtime of the algorithm is proportional to the number of steps. It provides a new way for efficiently obtaining the quantum state of the PageRank vector of large-scale networks.

quant-pharXiv:2609.08140Journal of Computational and Applied MathematicsSep 9, 20261 citation

Perturbation bounds for quantum Markov processes and their fixed points

Oleg Szehr, Michael M. Wolf

We investigate the stability of quantum Markov processes with respect to perturbations of their transition maps. In the first part, we introduce a condition number that measures the sensitivity of fixed points of a quantum channel to perturbations. We establish upper and lower bounds on this condition number in terms of subdominant eigenvalues of the transition map. In the second part, we consider quantum Markov processes that converge to a unique stationary state and we analyze the stability of the evolution at finite times. In this way we obtain a linear relation between the mixing time of a quantum Markov process and the sensitivity of its fixed point with respect to perturbations of the transition map.

arXiv:1210.1171Journal of Mathematical PhysicsMar 1, 201329 citations

Discrete-time open quantum walks for vertex ranking in graphs

Supriyo Dutta

This article presents a new quantum PageRank algorithm on graphs using discrete-time open quantum walks. Google's PageRank is a widely used algorithm for ranking the web pages on the world wide web in classical computation. From a broader perspective, it is also a fundamental measure for quantifying the importance of vertices in a network. Similarly, the new quantum PageRank also serves to quantify the significance of a network's vertices. In this work, we extend the concept of discrete-time open quantum walk on arbitrary directed and undirected graphs by utilizing the Weyl operators as Kraus operators. This new model of quantum walk is useful for building up the quantum PageRank algorithm, discussed in this article. We compare the classical PageRank and the newly defined quantum PageRank for different types of complex networks, such as the scale-free network, Erdős-Rényi random network, Watts-Strogatz network, spatial network, Zachary Karate club network, GNC, GN, GNR networks, Barabási and Albert network, etc. In addition, we study the convergence of the quantum PageRank process and its dependency on the damping factor α. We observe that this quantum PageRank procedure is faster than many other proposals reported in the literature.

arXiv:2404.14770Physical review. EMar 26, 20256 citations

A Simple Bound on the Error of Perturbation Theory in Quantum Mechanics

Daniel Harlow

I provide a straightforward proof that a simple harmonic oscillator perturbed by an (almost) arbitrary positive interaction has a perturbative expansion for any finite-time Euclidian transition amplitude which obeys the following result: the difference of the sum of the first N terms of the series and the exact result is bounded in absolute value by the next term in the series. The proof makes no assumptions about either the strength of the interactions or the convergence of the perturbation series. I then argue that the result generalizes immediately to a much broader class of quantum mechanical systems, including bare perturbation theory in quantum field theory. The case of renormalized perturbation theory is more subtle and remains open, as does the generalization to energy levels and connected S-matrix elements.

arXiv:0905.2466May 15, 20091 citation

Google In A Photonic Lattice

Kallol Roy, Ji Liu, Le Luo +4 more

The quantum version of Google PageRank has recently been investigated by various groups and shown to be quadratically faster in time than the classical PageRank algorithm. In this paper we propose the implementation of Quantum PageRank by a stochastic quantum walk of correlated photons in a photonic waveguide lattice, where we allow the density matrix to evolve according to the Lindblad-Kossakowski master equation. This yields a stationary state, the diagonal of whose density matrix gives the page ranking.

arXiv:1305.1766May 8, 20132 citations