Resolving degeneracies in Google search via quantum stochastic walks
arXiv:2207.11429 · doi:10.1088/1742-5468/ad1384
Abstract
The Internet is one of the most valuable technologies invented to date. Among them, Google is the most widely used search engine. The PageRank algorithm is the backbone of Google search, ranking web pages according to relevance and recency. We employ quantum stochastic walks (QSWs) to improve the classical PageRank (CPR) algorithm based on classical continuous time random walks. We implement QSW via two schemes: only incoherence and dephasing with incoherence. PageRank using QSW with only incoherence or QSW with dephasing and incoherence best resolves degeneracies that are unresolvable via CPR and with a convergence time comparable to that for CPR, which is generally the minimum. For some networks, the two QSW schemes obtain a convergence time lower than CPR and an almost degeneracy-free ranking compared to CPR.
arXiv comment23 pages, 23 figures
References in corpus (14)
- Statistical mechanics of complex networks
- The Quantum Internet
- Cooperative Game Theory Approaches for Network Partitioning
- Classes of behavior of small-world networks
- Spatial Networks
- Quantum Computation and Decision Trees
- Decoherence in quantum walks - a review
- Quantum stochastic walks: A generalization of classical random walks and quantum walks
- Quantum Navigation and Ranking in Complex Networks
- Quantum walks on graphs representing the firing patterns of a quantum neural network
- A simple, distance-dependent formulation of the Watts-Strogatz model for directed and undirected small-world networks
- QSWalk: a Mathematica package for quantum stochastic walks on arbitrary graphs
- Testing quantum speedups in exciton transport through a photosynthetic complex using quantum stochastic walks
- Modeling Transitivity in Complex Networks