arXiv:2410.07744 · IEEE Transactions on Network Science and Engineering
Modularity Maximization and Community Detection in Complex Networks Through Recursive and Hierarchical Annealing in the DWAVE Advantage Quantum Processing Units
Joan Falcó-Roget, Kacper Jurek, Barbara Wojtarowicz, Karol Capała, Katarzyna Rycerz
Quantum adiabatic optimization has long been expected to outperform classical methods in solving NP -type problems. While this has been proven in certain experiments, its main applications still reside in academic problems where the size of the system to be solved would not represent an obstacle to any modern desktop computer. Here, we develop a systematic procedure to find the global optima of the modularity function to discover community structure in complex networks solely relying on pure annealers rather than hybrid solutions. We bypass the one-hot encoding constraints by hierarchically and recursively encoding binary instances of the problem that can be solved without the need to guess the exact penalties for the Lagrange multipliers. We study the variability and robustness of the annealing process as a function of network size, directness of connections, topology, and the resolution of the communities. We show how our approach produces meaningful and at least equally optimal solutions to state-of-the-art community detection algorithms while maintaining tractable and potentially scalable computing times. Lastly, due to its recursive nature, the annealing process returns intermediate subdivisions, thus offering interpretable rather than black-box solutions. Thesedendrogramscan be used to unveil normal and pathological hidden hierarchies in brain networks, hence opening the door to clinical workflows. Overall, this represents a first step towards an applicable practice-oriented usage of pure quantum annealing, potentially bridging two segregated communities in modern science and engineering: that of network science and quantum computing.
Quantum adiabatic optimization has long been expected to outperform classical methods in solving NP -type problems. While this has been proven in certain experiments, its main applications still reside in academic problems where the size of the system to be solved would not represent an obstacle to any modern desktop computer. Here, we develop a systematic procedure to find the global optima of the modularity function to discover community structure in complex networks solely relying on pure annealers rather than hybrid solutions. We bypass the one-hot encoding constraints by hierarchically and recursively encoding binary instances of the problem that can be solved without the need to guess the exact penalties for the Lagrange multipliers. We study the variability and robustness of the annealing process as a function of network size, directness of connections, topology, and the resolution of the communities. We show how our approach produces meaningful and at least equally optimal solutions to state-of-the-art community detection algorithms while maintaining tractable and potentially scalable computing times. Lastly, due to its recursive nature, the annealing process returns intermediate subdivisions, thus offering interpretable rather than black-box solutions. Thesedendrogramscan be used to unveil normal and pathological hidden hierarchies in brain networks, hence opening the door to clinical workflows. Overall, this represents a first step towards an applicable practice-oriented usage of pure quantum annealing, potentially bridging two segregated communities in modern science and engineering: that of network science and quantum computing.
Recent advancements in network neuroscience are pointing in the direction of considering the brain as a small-world system with an efficient integration-segregation balance that facilitates different cognitive tasks and functions. In this context, community detection is a pivotal issue in computational neuroscience. In this paper we explored community detection within brain connectomes using the power of quantum annealers, and in particular the Leap's Hybrid Solver in D-Wave. By reframing the modularity optimization problem into a Discrete Quadratic Model, we show that quantum annealers achieved higher modularity indices compared to the Louvain Community Detection Algorithm without the need to overcomplicate the mathematical formulation. We also found that the number of communities detected in brain connectomes slightly differed while still being biologically interpretable. These promising preliminary results, together with recent findings, strengthen the claim that quantum optimization methods might be a suitable alternative against classical approaches when dealing with community assignment in networks.
Abstract Emerging quantum technologies represent a promising alternative for solving hard combinatorial problems in the post-Moore’s law era. For practical purposes, however, the current number of qubits limits the direct applicability to larger real-world instances in the near-term future. Therefore, a promising strategy to overcome this issue is represented by hybrid quantum classical algorithms which leverage classical as well as quantum devices. One prominent example of a hard computational problem is the community detection problem: a partition of a graph into distinct communities such that the ratio between intra-community and inter-community connectivity is maximized. In this paper, we explore the current potential of quantum annealing and gate-based quantum technologies to solve the community detection problem for an arbitrary number of communities. For this purpose, existing algorithms are (re-)implemented and new hybrid algorithms, that can be run on gate-model devices, are proposed. Their performance on standardized benchmark graphs has been evaluated and compared to the one of a state-of-the-art classical heuristic algorithm. Although no quantum speed-up has been achieved, the existing quantum annealing-based methods as well as the novel hybrid algorithms for gate-based quantum computers yield modularity values, which are similar to those of the classical heuristic. However, the modular architecture of the used algorithms allows for fast utilization of more powerful quantum technologies once they become available.Reproducibility:Our code and data are publicly available (Github in Quantum Modularization. https://github.com/jku-win se/quantum_modularization 2021).
Power grid partitioning is an important requirement for resilient distribution grids. Since electricity production is progressively shifted to the distribution side, dynamic identification of self-reliant grid subsets becomes crucial for operation. This problem can be represented as a modification to the well-known NP-hard Community Detection (CD) problem. We formulate it as a Quadratic Unconstrained Binary Optimization (QUBO) problem suitable for solving using quantum computation, which is expected to find better-quality partitions faster. The formulation aims to find communities with maximal self-sufficiency and minimal power flowing between them. To assess quantum optimization for sizeable problems, we develop a hierarchical divisive method that solves sub-problem QUBOs to perform grid bisections. Furthermore, we propose a customization of the Louvain heuristic that includes self-reliance. In the evaluation, we first demonstrate that this problem examines exponential runtime scaling classically. Then, using different IEEE power system test cases, we benchmark the solution quality for multiple approaches: D-Wave’s hybrid quantum-classical solvers, classical heuristics, and a branch-and-bound solver. As a result, we observe that the hybrid solvers provide very promising results, both with and without the divisive algorithm, regarding solution quality achieved within a given time frame. Directly utilizing D-Wave’s Quantum Annealing (QA) hardware shows inferior partitioning.
Quantum computing has emerged as a promising computational paradigm with the potential to solve problems that are intractable for classical computers. This paper provides an overview of the current state of quantum computing, including its historical development, hardware advancements, applications, and challenges. Special attention is given to combinatorial optimization, which is considered one of the most promising application domains. The limitations of current quantum systems and future research directions are also discussed. This paper presents a comparative study between a conventional D-Wave-based simulated annealing approach and a proposed hybrid optimization model for solving largescale combinatorial optimization problems. The study focuses on benchmark problems, including AES, TSP gr24, and a real-world load balancing problem, all formulated as QUBO models. The D-Wave approach employs the dwave-neal simulated annealing engine with various parameter settings, while the proposed model introduces a decomposition-based framework combined with adaptive parameter control and iterative refinement. The experimental results demonstrate that the proposed model consistently outperforms the conventional approach in terms of solution quality, achieving significantly lower energy values across all problem instances. In particular, for the TSP gr24 problem, the proposed model achieves near-optimal solutions with substantially reduced computation time. For large-scale problems such as AES and load balancing, the proposed model maintains scalability and robustness, whereas the conventional approach suffers from increased computational cost and performance degradation. Although the proposed method introduces additional computational steps, its hybrid structure effectively mitigates limitations related to local minima, parameter sensitivity, and scalability. These findings indicate that integrating classical optimization techniques with quantum-inspired methods is essential for practical applications. The proposed model provides a promising framework for solving complex real-world optimization problems and highlights the importance of hybrid approaches in advancing quantum annealing technologies.
Community detection, also known as graph partitioning, is a well-known NP-hard combinatorial optimization problem with applications in diverse fields such as complex network theory, transportation, and smart power grids. The problem's solution space grows drastically with the number of vertices and subgroups, making efficient algorithms crucial. In recent years, quantum computing has emerged as a promising approach to tackling NP-hard problems. This study explores the use of a quantum-inspired algorithm, Simulated Bifurcation (SB), for community detection. Modularity is employed as both the objective function and a metric to evaluate the solutions. The community detection problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, enabling seamless integration with the SB algorithm. Experimental results demonstrate that SB effectively identifies community structures in benchmark networks such as Zachary's Karate Club and the IEEE 33-bus system. Remarkably, SB achieved the highest modularity, matching the performance of Fujitsu's Digital Annealer, while surpassing results obtained from two quantum machines, D-Wave and IBM. These findings highlight the potential of Simulated Bifurcation as a powerful tool for solving community detection problems.
With the increase of intermittent renewable generation resources feeding into the electrical grid, Distribution System Operators (DSOs) must find ways to incorporate these new actors and adapt the grid to ensure stability and enable flexibility. Dividing the grid into logical clusters entails several organization and technical benefits, helping overcome these challenges.However, finding the optimal grid partitioning remains a challenging task due to its complexity. At the same time, a new technology has gained traction in the last decades for its promising speed-up potential in solving non-trivial combinatorial optimization problems: quantum computing. This work explores its application in Graph Partitioning using electrical modularity. We benchmarked several quantum annealing and hybrid methods on IEEE well-known test cases. The results obtained for the IEEE 14-bus test case show that quantum annealing DWaveSampler brings equal solutions or, for the optimal number partitions, a 1% improvement. For the more significant test cases, hybrid quantum annealing shows a relative error of less than 0.02% compared to the classical benchmark and for IEEE 118-bus test case shows time performance speed-up. The increment in performance would enable real time planning and operations of electrical grids in real time. This work intends to be the first step to showcase the potentials of quantum computing towards the modernization and adaption of electrical grids to the decentralized future of energy systems.