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

Tehnicki vjesnik - Technical Gazette

Link prediction using discrete-time quantum walk

Qian, Jing, Lintao Yang, Zetai Yu, Shouyin Liu

Published Oct 1, 2017• 4 citations
Publisher

Abstract

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.

DOI
10.17559/tv-20160104014155

Related papers

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

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

Quantum link prediction in complex networks

João P. Moutinho, André Melo, Bruno Coelho Coutinho +2 more

Predicting new links in physical, biological, social, or technological networks has a significant scientific and societal impact. Path-based link prediction methods utilize the explicit counting of even- and odd-length paths between nodes to quantify a score function and infer new or unobserved links. Here, we propose a quantum algorithm for path-based link prediction using a controlled continuous-time quantum walk to encode even and odd path-based prediction scores. Through classical simulations on a few real networks, we confirm that the quantum walk scoring function performs similarly to other path-based link predictors. In a brief complexity analysis we identify the potential of our approach in uncovering a quantum speedup for path-based link prediction.

arXiv:2112.04768•Physical Review A•Mar 10, 2023•32 citations

Random Walks: A Review of Algorithms and Applications

Feng Xia, Jiaying Liu, Hansong Nie +3 more

A random walk is known as a random process which describes a path including a succession of random steps in the mathematical space. It has increasingly been popular in various disciplines such as mathematics and computer science. Furthermore, in quantum mechanics, quantum walks can be regarded as quantum analogues of classical random walks. Classical random walks and quantum walks can be used to calculate the proximity between nodes and extract the topology in the network. Various random walk related models can be applied in different fields, which is of great significance to downstream tasks such as link prediction, recommendation, computer vision, semi-supervised learning, and network embedding. In this article, we aim to provide a comprehensive review of classical random walks and quantum walks. We first review the knowledge of classical random walks and quantum walks, including basic concepts and some typical algorithms. We also compare the algorithms based on quantum walks and classical random walks from the perspective of time complexity. Then we introduce their applications in the field of computer science. Finally we discuss the open issues from the perspectives of efficiency, main-memory volume, and computing time of existing algorithms. This study aims to contribute to this growing area of research by exploring random walks and quantum walks together.

arXiv:2008.03639•IEEE Transactions on Emerging Topics in Computational Intelligence•Nov 25, 2019•329 citations

Application of quantum walks on graph structures to quantum computing

Neil B. Lovett

Quantum computation is a new computational paradigm which can provide fundamentally faster computation than in the classical regime. This is dependent on finding efficient quantum algorithms for problems of practical interest. One of the most successful tools in developing new quantum algorithms is the quantum walk. In this thesis, we explore two applications of the discrete time quantum walk. In addition, we introduce an experimental scheme for generating cluster states, a universal resource for quantum computation. We give an explicit construction which provides a link between the circuit model of quantum computation, and a graph structure on which the discrete time quantum walk traverses, performing the same computation. We implement a universal gate set, proving the discrete time quantum walk is universal for quantum computation, thus confirming any quantum algorithm can be recast as a quantum walk algorithm. In addition, we study factors affecting the efficiency of the quantum walk search algorithm. Although there is a strong dependence on the spatial dimension of the structure being searched, we find secondary dependencies on other factors including the connectivity and disorder (symmetry). Fairly intuitively, as the connectivity increases, the efficiency of the algorithm increases, as the walker can coalesce on the marked state with higher probability in a quicker time. In addition, we find as disorder in the system increases, the algorithm can maintain the quantum speed up for a certain level of disorder before gradually reverting to the classical run time. Finally, we give an abstract scheme for generating cluster states. We see a linear scaling, better than many schemes, as doubling the size of the generating grid in our scheme produces a cluster state which is double the depth. Our scheme is able to create other interesting topologies of entangled states, including the unit cell for topological error correcting schemes.

•Mar 1, 2011•6 citations

Discrete-time quantum walk on complex networks for community detection

Kanae Mukai, Naomichi Hatano

Many systems such as social networks and biological networks take the form of complex networks, which have a community structure.Community detection in complex networks is of great interest to many researchers in statistical physics and mathematical physics.There have been studies on community detection that use the classical random walk.The present study utilizes the discrete-time quantum walk instead.The quantum walk plays an important role in various fields, especially in research on quantum computers, and attracts much attention from mathematical physics too.The discrete-time quantum walk has two properties: it linearly spreads on a flat space, and it localizes in some cases because of quantum coherence.We demonstrate that these properties of the quantum walk are useful for community detection on complex networks.We define the discrete-time quantum walk on complex networks and utilize it for community detection.We numerically show that the quantum walk with a Fourier coin is localized in a community to which the initial node belongs.Meanwhile, the quantum walk with a Grover coin tends to be localized around the initial node, not over a community.The probability of a classical random walk on the same network converges to a uniform distribution with a relaxation time generally unknown a priori.We thus claim that the time average of the probability of a Fourier-coin quantum walk on complex networks reveals the community structure more explicitly than that of a Grover-coin quantum walk and a snapshot of the classical random walk.We first demonstrate our method of community detection for a prototypical three-community network, producing the correct grouping.We then apply our method to two real-world networks, namely, Zachary's karate club and the U.S. Airport network.We successfully reveal the community structure, the two communities of the instructor and the administrator in the former and major airline companies in the latter.

arXiv:2005.13104•Physical Review Research•Jun 22, 2020•42 citations
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.
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.
Predicting new links in physical, biological, social, or technological networks has a significant scientific and societal impact. Path-based link prediction methods utilize the explicit counting of even- and odd-length paths between nodes to quantify a score function and infer new or unobserved links. Here, we propose a quantum algorithm for path-based link prediction using a controlled continuous-time quantum walk to encode even and odd path-based prediction scores. Through classical simulations on a few real networks, we confirm that the quantum walk scoring function performs similarly to other path-based link predictors. In a brief complexity analysis we identify the potential of our approach in uncovering a quantum speedup for path-based link prediction.
A random walk is known as a random process which describes a path including a succession of random steps in the mathematical space. It has increasingly been popular in various disciplines such as mathematics and computer science. Furthermore, in quantum mechanics, quantum walks can be regarded as quantum analogues of classical random walks. Classical random walks and quantum walks can be used to calculate the proximity between nodes and extract the topology in the network. Various random walk related models can be applied in different fields, which is of great significance to downstream tasks such as link prediction, recommendation, computer vision, semi-supervised learning, and network embedding. In this article, we aim to provide a comprehensive review of classical random walks and quantum walks. We first review the knowledge of classical random walks and quantum walks, including basic concepts and some typical algorithms. We also compare the algorithms based on quantum walks and classical random walks from the perspective of time complexity. Then we introduce their applications in the field of computer science. Finally we discuss the open issues from the perspectives of efficiency, main-memory volume, and computing time of existing algorithms. This study aims to contribute to this growing area of research by exploring random walks and quantum walks together.
Quantum computation is a new computational paradigm which can provide fundamentally faster computation than in the classical regime. This is dependent on finding efficient quantum algorithms for problems of practical interest. One of the most successful tools in developing new quantum algorithms is the quantum walk. In this thesis, we explore two applications of the discrete time quantum walk. In addition, we introduce an experimental scheme for generating cluster states, a universal resource for quantum computation. We give an explicit construction which provides a link between the circuit model of quantum computation, and a graph structure on which the discrete time quantum walk traverses, performing the same computation. We implement a universal gate set, proving the discrete time quantum walk is universal for quantum computation, thus confirming any quantum algorithm can be recast as a quantum walk algorithm. In addition, we study factors affecting the efficiency of the quantum walk search algorithm. Although there is a strong dependence on the spatial dimension of the structure being searched, we find secondary dependencies on other factors including the connectivity and disorder (symmetry). Fairly intuitively, as the connectivity increases, the efficiency of the algorithm increases, as the walker can coalesce on the marked state with higher probability in a quicker time. In addition, we find as disorder in the system increases, the algorithm can maintain the quantum speed up for a certain level of disorder before gradually reverting to the classical run time. Finally, we give an abstract scheme for generating cluster states. We see a linear scaling, better than many schemes, as doubling the size of the generating grid in our scheme produces a cluster state which is double the depth. Our scheme is able to create other interesting topologies of entangled states, including the unit cell for topological error correcting schemes.
Many systems such as social networks and biological networks take the form of complex networks, which have a community structure.Community detection in complex networks is of great interest to many researchers in statistical physics and mathematical physics.There have been studies on community detection that use the classical random walk.The present study utilizes the discrete-time quantum walk instead.The quantum walk plays an important role in various fields, especially in research on quantum computers, and attracts much attention from mathematical physics too.The discrete-time quantum walk has two properties: it linearly spreads on a flat space, and it localizes in some cases because of quantum coherence.We demonstrate that these properties of the quantum walk are useful for community detection on complex networks.We define the discrete-time quantum walk on complex networks and utilize it for community detection.We numerically show that the quantum walk with a Fourier coin is localized in a community to which the initial node belongs.Meanwhile, the quantum walk with a Grover coin tends to be localized around the initial node, not over a community.The probability of a classical random walk on the same network converges to a uniform distribution with a relaxation time generally unknown a priori.We thus claim that the time average of the probability of a Fourier-coin quantum walk on complex networks reveals the community structure more explicitly than that of a Grover-coin quantum walk and a snapshot of the classical random walk.We first demonstrate our method of community detection for a prototypical three-community network, producing the correct grouping.We then apply our method to two real-world networks, namely, Zachary's karate club and the U.S. Airport network.We successfully reveal the community structure, the two communities of the instructor and the administrator in the former and major airline companies in the latter.