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

International Journal of Modern Physics C

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

Wei-Min Shi, Li-Na Wu, Jia-Wei Liang, Yi‐Hua Zhou, Yu‐Guang Yang

Published Apr 11, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1142/s0129183125501013

Related papers

Discrete quantum-classical walks for link prediction

A. Marin, M. Soto-Gomez, Giorgio Valentini +3 more

Link prediction is a fundamental task in network science that involves estimating the likelihood of missing or future connections between nodes based on the structural patterns of a graph. While Graph Neural Networks (GNNs) have become a dominant approach, Random Walk (RW)-based methods remain highly relevant due to their lower computational demands in large-scale networks. Although recent hybrid quantum-classical walks have shown promise in exploring graph structures, existing continuous-time models are computationally expensive as they require solving high-dimensional systems of differential equations. In this paper, we propose a discrete version of a recent hybrid quantum-classical random walk algorithm that significantly improves computational efficiency by utilizing state vector representations instead of density matrices. Our method, inspired by the Quantum Jumps approach, alternates between coherent evolution and measurement-driven state collapse to generate trajectories for node embeddings. We integrate this algorithm into a link prediction pipeline and evaluate its performance across various synthetic topologies, including Grid, Power-Law, Erdös-Rényi, Barabási-Albert, and Community graphs. The experimental results demonstrate that the proposed discrete hybrid walks consistently outperform classical random walk approaches in Community and Grid topologies, showing that quantum-inspired dynamics can capture complex structural information more effectively than classical dynamics for specific topologies.

IEEE Conference on Artificial Intelligence (CAI)•May 8, 2026•0 citations

Link prediction using discrete-time quantum walk

Qian, Jing, Lintao Yang, Zetai Yu +1 more

Original scientific paperLink prediction is one of the key issues of complex networks, which attracts much research interest currently.Many link prediction methods have been proposed so far.The classical random walk as an effective tool has been widely used to study the link prediction problems.Quantum walk is the quantum analogue of classical random walk.Numerous research results show that quantum algorithms using quantum walk outperform their classical counterparts in many applications, such as graph matching and searching.But there have been few studies of the link prediction based on quantum walk, especially on discrete-time quantum walk.This paper proposes a new link prediction method based on discrete-time quantum walk.Experiment results show that prediction accuracy of our method is better than the typical methods.The time complexity of our method running on classical computers, compared with the methods based on classical random walk, is slightly higher.But our method can be greatly accelerated by executing on quantum computers.

Tehnicki vjesnik - Technical Gazette•Oct 1, 2017•4 citations

QuantumSim: Practical Simulation and Analysis of Discrete-Time Quantum Walks on Line and Cycle Graphs

Karuna Kadian, Sunita Garhwal, Ajay Kumar

The article describes how Discrete Time Quantum Walks (DTQWs) provide a useful means for recreating-quantum physical behaviour on graph structures, focusing on the effects of ballistic propagating effects and destructive interference, Methods were developed to simulate DTQWs using classical methods to visualise the changes in the probability distribution of the walker over time, specifically focusing on the Distal Path of the walker. A hybrid quantum machine learning model has been developed which combines the quantum features of quantum walk dynamics with classic technical indicators such as Relative Strength Index (RSI) and Moving Average Convergence Divergence (MACD), to enable the classification of financial trends. The classification model was trained on a synthetically balanced dataset created using Synthetic Minority Over-sampling Technique SMOTE and performance was assessed using standard metrics such as accuracy, precision and recall. The simulation results were evaluated and visualised in terms of their probability distributions. A successful model has been found which produces similar forecasting results compared with those achieved by normal benchmark methods for stock movement and portfolio construction.

International Conference on Artificial Intelligence and Speech Technology (AIST)•Nov 27, 2025•0 citations

GCQW: A Quantum Walk Model for Predicting Missing Links of Complex Networks

Wen Liang, Fei Yan, Abdullah M. Iliyasu +1 more

Link prediction remains a challenging pursuit in existing complex networks. Our study proposes a Grover coin driven quantum walk (GCQW) model for prediction of missing edges on complex networks. The GCQW model uses observed probabilities of common neighbours of two nodes as similarity between the nodes. Furthermore, each walk step of the proposed model is determined by a three degree of influence rule. Results of experiments based on the area under the receiver operating characteristic curve (AUC) index demonstrate the proposed model’s performance in eight real complex networks outperforms nine conventional comparison algorithms. Outcomes show that even when the ratio of testing to training is set in the range 0.1∼0.5, our GCQW model maintained a stable and competitive performance in terms of the AUC index. The proposed GCQW model will be expectedly applied in function modular mining of protein-protein interaction networks and friend recommendation of social media.

International Conference on Information Communication and Software Engineering (ICICSE)•Mar 18, 2022•1 citation

Quantum Walk-Based Routing Protocols for Wireless Networks

Jincheng Zhang

This paper investigates the application of quantum walks to routing protocols within wireless networks. Traditional routing algorithms often struggle with efficiency and convergence speed, particularly in dynamic and complex network topologies. We propose a novel approach utilizing quantum walk principles to explore network connectivity and identify optimal routes. Our methodology employs a quantum walk algorithm to simulate network traversal, leveraging quantum superposition and interference to potentially achieve faster convergence and reduced latency compared to classical approaches. The core of the system relies on a discrete-time quantum walk on a graph representing the wireless network, where nodes are the walkers and edges represent communication links. The algorithm aims to minimize the walk length, effectively finding the shortest path between source and destination nodes. We present a theoretical framework and outline the key components of a quantum walk-based routing protocol. While this research focuses on the theoretical aspects and does not include experimental validation, it lays the foundation for future work exploring the practical feasibility and performance benefits of quantum walk routing in real-world wireless network scenarios.

•Aug 31, 2026•0 citations

A study and analysis of a discrete quantum walk-based hybrid clustering approach using d-regular bipartite graph and 1D lattice

Sanjay Chakraborty, Soharab Hossain Shaikh, Sudhindu Bikash Mandal +2 more

Traditional machine learning shares several benefits with quantum information processing field. The study of machine learning with quantum mechanics is called quantum machine learning. Data clustering is an important tool for machine learning where quantum computing plays a vital role in its inherent speed up capability. In this paper, a hybrid quantum algorithm for data clustering (quantum walk-based hybrid clustering (QWBHC)) is introduced where one-dimensional discrete time quantum walks (DTQW) play the central role to update the positions of data points according to their probability distributions. A quantum oracle is also designed and it is mainly implemented on a finite [Formula: see text]-regular bipartite graph where data points are initially distributed as a predefined set of clusters. An overview of a quantum walk (QW) based clustering algorithm on 1D lattice structure is also introduced and described in this paper. In order to search the nearest neighbors, a unitary and reversible DTQW gives a quadratic speed up over the traditional classical random walk. This paper also demonstrates the comparisons of our proposed hybrid quantum clustering algorithm with some state-of-the-art clustering algorithms in terms of clustering accuracy and time complexity analysis. The proposed quantum oracle needs [Formula: see text] queries to mark the nearest data points among clusters and modify the existing clusters. Finally, the proposed QWBHC algorithm achieves [Formula: see text] performance.

International Journal of Quantum Information•Mar 1, 2019•5 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.
Link prediction is a fundamental task in network science that involves estimating the likelihood of missing or future connections between nodes based on the structural patterns of a graph. While Graph Neural Networks (GNNs) have become a dominant approach, Random Walk (RW)-based methods remain highly relevant due to their lower computational demands in large-scale networks. Although recent hybrid quantum-classical walks have shown promise in exploring graph structures, existing continuous-time models are computationally expensive as they require solving high-dimensional systems of differential equations. In this paper, we propose a discrete version of a recent hybrid quantum-classical random walk algorithm that significantly improves computational efficiency by utilizing state vector representations instead of density matrices. Our method, inspired by the Quantum Jumps approach, alternates between coherent evolution and measurement-driven state collapse to generate trajectories for node embeddings. We integrate this algorithm into a link prediction pipeline and evaluate its performance across various synthetic topologies, including Grid, Power-Law, Erdös-Rényi, Barabási-Albert, and Community graphs. The experimental results demonstrate that the proposed discrete hybrid walks consistently outperform classical random walk approaches in Community and Grid topologies, showing that quantum-inspired dynamics can capture complex structural information more effectively than classical dynamics for specific topologies.
Original scientific paperLink prediction is one of the key issues of complex networks, which attracts much research interest currently.Many link prediction methods have been proposed so far.The classical random walk as an effective tool has been widely used to study the link prediction problems.Quantum walk is the quantum analogue of classical random walk.Numerous research results show that quantum algorithms using quantum walk outperform their classical counterparts in many applications, such as graph matching and searching.But there have been few studies of the link prediction based on quantum walk, especially on discrete-time quantum walk.This paper proposes a new link prediction method based on discrete-time quantum walk.Experiment results show that prediction accuracy of our method is better than the typical methods.The time complexity of our method running on classical computers, compared with the methods based on classical random walk, is slightly higher.But our method can be greatly accelerated by executing on quantum computers.
The article describes how Discrete Time Quantum Walks (DTQWs) provide a useful means for recreating-quantum physical behaviour on graph structures, focusing on the effects of ballistic propagating effects and destructive interference, Methods were developed to simulate DTQWs using classical methods to visualise the changes in the probability distribution of the walker over time, specifically focusing on the Distal Path of the walker. A hybrid quantum machine learning model has been developed which combines the quantum features of quantum walk dynamics with classic technical indicators such as Relative Strength Index (RSI) and Moving Average Convergence Divergence (MACD), to enable the classification of financial trends. The classification model was trained on a synthetically balanced dataset created using Synthetic Minority Over-sampling Technique SMOTE and performance was assessed using standard metrics such as accuracy, precision and recall. The simulation results were evaluated and visualised in terms of their probability distributions. A successful model has been found which produces similar forecasting results compared with those achieved by normal benchmark methods for stock movement and portfolio construction.
Link prediction remains a challenging pursuit in existing complex networks. Our study proposes a Grover coin driven quantum walk (GCQW) model for prediction of missing edges on complex networks. The GCQW model uses observed probabilities of common neighbours of two nodes as similarity between the nodes. Furthermore, each walk step of the proposed model is determined by a three degree of influence rule. Results of experiments based on the area under the receiver operating characteristic curve (AUC) index demonstrate the proposed model’s performance in eight real complex networks outperforms nine conventional comparison algorithms. Outcomes show that even when the ratio of testing to training is set in the range 0.1∼0.5, our GCQW model maintained a stable and competitive performance in terms of the AUC index. The proposed GCQW model will be expectedly applied in function modular mining of protein-protein interaction networks and friend recommendation of social media.
This paper investigates the application of quantum walks to routing protocols within wireless networks. Traditional routing algorithms often struggle with efficiency and convergence speed, particularly in dynamic and complex network topologies. We propose a novel approach utilizing quantum walk principles to explore network connectivity and identify optimal routes. Our methodology employs a quantum walk algorithm to simulate network traversal, leveraging quantum superposition and interference to potentially achieve faster convergence and reduced latency compared to classical approaches. The core of the system relies on a discrete-time quantum walk on a graph representing the wireless network, where nodes are the walkers and edges represent communication links. The algorithm aims to minimize the walk length, effectively finding the shortest path between source and destination nodes. We present a theoretical framework and outline the key components of a quantum walk-based routing protocol. While this research focuses on the theoretical aspects and does not include experimental validation, it lays the foundation for future work exploring the practical feasibility and performance benefits of quantum walk routing in real-world wireless network scenarios.
Traditional machine learning shares several benefits with quantum information processing field. The study of machine learning with quantum mechanics is called quantum machine learning. Data clustering is an important tool for machine learning where quantum computing plays a vital role in its inherent speed up capability. In this paper, a hybrid quantum algorithm for data clustering (quantum walk-based hybrid clustering (QWBHC)) is introduced where one-dimensional discrete time quantum walks (DTQW) play the central role to update the positions of data points according to their probability distributions. A quantum oracle is also designed and it is mainly implemented on a finite [Formula: see text]-regular bipartite graph where data points are initially distributed as a predefined set of clusters. An overview of a quantum walk (QW) based clustering algorithm on 1D lattice structure is also introduced and described in this paper. In order to search the nearest neighbors, a unitary and reversible DTQW gives a quadratic speed up over the traditional classical random walk. This paper also demonstrates the comparisons of our proposed hybrid quantum clustering algorithm with some state-of-the-art clustering algorithms in terms of clustering accuracy and time complexity analysis. The proposed quantum oracle needs [Formula: see text] queries to mark the nearest data points among clusters and modify the existing clusters. Finally, the proposed QWBHC algorithm achieves [Formula: see text] performance.