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

arXiv:2501.00075

Community detection by simulated bifurcation

Wei Li, Yi-Lun Du, Nan Su, Konrad Tywoniuk, Kyle Godbey, Horst Stöcker B

Published Dec 30, 2024• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2501.00075

Related papers

Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection

David Bucher, Daniel Porawski, Benedikt Wimmer +5 more

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.

arXiv:2407.06773•IEEE Transactions on Smart Grid•Oct 18, 2024•10 citations

Scalable Community Detection Using Quantum Hamiltonian Descent and QUBO Formulation

Jinglei Cheng, Ruilin Zhou, Yuhang Gan +2 more

We present a quantum-inspired algorithm that utilizes Quantum Hamiltonian Descent (QHD) for efficient community detection. Our approach reformulates the community detection task as a Quadratic Unconstrained Binary Optimization (QUBO) problem, and QHD is deployed to identify optimal community structures. We implement a multi-level algorithm that iteratively refines community assignments by alternating between QUBO problem setup and QHD-based optimization. Benchmarking shows our method achieves up to 5.49% better modularity scores while requiring less computational time compared to classical optimization approaches. This work demonstrates the potential of hybrid quantum-inspired solutions for advancing community detection in largescale graph data.

arXiv:2411.14696•ACM/IEEE Design Automation Conference (DAC)•Jun 22, 2025•1 citation

Graph Partitioning with Fujitsu Digital Annealer

Yu-Ting Kao, Hsiu-Chuan Hsu

Graph partitioning, or community detection, is the cornerstone of many fields, such as logistics, transportation and smart power grids. Efficient computation and efficacious evaluation of communities are both essential, especially in commercial and industrial settings. However, the solution space of graph partitioning increases drastically with the number of vertices and subgroups. With an eye to solving large scale graph partitioning and other optimization problems within a short period of time, the Digital Annealer (DA), a specialized CMOS hardware also featuring improved algorithms, has been devised by Fujitsu Ltd. This study gauges Fujitsu DA's performance and running times. The modularity was implemented as both the objective function and metric for the solutions. The graph partitioning problems were formatted into Quadratic Unconstrained Binary Optimization (QUBO) structures so that they could be adequately imported into the DA. The DA yielded the highest modularity among other studies when partitioning Karate Club, Les Miserables, American Football, and Dolphin. Moreover, the DA was able to partition the Case 1354pegase power grid network into 45 subgroups, calling for 60,930 binary variables, whilst delivering optimal modularity results within a solving time of roughly 80 seconds. Our results suggest that the Fujitsu DA can be applied for rapid and efficient optimization for graph partitioning.

arXiv:2311.16559•Nov 28, 2023•0 citations

Solving Combinatorial Optimization Problems on Fujitsu Digital Annealer

Yu-Ting Kao, Jia-Le Liao, Hsiu-Chuan Hsu

Combinatorial optimization problems are ubiquitous in various disciplines and applications. Many heuristic algorithms have been devoted to solve these types of problems. In order to increase the efficiency for finding the optimal solutions, an application-specific hardware, called digital annealer (DA) has been developed for solving combinatorial optimization problems using quadratic unconstrained binary optimization (QUBO) formulations. In this study, we formulated the number partitioning problem and the graph partitioning problem into QUBO forms and solved such problems with the DA developed by Fujitsu Ltd. The QUBO formulation of the number partitioning problem is fully connected. The DA found the overall runtime for the optimal solution to be less than 30 seconds for 6500 binary variables. For the graph partitioning problem, we adopted modularity as the metric for determining the quality of the partitions. For Zachary's Karate Club graph, the modularity obtained was 0.445, a 6% increase against D-wave Quantum Annealer and Simulated Annealing. Moreover, to explore the DA's potential applications to real-world problems, we used the search for communities or virtual microgrids in a power distribution network as an example. The problem was formulated into graph partitioning. It is shown that the DA effectively identified community structures in the IEEE 33-bus and IEEE 118-bus network.

arXiv:2311.05196•Nov 9, 2023•2 citations

Community Detection in Electrical Grids Using Quantum Annealing

Marina Fernández-Campoamor, Corey O’Meara, G. Cortiana +2 more

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.

arXiv:2112.08300•Dec 15, 2021•10 citations

Quantum-Inspired optimization algorithms: Bridging classical computation and quantum principles for complex problem solving

Kuldoshjon Juraev, Bobir Zokirov, Madina Kholikova +2 more

This study explores quantum-inspired optimization algorithms (QIOAs) as practical tools for solving constrained combinatorial problems on classical machines. We analyze tasks that can be formulated in Ising or QUBO forms and benchmark three representative approaches: Simulated Bifurcation (SB), Quantum-Inspired Particle Swarm Optimization (QPSO), and a tensor-network (TN) method. A unified evaluation protocol is introduced that captures solution quality, feasibility, runtime, energy consumption, parameter sensitivity, and scalability. To ensure reliable performance, we develop automated penalty-adjustment and schedule-calibration strategies. Experimental results across diverse benchmarks show that SB and TN together yield the best trade-offs between accuracy and runtime: SB is efficient on dense instances with moderate penalties and low energy use, while TN is advantageous for sparse or modular networks, especially on GPUs. QPSO is competitive in smoother landscapes but more sensitive to hyperparameters. By linking performance to structural properties such as spectral gaps and constraint activity, we provide guidance for selecting suitable algorithms. Overall, QIOAs emerge as effective intermediaries between existing classical heuristics and emerging quantum devices, supported by a reproducible, energy-aware evaluation framework.

AIP conference proceedings•Jan 1, 2026•0 citations
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.
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.
We present a quantum-inspired algorithm that utilizes Quantum Hamiltonian Descent (QHD) for efficient community detection. Our approach reformulates the community detection task as a Quadratic Unconstrained Binary Optimization (QUBO) problem, and QHD is deployed to identify optimal community structures. We implement a multi-level algorithm that iteratively refines community assignments by alternating between QUBO problem setup and QHD-based optimization. Benchmarking shows our method achieves up to 5.49% better modularity scores while requiring less computational time compared to classical optimization approaches. This work demonstrates the potential of hybrid quantum-inspired solutions for advancing community detection in largescale graph data.
Graph partitioning, or community detection, is the cornerstone of many fields, such as logistics, transportation and smart power grids. Efficient computation and efficacious evaluation of communities are both essential, especially in commercial and industrial settings. However, the solution space of graph partitioning increases drastically with the number of vertices and subgroups. With an eye to solving large scale graph partitioning and other optimization problems within a short period of time, the Digital Annealer (DA), a specialized CMOS hardware also featuring improved algorithms, has been devised by Fujitsu Ltd. This study gauges Fujitsu DA's performance and running times. The modularity was implemented as both the objective function and metric for the solutions. The graph partitioning problems were formatted into Quadratic Unconstrained Binary Optimization (QUBO) structures so that they could be adequately imported into the DA. The DA yielded the highest modularity among other studies when partitioning Karate Club, Les Miserables, American Football, and Dolphin. Moreover, the DA was able to partition the Case 1354pegase power grid network into 45 subgroups, calling for 60,930 binary variables, whilst delivering optimal modularity results within a solving time of roughly 80 seconds. Our results suggest that the Fujitsu DA can be applied for rapid and efficient optimization for graph partitioning.
Combinatorial optimization problems are ubiquitous in various disciplines and applications. Many heuristic algorithms have been devoted to solve these types of problems. In order to increase the efficiency for finding the optimal solutions, an application-specific hardware, called digital annealer (DA) has been developed for solving combinatorial optimization problems using quadratic unconstrained binary optimization (QUBO) formulations. In this study, we formulated the number partitioning problem and the graph partitioning problem into QUBO forms and solved such problems with the DA developed by Fujitsu Ltd. The QUBO formulation of the number partitioning problem is fully connected. The DA found the overall runtime for the optimal solution to be less than 30 seconds for 6500 binary variables. For the graph partitioning problem, we adopted modularity as the metric for determining the quality of the partitions. For Zachary's Karate Club graph, the modularity obtained was 0.445, a 6% increase against D-wave Quantum Annealer and Simulated Annealing. Moreover, to explore the DA's potential applications to real-world problems, we used the search for communities or virtual microgrids in a power distribution network as an example. The problem was formulated into graph partitioning. It is shown that the DA effectively identified community structures in the IEEE 33-bus and IEEE 118-bus network.
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.
This study explores quantum-inspired optimization algorithms (QIOAs) as practical tools for solving constrained combinatorial problems on classical machines. We analyze tasks that can be formulated in Ising or QUBO forms and benchmark three representative approaches: Simulated Bifurcation (SB), Quantum-Inspired Particle Swarm Optimization (QPSO), and a tensor-network (TN) method. A unified evaluation protocol is introduced that captures solution quality, feasibility, runtime, energy consumption, parameter sensitivity, and scalability. To ensure reliable performance, we develop automated penalty-adjustment and schedule-calibration strategies. Experimental results across diverse benchmarks show that SB and TN together yield the best trade-offs between accuracy and runtime: SB is efficient on dense instances with moderate penalties and low energy use, while TN is advantageous for sparse or modular networks, especially on GPUs. QPSO is competitive in smoother landscapes but more sensitive to hyperparameters. By linking performance to structural properties such as spectral gaps and constraint activity, we provide guidance for selecting suitable algorithms. Overall, QIOAs emerge as effective intermediaries between existing classical heuristics and emerging quantum devices, supported by a reproducible, energy-aware evaluation framework.