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

Entropy

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

Wen Liang, Hequn LI, Guangqi Liu, Wenbo Zhang

Published Jun 14, 2025• 1 citation
Publisher

Abstract

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.

DOI
10.3390/e27060634

Related papers

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

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

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

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

Xiaoyang Liu, Nan Ding, Yudie Wu +2 more

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.

The Computer Journal•Feb 8, 2024•4 citations

Coined Quantum Walks on Complex Networks for Quantum Computers

Rei Sato

We propose a quantum circuit design for implementing coined quantum walks on complex networks. In complex networks, the coin and shift operators depend on the varying degrees of the nodes, which makes circuit construction more challenging than for regular networks. To address this issue, we use a dual-register encoding to enable a simplified shift operator and reduces the resource overhead. We implement the circuit using Qmod, a high-level quantum programming language, and evaluated the performance through numerical simulations on Erdős-Rényi, Watts-Strogatz, and Barabási-Albert models. The results show that the circuit depth scales as approximately $N^{1.9}$ regardless of the network topology. Furthermore, we execute the proposed circuits on the ibm\_torino superconducting quantum processor for Watts-Strogatz models with $N=4$ and $N=8$. The experiments show that hardware-aware optimization slightly improved the variation distance and Hellinger fidelity for the larger network, whereas connectivity constraints imposed overhead for the smaller one. These results indicate that while current NISQ devices are limited to small-scale validations, the polynomial scaling of our framework makes it suitable for larger-scale implementations in the fault-tolerant quantum computing era.

quant-pharXiv:2512.16400•Quantum Information Processing•Dec 19, 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
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.
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.
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.
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.
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.
We propose a quantum circuit design for implementing coined quantum walks on complex networks. In complex networks, the coin and shift operators depend on the varying degrees of the nodes, which makes circuit construction more challenging than for regular networks. To address this issue, we use a dual-register encoding to enable a simplified shift operator and reduces the resource overhead. We implement the circuit using Qmod, a high-level quantum programming language, and evaluated the performance through numerical simulations on Erdős-Rényi, Watts-Strogatz, and Barabási-Albert models. The results show that the circuit depth scales as approximately N1.9N^{1.9}N1.9 regardless of the network topology. Furthermore, we execute the proposed circuits on the ibm\_torino superconducting quantum processor for Watts-Strogatz models with N=4N=4N=4 and N=8N=8N=8. The experiments show that hardware-aware optimization slightly improved the variation distance and Hellinger fidelity for the larger network, whereas connectivity constraints imposed overhead for the smaller one. These results indicate that while current NISQ devices are limited to small-scale validations, the polynomial scaling of our framework makes it suitable for larger-scale implementations in the fault-tolerant quantum computing era.
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.