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

The Computer Journal

Discrete-Time Quantum Walks Community Detection in Multi-Domain Networks

Xiaoyang Liu, Nan Ding, Yudie Wu, Giacomo Fiumara, Pasquale De Meo

Published Feb 8, 2024• 4 citations
Publisher

Abstract

Abstract The problem of detecting communities in real-world networks has been extensively studied in the past, but most of the existing approaches work on single-domain networks, i.e. they consider only one type of relationship between nodes. Single-domain networks may contain noisy edges and they may lack some important information. Thus, some authors have proposed to consider the multiple relationships that connect the nodes of a network, thus obtaining multi-domain networks. However, most community detection approaches are limited to multi-layer networks, i.e. networks generated from the superposition of several single-domain networks (called layers) that are regarded as independent of each other. In addition to being computationally expensive, multi-layer approaches might yield inaccurate results because they ignore potential dependencies between layers. This paper proposes a multi-domain discrete-time quantum walks (MDQW) model for multi-domain networks. First, the walking space of network nodes in multi-domain network is constructed. Second, the quantum permutation circuit of the coin state is designed based on the coded particle state. Then, using different coin states, the shift operator performs several quantum walks on the particles. Finally, the corresponding update rule is selected to move the node according to the measurement result of the quantum state. With continuous update iteration, the shift operator automatically optimizes the discovered community structure. We experimentally compared our MDQW method with four state-of-the-art competitors on five real datasets. We used the normalized mutual information (NMI) to compare clustering quality, and we report an increase in NMI of up to 3.51 of our MDQW method in comparison with the second-best performing competitor. The MDQW method is much faster than its competitors, allowing us to conclude that MDQW is a useful tool in the analysis of large real-life multi-domain networks. Finally, we illustrate the usefulness of our approach on two real-world case studies.

DOI
10.1093/comjnl/bxae013

Related papers

Quantum Random Walk-Enhanced Framework for Social Network Analysis

Weronika Iga Halikowa, Norbert Głębocki

In this research, the computational efficiency of large-scale social network analysis is enhanced by the use of quantum random walk algorithms. The goal of this project is to address the need for high-efficiency centralized analysis of large-scale, heterogeneous social networks, community discovery, and dynamic effect mapping. In a theoretically sound framework of quantum random walks, amplitude superposition and unitary evolution principles have been used to improve both the sensitivity to local and global aspects. The solution uses real social network data with up to 5,000 nodes and more than 60,000 edges, and the testing results demonstrate its excellent scalability and fast convergence. Quantum algorithms have discovered community divisions and cut the mixing time by roughly 2.3 times after multiple optimizations. The performance indicators demonstrate that the above method has greatly improved key node detection accuracy and computation time as compared to the conventional baseline model in noisy situations. According to the aforementioned research, quantum-inspired algorithms have been used to expedite the analysis of large-scale data and reveal hidden structures that are challenging to identify using conventional techniques, such as bridge nodes and core-periphery distributions. The research assist data-driven choices in digital social ecosystems and lay the groundwork for in-depth network analysis.

Journal of Applied Automation Technologies•Sep 26, 2025•0 citations

A Method Inspired by One-Dimensional Discrete-Time Quantum Walks for Influential Node Identification

Wen Liang, Yifan Wang, Qiwei Liu +1 more

Identifying influential nodes in complex networks is essential for a wide range of applications, from social network analysis to enhancing infrastructure resilience. While quantum walk-based methods offer potential advantages, existing approaches face challenges in dimensionality, computational efficiency, and accuracy. To address these limitations, this study proposes a novel method inspired by the one-dimensional discrete-time quantum walk (IOQW). This design enables the development of a simplified shift operator that leverages both self-loops and the network's structural connectivity. Furthermore, degree centrality and path-based features are integrated into the coin operator, enhancing the accuracy and scalability of the IOQW framework. Comparative evaluations against state-of-the-art quantum and classical methods demonstrate that IOQW excels in capturing both local and global topological properties while maintaining a low computational complexity of O(N⟨k⟩), where ⟨k⟩ denotes the average degree. These advancements establish IOQW as a powerful and practical tool for influential node identification in complex networks, bridging quantum-inspired techniques with real-world network science applications.

Entropy•Jun 14, 2025•1 citation

EQDSC: Embedded Quantum Density-Based Spatial Clustering for Community Detection

Shuo He, Boxuan Ai, Pengfei Gao +3 more

Identifying community structures in complex networks is foundational to graph theory, but classical algorithms struggle with scalability and the "curse of dimensionality" in high-dimensional embedding, while existing quantum methods lack unified architectures or compatibility with practical hardware. Here we present Embedded Quantum Density-based Spatial Clustering (EQDSC), an end-to-end quantum framework for community detection with key theoretical and technical advances over state-of-the-art approaches: it integrates discrete-time quantum walks (DTQW) augmented with Grover diffusion operators for efficient topological feature extraction, and adopts quantum fidelity to quantify similarity—mitigating dimensionality issues inherently. We validated EQDSC on 11 real-world and synthetic datasets via Qiskit simulations. It achieved up to 0.855 modularity and 0.887 NMI (DBLP), outperforming classical methods by 18–35% on large networks. The achieved gains stem from quantum superposition and accelerated quantum walk diffusion, with small-dataset performance restricted by constrained parameter optimization. Simulated performance confirms practical applicability, laying the groundwork for future deployment on real NISQ devices.

IEEE Access•Jan 1, 2025•0 citations

A Quantum Approach to Walk on Networks

Anurag Kumar Singh, Binshumesh Sachan

Some interesting findings can be achieved by modeling and visualizing networks which can include complex networks and large scale networks to name a few. These networks have been analyzed with the help of classical stochastic walks before. So, here in our proposed work, we provide the quantum version of the walk which basically involves making use of properties found in quantum computing. These properties can include such as quantum interference, no-cloning theorem, and restriction on intermediate measurement. In this proposed work, we present quantum circuit designs for discrete time random walk algorithms that operate on various networks.To demonstrate our ideas we have considered two different types of networks, the star network and an extended version of the star network.Though there exist a few research works related to quantum approach for random walk on networks, to the best of our knowledge, the ideas and approach we present here are unique. These ideas which we have discussed can be extended to more complex networks and systems as well. As an application of quantum walk we have shown, how results got after performing quantum walk can be used to identify critical nodes in such networks. Therefore, we have also provided some analysis of complex networks. Identification of critical nodes is important for robustness and survivability of the network.

International Conference on Signal Processing, Computing and Control (ISPCC)•Oct 7, 2021•1 citation

Implementing quantum walks with a single qubit

Qi-Ping Su, Shi-Chao Wang, Yan Chi +5 more

Quantum walks have wide applications in quantum information, such as universal quantum computation, so it is important to explore properties of quantum walks thoroughly. We propose a novel method to implement discrete-time quantum walks (DTQWs) using only a single qubit, in which both coin and walker are encoded in the two-dimensional state space of a single qubit, operations are realized using single-qubit gates only, and high-dimensional final states of DTQWs can be obtained naturally. With this "one-qubit" approach, DTQW experiments can be realized much more easily, compared with previous methods, in most quantum systems and all properties based on quantum states of DTQWs (such as quantum correlation and coherence) can be investigated. By this approach, we experimentally implement one-particle and two-particle DTQWs with seven steps using single photons. Furthermore, we systematically investigate quantum correlations and coherence (based on the full state of the coin and walker) of the DTQW systems with different initial states of the coin, which have not been obtained and studied in DTQW experiments. As an application, we also study the assisted distillation of quantum coherence using the full state of the two-particle DTQW from the experiment. The maximal increase in distillable coherence for high-dimensional mixed states is investigated for the first time by obtaining its upper and lower bounds. Our work opens a new door to implement DTQW experiments and to better explore properties of quantum walks.

arXiv:2206.03642•Jun 8, 2022•1 citation

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•0 citations
Abstract The problem of detecting communities in real-world networks has been extensively studied in the past, but most of the existing approaches work on single-domain networks, i.e. they consider only one type of relationship between nodes. Single-domain networks may contain noisy edges and they may lack some important information. Thus, some authors have proposed to consider the multiple relationships that connect the nodes of a network, thus obtaining multi-domain networks. However, most community detection approaches are limited to multi-layer networks, i.e. networks generated from the superposition of several single-domain networks (called layers) that are regarded as independent of each other. In addition to being computationally expensive, multi-layer approaches might yield inaccurate results because they ignore potential dependencies between layers. This paper proposes a multi-domain discrete-time quantum walks (MDQW) model for multi-domain networks. First, the walking space of network nodes in multi-domain network is constructed. Second, the quantum permutation circuit of the coin state is designed based on the coded particle state. Then, using different coin states, the shift operator performs several quantum walks on the particles. Finally, the corresponding update rule is selected to move the node according to the measurement result of the quantum state. With continuous update iteration, the shift operator automatically optimizes the discovered community structure. We experimentally compared our MDQW method with four state-of-the-art competitors on five real datasets. We used the normalized mutual information (NMI) to compare clustering quality, and we report an increase in NMI of up to 3.51 of our MDQW method in comparison with the second-best performing competitor. The MDQW method is much faster than its competitors, allowing us to conclude that MDQW is a useful tool in the analysis of large real-life multi-domain networks. Finally, we illustrate the usefulness of our approach on two real-world case studies.
In this research, the computational efficiency of large-scale social network analysis is enhanced by the use of quantum random walk algorithms. The goal of this project is to address the need for high-efficiency centralized analysis of large-scale, heterogeneous social networks, community discovery, and dynamic effect mapping. In a theoretically sound framework of quantum random walks, amplitude superposition and unitary evolution principles have been used to improve both the sensitivity to local and global aspects. The solution uses real social network data with up to 5,000 nodes and more than 60,000 edges, and the testing results demonstrate its excellent scalability and fast convergence. Quantum algorithms have discovered community divisions and cut the mixing time by roughly 2.3 times after multiple optimizations. The performance indicators demonstrate that the above method has greatly improved key node detection accuracy and computation time as compared to the conventional baseline model in noisy situations. According to the aforementioned research, quantum-inspired algorithms have been used to expedite the analysis of large-scale data and reveal hidden structures that are challenging to identify using conventional techniques, such as bridge nodes and core-periphery distributions. The research assist data-driven choices in digital social ecosystems and lay the groundwork for in-depth network analysis.
Identifying influential nodes in complex networks is essential for a wide range of applications, from social network analysis to enhancing infrastructure resilience. While quantum walk-based methods offer potential advantages, existing approaches face challenges in dimensionality, computational efficiency, and accuracy. To address these limitations, this study proposes a novel method inspired by the one-dimensional discrete-time quantum walk (IOQW). This design enables the development of a simplified shift operator that leverages both self-loops and the network's structural connectivity. Furthermore, degree centrality and path-based features are integrated into the coin operator, enhancing the accuracy and scalability of the IOQW framework. Comparative evaluations against state-of-the-art quantum and classical methods demonstrate that IOQW excels in capturing both local and global topological properties while maintaining a low computational complexity of O(N⟨k⟩), where ⟨k⟩ denotes the average degree. These advancements establish IOQW as a powerful and practical tool for influential node identification in complex networks, bridging quantum-inspired techniques with real-world network science applications.
Identifying community structures in complex networks is foundational to graph theory, but classical algorithms struggle with scalability and the "curse of dimensionality" in high-dimensional embedding, while existing quantum methods lack unified architectures or compatibility with practical hardware. Here we present Embedded Quantum Density-based Spatial Clustering (EQDSC), an end-to-end quantum framework for community detection with key theoretical and technical advances over state-of-the-art approaches: it integrates discrete-time quantum walks (DTQW) augmented with Grover diffusion operators for efficient topological feature extraction, and adopts quantum fidelity to quantify similarity—mitigating dimensionality issues inherently. We validated EQDSC on 11 real-world and synthetic datasets via Qiskit simulations. It achieved up to 0.855 modularity and 0.887 NMI (DBLP), outperforming classical methods by 18–35% on large networks. The achieved gains stem from quantum superposition and accelerated quantum walk diffusion, with small-dataset performance restricted by constrained parameter optimization. Simulated performance confirms practical applicability, laying the groundwork for future deployment on real NISQ devices.
Some interesting findings can be achieved by modeling and visualizing networks which can include complex networks and large scale networks to name a few. These networks have been analyzed with the help of classical stochastic walks before. So, here in our proposed work, we provide the quantum version of the walk which basically involves making use of properties found in quantum computing. These properties can include such as quantum interference, no-cloning theorem, and restriction on intermediate measurement. In this proposed work, we present quantum circuit designs for discrete time random walk algorithms that operate on various networks.To demonstrate our ideas we have considered two different types of networks, the star network and an extended version of the star network.Though there exist a few research works related to quantum approach for random walk on networks, to the best of our knowledge, the ideas and approach we present here are unique. These ideas which we have discussed can be extended to more complex networks and systems as well. As an application of quantum walk we have shown, how results got after performing quantum walk can be used to identify critical nodes in such networks. Therefore, we have also provided some analysis of complex networks. Identification of critical nodes is important for robustness and survivability of the network.
Quantum walks have wide applications in quantum information, such as universal quantum computation, so it is important to explore properties of quantum walks thoroughly. We propose a novel method to implement discrete-time quantum walks (DTQWs) using only a single qubit, in which both coin and walker are encoded in the two-dimensional state space of a single qubit, operations are realized using single-qubit gates only, and high-dimensional final states of DTQWs can be obtained naturally. With this "one-qubit" approach, DTQW experiments can be realized much more easily, compared with previous methods, in most quantum systems and all properties based on quantum states of DTQWs (such as quantum correlation and coherence) can be investigated. By this approach, we experimentally implement one-particle and two-particle DTQWs with seven steps using single photons. Furthermore, we systematically investigate quantum correlations and coherence (based on the full state of the coin and walker) of the DTQW systems with different initial states of the coin, which have not been obtained and studied in DTQW experiments. As an application, we also study the assisted distillation of quantum coherence using the full state of the two-particle DTQW from the experiment. The maximal increase in distillable coherence for high-dimensional mixed states is investigated for the first time by obtaining its upper and lower bounds. Our work opens a new door to implement DTQW experiments and to better explore properties of quantum walks.
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.