Discrete-Time Open Quantum Walks for Vertex Ranking in Graphs

Abstract

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 $\alpha$. We observe that this quantum PageRank procedure is faster than many other proposals reported in the literature.

This is the accepted preprint of the article published in Physical Review E (https://journals.aps.org/pre/abstract/10.1103/PhysRevE.111.034312)

References in corpus (20)

• Cooperative Game Theory Approaches for Network Partitioning
• Quantum algorithm for solving linear systems of equations
• Bloch vectors for qudits
• The effects of mixedness and entanglement on the properties of the entropic uncertainty in Heisenberg model with Dzyaloshinski-Moriya interaction
• Log-Networks
• Open Quantum Random Walks
• Google in a Quantum Network
• Quantum Navigation and Ranking in Complex Networks
• Adiabatic quantum algorithm for search engine ranking
• Quantum Google in a Complex Network
• Centrality measure based on continuous-time quantum walks and experimental realization
• Quantum NETwork: from theory to practice
• Complex Quantum Networks: a Topical Review
• Open Quantum Walks: a short introduction
• Experimental parity-time symmetry quantum walks on a directed graph
• Qudit States in Noisy Quantum Channels
• Generalized Quantum PageRank Algorithm with Arbitrary Phase Rotations
• Weyl channels for multipartite systems
• Resolving degeneracies in Google search via quantum stochastic walks
• Non-Markovianity in Discrete-Time Open Quantum Random Walk on Arbitrary Graphs

Cited by in corpus (3)

• Dynamics and computation in linear open quantum walks
• Dissipative realization of a quantum distance-based classifier using open quantum walks
• Quantum state transfer and periodicity in discrete-time quantum walks under non--Markovian dephasing noise