Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2404.14770 · Physical review. E

Discrete-time open quantum walks for vertex ranking in graphs

Supriyo Dutta

Published Mar 26, 2025• 6 citations
arXivHTMLPDF

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

DOI
10.1103/physreve.111.034312

Related papers

Experimental realization of continuous-time quantum walks on directed graphs and their application in PageRank

Kunkun Wang, Yuhao Shi, Lei Xiao +3 more

PageRank is an algorithm used by Google Search to rank web pages in their search engine results. An important step for quantum networks is to quantize the classical protocol as quantum mechanics provides computational resources that can be used to outperform classical algorithms. In this paper, we experimentally realize continuous-time quantum walks for directed graphs with non-Hermitian adjacency matrices by using linear optical circuits and single photons. We find that the node classical centrality in a directed graph is correlated with the maximum node probability resulting from a continuous-time quantum walk and then demonstrate PageRank. Our work opens up an avenue of applications of quantum information in real-life tasks.

Optica•Sep 21, 2020•50 citations

Resolving degeneracies in Google search via quantum stochastic walks

Colin Benjamin, Naini Dudhe

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) with the hope of bettering the classical PageRank (CPR) algorithm, which is 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:2207.11429•Journal of Statistical Mechanics Theory and Experiment•Jan 1, 2024•5 citations

Discrete quantum-classical walks for link prediction

A. Marin, M. Soto-Gomez, Giorgio Valentini +3 more

Link prediction is a fundamental task in network science that involves estimating the likelihood of missing or future connections between nodes based on the structural patterns of a graph. While Graph Neural Networks (GNNs) have become a dominant approach, Random Walk (RW)-based methods remain highly relevant due to their lower computational demands in large-scale networks. Although recent hybrid quantum-classical walks have shown promise in exploring graph structures, existing continuous-time models are computationally expensive as they require solving high-dimensional systems of differential equations. In this paper, we propose a discrete version of a recent hybrid quantum-classical random walk algorithm that significantly improves computational efficiency by utilizing state vector representations instead of density matrices. Our method, inspired by the Quantum Jumps approach, alternates between coherent evolution and measurement-driven state collapse to generate trajectories for node embeddings. We integrate this algorithm into a link prediction pipeline and evaluate its performance across various synthetic topologies, including Grid, Power-Law, Erdös-Rényi, Barabási-Albert, and Community graphs. The experimental results demonstrate that the proposed discrete hybrid walks consistently outperform classical random walk approaches in Community and Grid topologies, showing that quantum-inspired dynamics can capture complex structural information more effectively than classical dynamics for specific topologies.

IEEE Conference on Artificial Intelligence (CAI)•May 8, 2026•0 citations

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, 2016•2 citations

Generalized quantum PageRank algorithm with arbitrary phase rotations

Sergio A. Ortega, Miguel Angel Martin-Delgado

The quantization of the PageRank algorithm is a promising tool for a future quantum internet. Here we present a modification of the quantum PageRank, introducing arbitrary phase rotations (APR) in the underlying Szegedy's quantum walk. We define three different APR schemes with only one phase as a degree of freedom. We have analyzed the behavior of these algorithms in a small generic graph, observing that a decrease of the phase reduces the standard deviation of the instantaneous PageRank, so the nodes of the network can be distinguished better. However, the algorithm takes more time to converge, so the phase cannot be decreased arbitrarily. With these results we choose a concrete value for the phase to later apply the algorithm to complex scale-free graphs. In these networks, the original quantum PageRank is able to break the degeneracy of the residual nodes and detect secondary hubs that the classical algorithm suppresses. Nevertheless, not all of the detected secondary hubs are real according to the PageRank's definition. Some APR schemes can overcome this problem, restoring the degeneration of the residual nodes and highlighting the truly secondary hubs of the networks. Finally, we have studied the stability of the new algorithms. The original quantum algorithm was known to be more stable than the classical. We have found that one of our algorithms, whose PageRank distribution resembles the classical one, has a stability similar to the original quantum algorithm.

arXiv:2209.13451•Physical Review Research•Jan 31, 2023•10 citations

Variational Quantum PageRank

Sims, Christopher

The PageRank algorithm is used to rank web pages by their importance. Since its development, the PageRank algorithm is a critical and fundamental part of search engines today. PageRank is a graph-based algorithm that ranks pages based on how many other pages link to them. This work develops a variational quantum version of the PageRank algorithm and compares the performance of the two algorithms. It is found that quantum PageRank performs better at ranking websites than the normal PageRank algorithm

arXiv:2304.12232•Apr 19, 2023•0 citations
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.
PageRank is an algorithm used by Google Search to rank web pages in their search engine results. An important step for quantum networks is to quantize the classical protocol as quantum mechanics provides computational resources that can be used to outperform classical algorithms. In this paper, we experimentally realize continuous-time quantum walks for directed graphs with non-Hermitian adjacency matrices by using linear optical circuits and single photons. We find that the node classical centrality in a directed graph is correlated with the maximum node probability resulting from a continuous-time quantum walk and then demonstrate PageRank. Our work opens up an avenue of applications of quantum information in real-life tasks.
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) with the hope of bettering the classical PageRank (CPR) algorithm, which is 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.
Link prediction is a fundamental task in network science that involves estimating the likelihood of missing or future connections between nodes based on the structural patterns of a graph. While Graph Neural Networks (GNNs) have become a dominant approach, Random Walk (RW)-based methods remain highly relevant due to their lower computational demands in large-scale networks. Although recent hybrid quantum-classical walks have shown promise in exploring graph structures, existing continuous-time models are computationally expensive as they require solving high-dimensional systems of differential equations. In this paper, we propose a discrete version of a recent hybrid quantum-classical random walk algorithm that significantly improves computational efficiency by utilizing state vector representations instead of density matrices. Our method, inspired by the Quantum Jumps approach, alternates between coherent evolution and measurement-driven state collapse to generate trajectories for node embeddings. We integrate this algorithm into a link prediction pipeline and evaluate its performance across various synthetic topologies, including Grid, Power-Law, Erdös-Rényi, Barabási-Albert, and Community graphs. The experimental results demonstrate that the proposed discrete hybrid walks consistently outperform classical random walk approaches in Community and Grid topologies, showing that quantum-inspired dynamics can capture complex structural information more effectively than classical dynamics for specific topologies.
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.
The quantization of the PageRank algorithm is a promising tool for a future quantum internet. Here we present a modification of the quantum PageRank, introducing arbitrary phase rotations (APR) in the underlying Szegedy's quantum walk. We define three different APR schemes with only one phase as a degree of freedom. We have analyzed the behavior of these algorithms in a small generic graph, observing that a decrease of the phase reduces the standard deviation of the instantaneous PageRank, so the nodes of the network can be distinguished better. However, the algorithm takes more time to converge, so the phase cannot be decreased arbitrarily. With these results we choose a concrete value for the phase to later apply the algorithm to complex scale-free graphs. In these networks, the original quantum PageRank is able to break the degeneracy of the residual nodes and detect secondary hubs that the classical algorithm suppresses. Nevertheless, not all of the detected secondary hubs are real according to the PageRank's definition. Some APR schemes can overcome this problem, restoring the degeneration of the residual nodes and highlighting the truly secondary hubs of the networks. Finally, we have studied the stability of the new algorithms. The original quantum algorithm was known to be more stable than the classical. We have found that one of our algorithms, whose PageRank distribution resembles the classical one, has a stability similar to the original quantum algorithm.
The PageRank algorithm is used to rank web pages by their importance. Since its development, the PageRank algorithm is a critical and fundamental part of search engines today. PageRank is a graph-based algorithm that ranks pages based on how many other pages link to them. This work develops a variational quantum version of the PageRank algorithm and compares the performance of the two algorithms. It is found that quantum PageRank performs better at ranking websites than the normal PageRank algorithm