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:2104.09637 · Journal of Complex Networks

Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks

Paola Boito, Roberto Grena

Published Oct 7, 2021• 5 citations
arXivHTMLPDF

Abstract

Abstract In this article, we introduce, test and discuss three quantum methods for computing hub and authority centrality scores in directed networks. The methods are based on unitary, continuous-time quantum walks; the construction of a suitable Hermitian Hamiltonian is achieved by performing a quantum walk on the associated bipartite graph. Two methods, called CQAu and CQAw, use the same evolution operator, inspired by the classical Hyperlink-Induced Topic Search (HITS) algorithm, but with different initial states; the computation of hub and authority scores is performed simultaneously. The third method, called CQG and inspired by classical PageRank, requires instead two separate runs with different evolution operators, one for hub and one for authority scores. The methods are tested on several directed graphs with different sizes and properties; a comparison with other well-established ranking algorithms is provided. CQAw emerges as the most reliable of the three methods and yields rankings that are largely compatible with results from HITS, although CQAu and CQG also present interesting features and potential for applications.

DOI
10.1093/comnet/cnab038

Related papers

Quantum centrality testing on directed graphs via PT -symmetric quantum walks

Josh Izaac, Jingbo B. Wang, Paul C Abbott +1 more

Various quantum-walk-based algorithms have been proposed to analyze and rank the centrality of graph vertices. However, issues arise when working with directed graphs: the resulting non-Hermitian Hamiltonian leads to nonunitary dynamics, and the total probability of the quantum walker is no longer conserved. In this paper, we discuss a method for simulating directed graphs using $PT$-symmetric quantum walks, allowing probability-conserving nonunitary evolution. This method is equivalent to mapping the directed graph to an undirected, yet weighted, complete graph over the same vertex set, and can be extended to cover interdependent networks of directed graphs. Previous work has shown centrality measures based on the continuous-time quantum walk provide an eigenvectorlike quantum centrality; using the $PT$-symmetric framework, we extend these centrality algorithms to directed graphs with a significantly reduced Hilbert space compared to previous proposals. In certain cases, this centrality measure provides an advantage over classical algorithms used in network analysis, for example, by breaking vertex rank degeneracy. Finally, we perform a statistical analysis over ensembles of random graphs, and show strong agreement with the classical PageRank measure on directed acyclic graphs.

arXiv:1607.02673•Physical Review A•Sep 5, 2017•18 citations

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

Continuous-time quantum walk based centrality testing on weighted graphs

Yang Wang, Shichuan Xue, Junjie Wu +1 more

Centrality measure is an essential tool in network analysis and widely used in the domain of computer science, biology and sociology. Taking advantage of the speedup offered by quantum computation, various quantum centrality measures have been proposed. However, few work of quantum centrality involves weighted graphs, while the weight of edges should be considered in certain real-world networks. In this work, we extend the centrality measure based on continuous-time quantum walk to weighted graphs. We testify the feasibility and reliability of this quantum centrality using an ensemble of 41,675 graphs with various topologies and comparing with the eigenvector centrality measure. The average Vigna's correlation index of all the tested graphs with all edge weights in [1, 10] is as high as 0.967, indicating the pretty good consistency of rankings by the continuous-time quantum walk centrality and the eigenvector centrality. The intuitive consistency of the top-ranked vertices given by this quantum centrality measure and classical centrality measures is also demonstrated on large-scale weighted graphs. Moreover, the range of the continuous-time quantum walk centrality values is much bigger than that of classical centralities, which exhibits better distinguishing ability to pick the important vertices from the ones with less importance. All these results show that the centrality measure based on continuous-time quantum walk still works well on weighted graphs.

Scientific Reports•Apr 9, 2022•15 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

On the quantum simulation of complex networks

Duarte Magano, João P. Moutinho, Bruno Coelho Coutinho

Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.

arXiv:2212.06126•SciPost Physics Core•Aug 24, 2023•6 citations

Experimental Parity-Time Symmetric Quantum Walks for Centrality Ranking on Directed Graphs

Tong Wu, Josh Izaac, Zixi Li +5 more

Using quantum walks (QWs) to rank the centrality of nodes in networks, represented by graphs, is advantageous compared to certain widely used classical algorithms. However, it is challenging to implement a directed graph via QW, since it corresponds to a non-Hermitian Hamiltonian and thus cannot be accomplished by conventional QW. Here we report the realizations of centrality rankings of a three-, a four-, and a nine-vertex directed graph with parity-time (PT) symmetric quantum walks by using high-dimensional photonic quantum states, multiple concatenated interferometers, and dimension dependent loss to achieve these. We demonstrate the advantage of the QW approach experimentally by breaking the vertex rank degeneracy in a four-vertex graph. Furthermore, we extend our experiment from single-photon to two-photon Fock states as inputs and realize the centrality ranking of a nine-vertex graph. Our work shows that a PT symmetric multiphoton quantum walk paves the way for realizing advanced algorithms.

arXiv:1912.08411•Physical Review Letters•Dec 8, 2020•24 citations
Abstract In this article, we introduce, test and discuss three quantum methods for computing hub and authority centrality scores in directed networks. The methods are based on unitary, continuous-time quantum walks; the construction of a suitable Hermitian Hamiltonian is achieved by performing a quantum walk on the associated bipartite graph. Two methods, called CQAu and CQAw, use the same evolution operator, inspired by the classical Hyperlink-Induced Topic Search (HITS) algorithm, but with different initial states; the computation of hub and authority scores is performed simultaneously. The third method, called CQG and inspired by classical PageRank, requires instead two separate runs with different evolution operators, one for hub and one for authority scores. The methods are tested on several directed graphs with different sizes and properties; a comparison with other well-established ranking algorithms is provided. CQAw emerges as the most reliable of the three methods and yields rankings that are largely compatible with results from HITS, although CQAu and CQG also present interesting features and potential for applications.
Various quantum-walk-based algorithms have been proposed to analyze and rank the centrality of graph vertices. However, issues arise when working with directed graphs: the resulting non-Hermitian Hamiltonian leads to nonunitary dynamics, and the total probability of the quantum walker is no longer conserved. In this paper, we discuss a method for simulating directed graphs using PTPTPT-symmetric quantum walks, allowing probability-conserving nonunitary evolution. This method is equivalent to mapping the directed graph to an undirected, yet weighted, complete graph over the same vertex set, and can be extended to cover interdependent networks of directed graphs. Previous work has shown centrality measures based on the continuous-time quantum walk provide an eigenvectorlike quantum centrality; using the PTPTPT-symmetric framework, we extend these centrality algorithms to directed graphs with a significantly reduced Hilbert space compared to previous proposals. In certain cases, this centrality measure provides an advantage over classical algorithms used in network analysis, for example, by breaking vertex rank degeneracy. Finally, we perform a statistical analysis over ensembles of random graphs, and show strong agreement with the classical PageRank measure on directed acyclic graphs.
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.
Centrality measure is an essential tool in network analysis and widely used in the domain of computer science, biology and sociology. Taking advantage of the speedup offered by quantum computation, various quantum centrality measures have been proposed. However, few work of quantum centrality involves weighted graphs, while the weight of edges should be considered in certain real-world networks. In this work, we extend the centrality measure based on continuous-time quantum walk to weighted graphs. We testify the feasibility and reliability of this quantum centrality using an ensemble of 41,675 graphs with various topologies and comparing with the eigenvector centrality measure. The average Vigna's correlation index of all the tested graphs with all edge weights in [1, 10] is as high as 0.967, indicating the pretty good consistency of rankings by the continuous-time quantum walk centrality and the eigenvector centrality. The intuitive consistency of the top-ranked vertices given by this quantum centrality measure and classical centrality measures is also demonstrated on large-scale weighted graphs. Moreover, the range of the continuous-time quantum walk centrality values is much bigger than that of classical centralities, which exhibits better distinguishing ability to pick the important vertices from the ones with less importance. All these results show that the centrality measure based on continuous-time quantum walk still works well on weighted graphs.
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.
Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.
Using quantum walks (QWs) to rank the centrality of nodes in networks, represented by graphs, is advantageous compared to certain widely used classical algorithms. However, it is challenging to implement a directed graph via QW, since it corresponds to a non-Hermitian Hamiltonian and thus cannot be accomplished by conventional QW. Here we report the realizations of centrality rankings of a three-, a four-, and a nine-vertex directed graph with parity-time (PT) symmetric quantum walks by using high-dimensional photonic quantum states, multiple concatenated interferometers, and dimension dependent loss to achieve these. We demonstrate the advantage of the QW approach experimentally by breaking the vertex rank degeneracy in a four-vertex graph. Furthermore, we extend our experiment from single-photon to two-photon Fock states as inputs and realize the centrality ranking of a nine-vertex graph. Our work shows that a PT symmetric multiphoton quantum walk paves the way for realizing advanced algorithms.