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:2209.13451 · Physical Review Research

Generalized quantum PageRank algorithm with arbitrary phase rotations

Sergio A. Ortega, Miguel Angel Martin-Delgado

Published Jan 31, 2023• 12 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevresearch.5.013061

Related papers

Quantum versatility in PageRank

Weiwei Zhang, Zhimin Wu, Heng-Yue Jia +4 more

Quantum mechanics empowers the emergence of quantum advantages in various fields, including quantum algorithms. Quantum PageRank is a promising tool for a future quantum internet. Recently, arbitrary phase rotations (APRs) have been introduced in the underlying Szegedy's quantum walk of the quantum PageRank algorithm. In this work we thoroughly study the role APR plays in quantum PageRank. We discover the versatility resulting from quantumness. Specifically, we discover the emergence of a cluster phenomenon in rankings considering the rotation phases, i.e., the existence of similar clusters in the distribution of the rankings and their fidelity with the corresponding classical PageRanks, the ranking distribution variance, the coherence and entanglement of PageRank states, and the power-law parameter in the ranking distributions on a scale-free network concerning the two rotation phases. Furthermore, we propose an alternate quantum PageRank with APR which provides an extra tunnel for the analysis of PageRank. We also study the PageRank on the trackback graph of a scale-free graph for the investigation of network information traffic tracking. We demonstrate the rich cluster diversity formed in our alternate quantum PageRank, which offers a novel perspective on the quantum versatility of PageRank. Our results present the quantum-enabled perspective for PageRanking and shed light on the design and application of practical quantum PageRank algorithms. Published by the American Physical Society 2024

arXiv:2411.13114•Physical Review Research•Nov 19, 2024•4 citations

Complex-phase extensions of the Szegedy quantum walk on graphs

Sergio A. Ortega, Miguel Angel Martin-Delgado

This work introduces a graph-phased Szegedy's quantum walk, which incorporates link phases and local arbitrary phase rotations (APR), unlocking new possibilities for quantum algorithm efficiency. We demonstrate how to adapt quantum circuits to these advancements, allowing phase patterns that ensure computational practicality. The graph-phased model broadens the known equivalence between coined quantum walks and Szegedy's model, accommodating a wider array of coin operators. Through illustrative examples, we reveal intriguing disparities between classical and quantum interpretations of walk dynamics. Remarkably, local APR phases emerge as powerful tools for marking graph nodes, optimizing quantum searches without altering graph structure. We further explore the surprising nuances between single and double operator approaches, highlighting a greater range of compatible coins with the latter. To facilitate these advancements, we present an improved classical simulation algorithm, which operates with superior efficiency. This study not only refines quantum walk methodologies but also paves the way for future explorations, including potential applications in quantum search and PageRank algorithms. Our findings illuminate the path towards more versatile and powerful quantum computing paradigms.

arXiv:2410.22011•Physical Review A•Mar 19, 2025•4 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•3 citations

Quantum Google in a Complex Network

Giuseppe Davide Paparo, Markus Müller, Francesc Comellas +1 more

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.

arXiv:1303.3891•Scientific Reports•Oct 4, 2013•93 citations

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

Quantum walk based algorithm on scale free networks

German Alamilla Peralta

The classification of information contained in complex networks such as the WWW is a central problem in network science for its technological impact. A highly successful methodology for this purpose is Google’s PageRank algorithm. It allows to measure the importance or relevance of a web page depending on the relationship between pages and its connections, i.e, the hyperlink structure. Finding ways to apply the advantages of quantum computers to real world computational tasks is an active research area. In this thesis, we implement a quantum gate-based algorithm that replicates the behaviour of the Quantum PageRank algorithm. We present a comprehensive analysis with the Szegedy quantum walk formalism. The implementation procedure is based in the quantum circuit model of quantum computing. Here, we review a Quantum PageRank algorithm and illustrate the main findings. We show the behaviour of the quantum PageRank algorithm using the IBM’s Q experience framework for quantum computing. We investigate the behavior of the Quantum PageRank algorithm using quantum walks by giving explicit connections with corresponding classical algorithm. We make a comparative analysis of our findings and discuss the capabilities of a quantum computing platform applied to the Quantum PageRank algorithm. Within the restrictions imposed by hardware, we implement a multiple-controlled gate using ancilla qubits and all other elements required for implementing our quantum algorithm.

•Mar 14, 2020•0 citations
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.
Quantum mechanics empowers the emergence of quantum advantages in various fields, including quantum algorithms. Quantum PageRank is a promising tool for a future quantum internet. Recently, arbitrary phase rotations (APRs) have been introduced in the underlying Szegedy's quantum walk of the quantum PageRank algorithm. In this work we thoroughly study the role APR plays in quantum PageRank. We discover the versatility resulting from quantumness. Specifically, we discover the emergence of a cluster phenomenon in rankings considering the rotation phases, i.e., the existence of similar clusters in the distribution of the rankings and their fidelity with the corresponding classical PageRanks, the ranking distribution variance, the coherence and entanglement of PageRank states, and the power-law parameter in the ranking distributions on a scale-free network concerning the two rotation phases. Furthermore, we propose an alternate quantum PageRank with APR which provides an extra tunnel for the analysis of PageRank. We also study the PageRank on the trackback graph of a scale-free graph for the investigation of network information traffic tracking. We demonstrate the rich cluster diversity formed in our alternate quantum PageRank, which offers a novel perspective on the quantum versatility of PageRank. Our results present the quantum-enabled perspective for PageRanking and shed light on the design and application of practical quantum PageRank algorithms. Published by the American Physical Society 2024
This work introduces a graph-phased Szegedy's quantum walk, which incorporates link phases and local arbitrary phase rotations (APR), unlocking new possibilities for quantum algorithm efficiency. We demonstrate how to adapt quantum circuits to these advancements, allowing phase patterns that ensure computational practicality. The graph-phased model broadens the known equivalence between coined quantum walks and Szegedy's model, accommodating a wider array of coin operators. Through illustrative examples, we reveal intriguing disparities between classical and quantum interpretations of walk dynamics. Remarkably, local APR phases emerge as powerful tools for marking graph nodes, optimizing quantum searches without altering graph structure. We further explore the surprising nuances between single and double operator approaches, highlighting a greater range of compatible coins with the latter. To facilitate these advancements, we present an improved classical simulation algorithm, which operates with superior efficiency. This study not only refines quantum walk methodologies but also paves the way for future explorations, including potential applications in quantum search and PageRank algorithms. Our findings illuminate the path towards more versatile and powerful quantum computing paradigms.
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
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 classification of information contained in complex networks such as the WWW is a central problem in network science for its technological impact. A highly successful methodology for this purpose is Google’s PageRank algorithm. It allows to measure the importance or relevance of a web page depending on the relationship between pages and its connections, i.e, the hyperlink structure. Finding ways to apply the advantages of quantum computers to real world computational tasks is an active research area. In this thesis, we implement a quantum gate-based algorithm that replicates the behaviour of the Quantum PageRank algorithm. We present a comprehensive analysis with the Szegedy quantum walk formalism. The implementation procedure is based in the quantum circuit model of quantum computing. Here, we review a Quantum PageRank algorithm and illustrate the main findings. We show the behaviour of the quantum PageRank algorithm using the IBM’s Q experience framework for quantum computing. We investigate the behavior of the Quantum PageRank algorithm using quantum walks by giving explicit connections with corresponding classical algorithm. We make a comparative analysis of our findings and discuss the capabilities of a quantum computing platform applied to the Quantum PageRank algorithm. Within the restrictions imposed by hardware, we implement a multiple-controlled gate using ancilla qubits and all other elements required for implementing our quantum algorithm.