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:1303.3891 · Scientific Reports

Quantum Google in a Complex Network

Giuseppe Davide Paparo, Markus Müller, Francesc Comellas, Miguel Angel Martin-Delgado

Published Oct 4, 2013• 93 citations
arXivHTMLPDF

Abstract

We investigate the behaviour of the recently proposed Quantum PageRank algorithm, in large complex networks. We find that the algorithm is able to univocally reveal the underlying topology of the network and to identify and order the most relevant nodes. Furthermore, it is capable to clearly highlight the structure of secondary hubs and to resolve the degeneracy in importance of the low lying part of the list of rankings. The quantum algorithm displays an increased stability with respect to a variation of the damping parameter, present in the Google algorithm, and a more clearly pronounced power-law behaviour in the distribution of importance, as compared to the classical algorithm. We test the performance and confirm the listed features by applying it to real world examples from the WWW. Finally, we raise and partially address whether the increased sensitivity of the quantum algorithm persists under coordinated attacks in scale-free and random networks.

DOI
10.1038/srep02773

Related papers

Construction and Application to Complex Networks

Francesc Comellas

We review the main ndings on the ranking capabilities of the recently proposed Quantum PageRank algorithm (1,2) applied to large complex networks. The algorithm has been shown to identify unambiguously the underlying topology of the network and to be capable of clearly highlighting the struc- ture of secondary hubs of networks. Furthermore it can resolve the degeneracy in importance of the low lying part of the list of rankings. Examples of applications include real world instances from the WWW, which typically display a scale-free network structure and models of hierarchical networks. The quantum algorithm has been shown to display an increased stability with respect to a variation of the damping parameter, present in the Google algorithm, and a more clearly pronounced power-law behaviour in the distribution of importance among the nodes, as compared to the classical algorithm.

•Jan 1, 2014•0 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

Randomized SearchRank: A semiclassical approach to a quantum search engine

Sergio A. Ortega, Miguel Angel Martin-Delgado

The quantum SearchRank algorithm is a promising tool for a future quantum search engine based on PageRank quantization. However, this algorithm loses its functionality when the N / M ratio between the network size N and the number of marked nodes M is sufficiently large. We propose a modification of the algorithm, replacing the underlying Szegedy quantum walk with a semiclassical walk. To maintain the same time complexity as the quantum SearchRank algorithm we propose a simplification of the algorithm. This new algorithm is called randomized SearchRank, since it corresponds to a quantum walk over a randomized mixed state. The performance of the SearchRank algorithms is first analyzed on an example network and then statistically on a set of different networks of increasing size and different number of marked nodes. On the one hand, to test the search ability of the algorithms, it is computed how the probability of measuring the marked nodes decreases with N / M for the quantum SearchRank, but remarkably it remains at a high value around 0.9 for our semiclassical algorithms, solving the quantum SearchRank problem. The time complexity of the algorithms is also analyzed, obtaining a quadratic speedup with respect to the classical ones. On the other hand, the ranking functionality of the algorithms has been investigated, obtaining a good agreement with the classical PageRank distribution. Finally, the dependence of these algorithms on the intrinsic PageRank damping parameter has been clarified. Our results suggest that this parameter should be below a threshold so that the execution time does not increase drastically. Published by the American Physical Society 2024

arXiv:2401.01554•Physical Review Research•Oct 4, 2024•2 citations

Quantum Navigation and Ranking in Complex Networks

Eduardo Sánchez-Burillo, Jordi Duch, Jesús Gómez‐Gardeñes +1 more

Complex networks are formal frameworks capturing the interdependencies between the elements of large systems and databases. This formalism allows to use network navigation methods to rank the importance that each constituent has on the global organization of the system. A key example is Pagerank navigation which is at the core of the most used search engine of the World Wide Web. Inspired in this classical algorithm, we define a quantum navigation method providing a unique ranking of the elements of a network. We analyze the convergence of quantum navigation to the stationary rank of networks and show that quantumness decreases the number of navigation steps before convergence. In addition, we show that quantum navigation allows to solve degeneracies found in classical ranks. By implementing the quantum algorithm in real networks, we confirm these improvements and show that quantum coherence unveils new hierarchical features about the global organization of complex systems.

arXiv:1202.3471•Scientific Reports•Aug 28, 2012•115 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.14770•Physical review. E•Mar 26, 2025•6 citations

Google in a Quantum Network

G. D. Paparo, M. A. Martin-Delgado

We introduce the characterization of a class of quantum PageRank algorithms in a scenario in which some kind of quantum network is realizable out of the current classical internet web, but no quantum computer is yet available. This class represents a quantization of the PageRank protocol currently employed to list web pages according to their importance. We have found an instance of this class of quantum protocols that outperforms its classical counterpart and may break the classical hierarchy of web pages depending on the topology of the web.

arXiv:1112.2079•Scientific Reports•Jun 8, 2012•136 citations
We investigate the behaviour of the recently proposed Quantum PageRank algorithm, in large complex networks. We find that the algorithm is able to univocally reveal the underlying topology of the network and to identify and order the most relevant nodes. Furthermore, it is capable to clearly highlight the structure of secondary hubs and to resolve the degeneracy in importance of the low lying part of the list of rankings. The quantum algorithm displays an increased stability with respect to a variation of the damping parameter, present in the Google algorithm, and a more clearly pronounced power-law behaviour in the distribution of importance, as compared to the classical algorithm. We test the performance and confirm the listed features by applying it to real world examples from the WWW. Finally, we raise and partially address whether the increased sensitivity of the quantum algorithm persists under coordinated attacks in scale-free and random networks.
We review the main ndings on the ranking capabilities of the recently proposed Quantum PageRank algorithm (1,2) applied to large complex networks. The algorithm has been shown to identify unambiguously the underlying topology of the network and to be capable of clearly highlighting the struc- ture of secondary hubs of networks. Furthermore it can resolve the degeneracy in importance of the low lying part of the list of rankings. Examples of applications include real world instances from the WWW, which typically display a scale-free network structure and models of hierarchical networks. The quantum algorithm has been shown to display an increased stability with respect to a variation of the damping parameter, present in the Google algorithm, and a more clearly pronounced power-law behaviour in the distribution of importance among the nodes, as compared to the classical algorithm.
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 quantum SearchRank algorithm is a promising tool for a future quantum search engine based on PageRank quantization. However, this algorithm loses its functionality when the N / M ratio between the network size N and the number of marked nodes M is sufficiently large. We propose a modification of the algorithm, replacing the underlying Szegedy quantum walk with a semiclassical walk. To maintain the same time complexity as the quantum SearchRank algorithm we propose a simplification of the algorithm. This new algorithm is called randomized SearchRank, since it corresponds to a quantum walk over a randomized mixed state. The performance of the SearchRank algorithms is first analyzed on an example network and then statistically on a set of different networks of increasing size and different number of marked nodes. On the one hand, to test the search ability of the algorithms, it is computed how the probability of measuring the marked nodes decreases with N / M for the quantum SearchRank, but remarkably it remains at a high value around 0.9 for our semiclassical algorithms, solving the quantum SearchRank problem. The time complexity of the algorithms is also analyzed, obtaining a quadratic speedup with respect to the classical ones. On the other hand, the ranking functionality of the algorithms has been investigated, obtaining a good agreement with the classical PageRank distribution. Finally, the dependence of these algorithms on the intrinsic PageRank damping parameter has been clarified. Our results suggest that this parameter should be below a threshold so that the execution time does not increase drastically. Published by the American Physical Society 2024
Complex networks are formal frameworks capturing the interdependencies between the elements of large systems and databases. This formalism allows to use network navigation methods to rank the importance that each constituent has on the global organization of the system. A key example is Pagerank navigation which is at the core of the most used search engine of the World Wide Web. Inspired in this classical algorithm, we define a quantum navigation method providing a unique ranking of the elements of a network. We analyze the convergence of quantum navigation to the stationary rank of networks and show that quantumness decreases the number of navigation steps before convergence. In addition, we show that quantum navigation allows to solve degeneracies found in classical ranks. By implementing the quantum algorithm in real networks, we confirm these improvements and show that quantum coherence unveils new hierarchical features about the global organization of complex systems.
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.
We introduce the characterization of a class of quantum PageRank algorithms in a scenario in which some kind of quantum network is realizable out of the current classical internet web, but no quantum computer is yet available. This class represents a quantization of the PageRank protocol currently employed to list web pages according to their importance. We have found an instance of this class of quantum protocols that outperforms its classical counterpart and may break the classical hierarchy of web pages depending on the topology of the web.