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

CRC Press eBooks

Applications of Quantum Walks in Community Detection

Fei Yan, Liang Wen, Fangyan Dong

Published Nov 24, 2025• 0 citations
Publisher

Abstract

This chapter elucidates the applications of discrete-time quantum walks in community detection, featuring the two-stage quantum walk algorithm and the Fourier quantum walk algorithm. It further investigates the applications of continuous-time quantum walks in community detection, specifically continuous-time quantum walks between communities and within communities.

DOI
10.1201/9781003683902-7

Related papers

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

Applications of Quantum Walks in Node Discovery

Fei Yan, Liang Wen, Fangyan Dong

This chapter explores the applications of discrete-time quantum walks in node mining, covering algorithms such as the quantum PageRank, the parameterized coin quantum walk, and the three-degree decay Grover walk. It also examines the applications of continuous-time quantum walks in this domain, including adaptations of the Google PageRank algorithm for open quantum systems, the quantum Jensen-Shannon divergence algorithm, and an information propagation model based on quantum walks.

CRC Press eBooks•Nov 24, 2025•0 citations

Quantum Walks: Theory, Application, and Implementation

Albert T. Schmitz

The quantum walk is a method for conceptualizing and designing quantum computing algorithms and it comes in two forms: the continuous-time and discrete-time quantum walk. The thesis is organized into three parts, each of which looks to develop the concept and uses of the quantum walk. The first part is the theory of the quantum walk. This includes definitions and considerations for the various incarnations of the discrete-time quantum walk and a discussion on the general method for connecting the continuous-time and discrete-time versions. As a result, it is shown that most versions of the discrete-time quantum walk can be put into a general form and this can be used to simulate any continuous-time quantum walk. The second part uses these results for a hypothetical application. The application presented is a search algorithm that appears to scale in the time for completion independent of the size of the search space. This behavior is then elaborated upon and shown to have general qualitative agreement with simulations to within the approximations that are made. The third part introduces a method of implementation. Given a universal quantum computer, the method is discussed and shown to simulate an arbitrary discrete-time quantum walk. Some of the benefits of this method are that half the unitary evolution can be achieved without the use of any gates and there may be some possibility for error detection. The three parts combined suggest a possible experiment, given a quantum computing scheme of sufficient robustness.

•Jan 1, 2016•1 citation

Foundational Theory of Quantum Walks

Fei Yan, Liang Wen, Fangyan Dong

This chapter presents the quantum walks on regular graphs (including low-dimensional discrete-time quantum walks, one-dimensional continuous-time quantum walks, and related variants) as well as quantum walks on complex networks. It provides a general framework for describing and defining quantum walk algorithms on complex networks.

CRC Press eBooks•Nov 24, 2025•0 citations

Community Detection in Complex Networks with Quantum Random Walks

Dimitris I. Tsomokos

Complex networks are structurally disordered systems that often display clustering behavior. The emergent clusters, also known as communities, consist of nodes that are more connected among themselves than they are connected with the rest of the network. Analyzing community structure is an important problem in network theory, with numerous applications in different fields. In this work I investigate the evolution of a continuoustime quantum random walk on a social network with benchmark community structure and show that it can be used to perform community detection.

•Dec 14, 2010•2 citations

Community detection in network using Szegedy quantum walk

Md Samsur Rahaman, Supriyo Dutta

In a network, the vertices with similar characteristics construct communities. The vertices in a community are well-connected. Detecting the communities in a network is a challenging and important problem in the theory of complex networks. One approach to solving this problem uses the classical random walks on graphs. In quantum computing, quantum walks are the quantum mechanical counterparts of classical random walks. In this article, we employ a variant of Szegedy's quantum walk to develop a procedure for discovering the communities in networks. The limiting probability distribution of quantum walks assists us in determining the inclusion of a vertex in a community. We apply our community detection procedure to a variety of graphs and social networks, including the relaxed caveman graph, $l$-partition graph, Karate club graph, and the dolphin's social network, among others.

quant-pharXiv:2601.21152•Jan 30, 2026•1 citation
This chapter elucidates the applications of discrete-time quantum walks in community detection, featuring the two-stage quantum walk algorithm and the Fourier quantum walk algorithm. It further investigates the applications of continuous-time quantum walks in community detection, specifically continuous-time quantum walks between communities and within communities.
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.
The quantum walk is a method for conceptualizing and designing quantum computing algorithms and it comes in two forms: the continuous-time and discrete-time quantum walk. The thesis is organized into three parts, each of which looks to develop the concept and uses of the quantum walk. The first part is the theory of the quantum walk. This includes definitions and considerations for the various incarnations of the discrete-time quantum walk and a discussion on the general method for connecting the continuous-time and discrete-time versions. As a result, it is shown that most versions of the discrete-time quantum walk can be put into a general form and this can be used to simulate any continuous-time quantum walk. The second part uses these results for a hypothetical application. The application presented is a search algorithm that appears to scale in the time for completion independent of the size of the search space. This behavior is then elaborated upon and shown to have general qualitative agreement with simulations to within the approximations that are made. The third part introduces a method of implementation. Given a universal quantum computer, the method is discussed and shown to simulate an arbitrary discrete-time quantum walk. Some of the benefits of this method are that half the unitary evolution can be achieved without the use of any gates and there may be some possibility for error detection. The three parts combined suggest a possible experiment, given a quantum computing scheme of sufficient robustness.
Complex networks are structurally disordered systems that often display clustering behavior. The emergent clusters, also known as communities, consist of nodes that are more connected among themselves than they are connected with the rest of the network. Analyzing community structure is an important problem in network theory, with numerous applications in different fields. In this work I investigate the evolution of a continuoustime quantum random walk on a social network with benchmark community structure and show that it can be used to perform community detection.
In a network, the vertices with similar characteristics construct communities. The vertices in a community are well-connected. Detecting the communities in a network is a challenging and important problem in the theory of complex networks. One approach to solving this problem uses the classical random walks on graphs. In quantum computing, quantum walks are the quantum mechanical counterparts of classical random walks. In this article, we employ a variant of Szegedy's quantum walk to develop a procedure for discovering the communities in networks. The limiting probability distribution of quantum walks assists us in determining the inclusion of a vertex in a community. We apply our community detection procedure to a variety of graphs and social networks, including the relaxed caveman graph, lll-partition graph, Karate club graph, and the dolphin's social network, among others.