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:1905.06575 · Quantum Information Processing

Discrete-time quantum walk algorithm for ranking nodes on a network

Prateek Chawla, Roopesh Mangal, C. M. Chandrashekar

Published Mar 31, 2020• 33 citations
arXivHTMLPDF
DOI
10.1007/s11128-020-02650-4

Related papers

Ranking nodes in directed networks via continuous-time quantum walks

Paola Boito, Roberto Grena

arXiv:2210.13379•Quantum Information Processing•Jun 13, 2023•4 citations

A link prediction algorithm based on discrete-time quantum walk model on weighted graphs

Wei-Min Shi, Li-Na Wu, Jia-Wei Liang +2 more

Compared with the classical random walk, the quantum walk has the advantages of less time to find the target node and less time scattered from the source node to all nodes. Therefore, in order to further improve the accuracy of link prediction algorithms, a link prediction algorithm based on discrete-time quantum walk (DTQW) on weighted graphs is proposed by integrating node attributes and introducing the idea of assigning weights to edges in network dynamics. In this algorithm, a weighted graph is first constructed based on the attribute information of nodes in the graph, and then a DTQW model is constructed based on the weighted graph. Then, under the control of the evolution operator, the walker performs a DTQW on the weighted graph; Finally, the link prediction algorithm is implemented by defining the similarity between nodes based on the average probability of the walker reaching each node. The experimental results show that in three real social networks, Douban, Weibo and Zhihu, this algorithm has different degrees of improvement in prediction accuracy and the algorithm stability is among the top in comparison with the optimal benchmark prediction algorithm.

International Journal of Modern Physics C•Apr 11, 2025•0 citations

Circuit Implementation of Discrete-Time Quantum Walks on Complex Networks

Rei Sato, Kazuhiro Saito

In this paper, we propose a circuit design for implementing quantum walks on complex networks. Quantum walks are powerful tools for various graph-based applications such as spatial search, community detection, and node classification. Although many quantum-walk-based graph algorithms have been extensively studied, specific quantum circuits for implementing these algorithms have not yet been provided. To address this issue, we present a circuit design for implementing the discrete-time quantum walk on complex networks. We investigate the functionality of our circuit using the small-sized Watts-and-Strogatz model as the complex network model, comparing it with theoretical calculations. This work offers a new approach to constructing quantum circuits for implementing quantum walks on arbitrary complex networks.

arXiv:2408.15653•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•2 citations

Discrete-time quantum walk-based optimization algorithm

Ioannis Liliopoulos, Georgios D. Varsamis, Ioannis G. Karafyllidis

Quantum Information Processing•Jan 17, 2024•7 citations

Forward Discrete‐Time Quantum Walk for Efficiently Identifying Critical Nodes of Complex Networks

Zhengyi Wang, Feng Gao, Yuan Xu +2 more

Abstract Critical node identification is the precondition for exploring complex networks, which is a graph‐based optimal search problem in principle. Classical methods, hindered by limited parallel processing capabilities, often grapple with high computational demands and inefficiency. Recent studies have leveraged quantum walk (QW) to tackle such challenges. However, existing QW‐based approaches are constrained by graph structures and prone to recurrent traversal issues. Being different, a novel forward discrete‐time quantum walk (F‐DTQW) method is proposed, which can traverse without redundant visits by prohibiting reverse and lateral propagations. The proposed method significantly enhances the efficiency of critical node identification and is applicable to arbitrary complex networks. The proposed method is validated on typical complex networks such as small‐world, scale‐free, and directed networks, and calculates the transition probability of nodes, corresponding to the centrality measurement index of transition connectivity (TC), which expands from the betweenness centrality (BC) index. The time complexity of F‐DTQW is also analyzed, which is reduced from O ( N 3 ) to O ( N 2 ) compared to the classical method.

Advanced Quantum Technologies•Jul 31, 2025•1 citation

Applications of quantum walk algorithms

de Jan Vos

•Aug 1, 2006•0 citations
Compared with the classical random walk, the quantum walk has the advantages of less time to find the target node and less time scattered from the source node to all nodes. Therefore, in order to further improve the accuracy of link prediction algorithms, a link prediction algorithm based on discrete-time quantum walk (DTQW) on weighted graphs is proposed by integrating node attributes and introducing the idea of assigning weights to edges in network dynamics. In this algorithm, a weighted graph is first constructed based on the attribute information of nodes in the graph, and then a DTQW model is constructed based on the weighted graph. Then, under the control of the evolution operator, the walker performs a DTQW on the weighted graph; Finally, the link prediction algorithm is implemented by defining the similarity between nodes based on the average probability of the walker reaching each node. The experimental results show that in three real social networks, Douban, Weibo and Zhihu, this algorithm has different degrees of improvement in prediction accuracy and the algorithm stability is among the top in comparison with the optimal benchmark prediction algorithm.
In this paper, we propose a circuit design for implementing quantum walks on complex networks. Quantum walks are powerful tools for various graph-based applications such as spatial search, community detection, and node classification. Although many quantum-walk-based graph algorithms have been extensively studied, specific quantum circuits for implementing these algorithms have not yet been provided. To address this issue, we present a circuit design for implementing the discrete-time quantum walk on complex networks. We investigate the functionality of our circuit using the small-sized Watts-and-Strogatz model as the complex network model, comparing it with theoretical calculations. This work offers a new approach to constructing quantum circuits for implementing quantum walks on arbitrary complex networks.
Abstract Critical node identification is the precondition for exploring complex networks, which is a graph‐based optimal search problem in principle. Classical methods, hindered by limited parallel processing capabilities, often grapple with high computational demands and inefficiency. Recent studies have leveraged quantum walk (QW) to tackle such challenges. However, existing QW‐based approaches are constrained by graph structures and prone to recurrent traversal issues. Being different, a novel forward discrete‐time quantum walk (F‐DTQW) method is proposed, which can traverse without redundant visits by prohibiting reverse and lateral propagations. The proposed method significantly enhances the efficiency of critical node identification and is applicable to arbitrary complex networks. The proposed method is validated on typical complex networks such as small‐world, scale‐free, and directed networks, and calculates the transition probability of nodes, corresponding to the centrality measurement index of transition connectivity (TC), which expands from the betweenness centrality (BC) index. The time complexity of F‐DTQW is also analyzed, which is reduced from O ( N 3 ) to O ( N 2 ) compared to the classical method.