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

Scientific Reports

Continuous-time quantum walk based centrality testing on weighted graphs

Yang Wang, Shichuan Xue, Junjie Wu, Ping Xu

Published Apr 9, 2022• 15 citations
Publisher

Abstract

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.

DOI
10.1038/s41598-022-09915-1

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

Continuous-time quantum-walk centrality for protein residue interaction networks

Shah Ishmam Mohtashim, Manas Sajjan, Sabre Kais

We present a quantum-dynamical framework for identifying structurally important residues in proteins based on continuous time quantum walks (CTQWs) on weighted residue interaction networks constructed from experimentally resolved structures. By mapping the weighted adjacency matrix to a Hamiltonian, residue importance emerges from the long-time averaged occupation probability, confirmed analytically through its spectral decomposition. Across a dataset of approximately 150 proteins spanning diverse structural and functional classes, CTQW centrality exhibits consistently strong agreement with classical eigenvector centrality in identifying central residues, while extending beyond it through incorporating signatures of quantum interference. Analyzing the time-averaged quantum transition matrix reveals consistently larger spectral gaps than the classical random-walk operator. Furthermore, biological relevance is confirmed through recovery of experimentally established functional residues in proteins kinase A and oxytocin. CTQW-derived centrality rankings are accessible on near-term intermediate-scale quantum hardware, as we demonstrate through a proof-of-principle implementation on IBM superconducting quantum hardware. These results establish continuous-time quantum walks as a computationally tractable framework for protein network analysis, that connects network theoretical treatments of protein structural biology to continuous-time quantum walk dynamics.

quant-pharXiv:2604.17486•Apr 21, 2026•0 citations

Continuous-Time Quantum-Walk Centrality for Protein Residue Interaction Networks

Shah Ishmam Mohtashim, Manas Sajjan, Sabre Kais

We present a quantum-dynamical framework for identifying structurally and functionally important residues in proteins based on continuous-time quantum walks (CTQWs) on weighted residue-interaction networks constructed from experimentally resolved structures. By mapping the weighted adjacency matrix to a Hamiltonian, residue importance emerges from the long-time averaged occupation probability, confirmed analytically through its spectral decomposition. Across a data set of 150 proteins spanning diverse structural and functional classes, CTQW centrality exhibits consistently strong agreement with classical eigenvector centrality in identifying central residues, while extending beyond it through incorporating signatures of quantum interference. Analyzing the time-averaged quantum transition matrix reveals consistently larger spectral gaps than the classical random-walk operator. Furthermore, biological relevance is confirmed through recovery of experimentally established functional residues in proteins kinase A and oxytocin. CTQW-derived centrality rankings are accessible on near-term intermediate-scale quantum hardware, as we demonstrate through a proof-of-principle implementation on IBM superconducting quantum hardware. These results establish continuous-time quantum walks as a computationally tractable framework for protein network analysis, that connects network theoretical treatments of protein structural biology to continuous-time quantum walk dynamics.

Journal of the American Chemical Society•Jun 26, 2026•2 citations

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

Paola Boito, Roberto Grena

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.

arXiv:2104.09637•Journal of Complex Networks•Oct 7, 2021•5 citations

Centrality measure based on continuous-time quantum walks and experimental realization

Josh Izaac, Xiang Zhan, Zhihao Bian +4 more

Network centrality has important implications well beyond its role in physical and information transport analysis; as such, various quantum-walk-based algorithms have been proposed for measuring network vertex centrality. In this work, we propose a continuous-time quantum walk algorithm for determining vertex centrality, and show that it generalizes to arbitrary graphs via a statistical analysis of randomly generated scale-free and Erd\ifmmode \mbox{\H{o}}\else \H{o}\fi{}s-R\'enyi networks. As a proof of concept, the algorithm is detailed on a four-vertex star graph and physically implemented via linear optics, using spatial and polarization degrees of freedoms of single photons. This paper reports a successful physical demonstration of a quantum centrality algorithm.

arXiv:1702.03493•Physical Review A•Mar 13, 2017•46 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
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.
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.
We present a quantum-dynamical framework for identifying structurally important residues in proteins based on continuous time quantum walks (CTQWs) on weighted residue interaction networks constructed from experimentally resolved structures. By mapping the weighted adjacency matrix to a Hamiltonian, residue importance emerges from the long-time averaged occupation probability, confirmed analytically through its spectral decomposition. Across a dataset of approximately 150 proteins spanning diverse structural and functional classes, CTQW centrality exhibits consistently strong agreement with classical eigenvector centrality in identifying central residues, while extending beyond it through incorporating signatures of quantum interference. Analyzing the time-averaged quantum transition matrix reveals consistently larger spectral gaps than the classical random-walk operator. Furthermore, biological relevance is confirmed through recovery of experimentally established functional residues in proteins kinase A and oxytocin. CTQW-derived centrality rankings are accessible on near-term intermediate-scale quantum hardware, as we demonstrate through a proof-of-principle implementation on IBM superconducting quantum hardware. These results establish continuous-time quantum walks as a computationally tractable framework for protein network analysis, that connects network theoretical treatments of protein structural biology to continuous-time quantum walk dynamics.
We present a quantum-dynamical framework for identifying structurally and functionally important residues in proteins based on continuous-time quantum walks (CTQWs) on weighted residue-interaction networks constructed from experimentally resolved structures. By mapping the weighted adjacency matrix to a Hamiltonian, residue importance emerges from the long-time averaged occupation probability, confirmed analytically through its spectral decomposition. Across a data set of 150 proteins spanning diverse structural and functional classes, CTQW centrality exhibits consistently strong agreement with classical eigenvector centrality in identifying central residues, while extending beyond it through incorporating signatures of quantum interference. Analyzing the time-averaged quantum transition matrix reveals consistently larger spectral gaps than the classical random-walk operator. Furthermore, biological relevance is confirmed through recovery of experimentally established functional residues in proteins kinase A and oxytocin. CTQW-derived centrality rankings are accessible on near-term intermediate-scale quantum hardware, as we demonstrate through a proof-of-principle implementation on IBM superconducting quantum hardware. These results establish continuous-time quantum walks as a computationally tractable framework for protein network analysis, that connects network theoretical treatments of protein structural biology to continuous-time quantum walk dynamics.
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.
Network centrality has important implications well beyond its role in physical and information transport analysis; as such, various quantum-walk-based algorithms have been proposed for measuring network vertex centrality. In this work, we propose a continuous-time quantum walk algorithm for determining vertex centrality, and show that it generalizes to arbitrary graphs via a statistical analysis of randomly generated scale-free and Erd\ifmmode \mbox{\H{o}}\else \H{o}\fi{}s-R\'enyi networks. As a proof of concept, the algorithm is detailed on a four-vertex star graph and physically implemented via linear optics, using spatial and polarization degrees of freedoms of single photons. This paper reports a successful physical demonstration of a quantum centrality algorithm.
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.