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:2408.04366 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Towards Less Greedy Quantum Coalition Structure Generation in Induced Subgraph Games

Jonas Nüβlein, Daniëlle Schuman, David Bucher, Naeimeh Mohseni, Kumar Ghosh, Corey O’Meara, G. Cortiana, Claudia Linnhoff–Popien

Published Sep 15, 2024• 1 citation
arXivHTMLPDF

Abstract

The transition to 100% renewable energy requires new techniques for managing energy networks, such as dividing them into sensible subsets of prosumers called micro-grids. Doing so in an optimal manner is a difficult optimization problem, as it can be abstracted to the Coalition Structure Generation problem in Induced Subgraph Games, a NP-complete problem which requires dividing an undirected, complete, weighted graph into subgraphs in a way that maximizes the sum of their internal weights. Recently, Venkatesh et al. [1] published a Quantum Annealing (QA)-based iterative algorithm called GCS-Q, which they claim to be the best currently existing solver for the problem in terms of runtime complexity. As this algorithm makes the application of QA to the problem seem promising, but is a greedy one, this work proposes several less greedy QA-based approaches and investigates whether any of them can outperform GCS-Q in terms of solution quality. While we find that this is not the case yet on D-Wave hardware, most of them do when using the classical QBSolv software as a solver. Especially an algorithm we call 4-split iterative R-QUBO shows potential here, finding all optima in our dataset while scaling favorably with the problem size in terms of runtime. Thus, it appears to be interesting for future research on quantum approaches to the problem, assuming QA hardware will become more noise-resilient over time.

DOI
10.1109/qce60285.2024.10247

Related papers

QuACS

Supreeth Mysore Venkatesh, Antonio Macaluso, Matthias Klusch

Coalition Structure Generation (CSG) is an NP-Hard problem in which agents are partitioned into mutually exclusive groups to maximize their social welfare. In this work, we propose QuACS, a novel hybrid quantum-classical algorithm for Coalition Structure Generation in Induced Subgraph Games (ISGs). Starting from a coalition structure where all the agents belong to a single coalition, QuACS recursively identifies the optimal partition into two disjoint subsets. This problem is reformulated as a QUBO and then solved using QAOA. Given an n-agent ISG, we show that the proposed algorithm outperforms existing approximate classical solvers with a runtime of O(n2) and an expected approximation ratio of 92%. Furthermore, it requires a significantly lower number of qubits and allows experiments on medium-sized problems compared to existing quantum solutions. To show the effectiveness of QuACS we perform experiments on standard benchmark datasets using quantum simulation.

arXiv:2304.07218•ACM International Conference on Computing Frontiers (CF)•May 9, 2023•8 citations

Evidence of quantum scaling advantage in approximate optimization for energy coalition formation with 100+ agents

Naeimeh Mohseni, Thomas Morstyn, Corey O’Meara +3 more

Abstract The formation of energy communities is pivotal for advancing decentralized and sustainable energy management. Within this context, coalition structure generation (CSG) emerges as a promising framework. The complexity of CSG grows rapidly with the number of agents, making classical solvers impractical for even moderate sizes. This suggests CSG as an ideal candidate for benchmarking quantum algorithms against classical ones. Facing ongoing challenges in attaining computational quantum advantage for exact optimization, we pivot our focus to benchmarking quantum and classical solvers for approximate optimization. Approximate optimization is particularly critical for industrial use cases requiring real-time optimization, where finding high-quality solutions quickly is often more valuable than achieving exact solutions more slowly. Our findings indicate that quantum annealing (QA) on DWave can achieve solutions of comparable quality to our best classical solver, but with more favorable runtime scaling, showcasing an advantage. This advantage is observed when compared to solvers, such as Tabu search, simulated annealing, and the state-of-the-art solver Gurobi in finding approximate solutions for energy community formation involving over 100 agents. DWave also surpasses 1-round QAOA on IBM hardware. Our findings represent the largest benchmark of quantum approximate optimizations for a real-world dense model beyond the hardware’s native topology, where D-Wave demonstrates a scaling advantage.

Quantum Science and Technology•Nov 6, 2025•1 citation

Demonstrating Quantum Scaling Advantage in Approximate Optimization for Energy Coalition Formation with 100+ Agents

Naeimeh Mohseni, Thomas Morstyn, Corey O’Meara +3 more

The formation of energy communities is pivotal for advancing decentralized and sustainable energy management. Within this context, Coalition Structure Generation (CSG) emerges as a promising framework. The complexity of CSG grows rapidly with the number of agents, making classical solvers impractical for even moderate sizes. This suggests CSG as an ideal candidate for benchmarking quantum algorithms against classical ones. Facing ongoing challenges in attaining computational quantum advantage for exact optimization, we pivot our focus to benchmarking quantum and classical solvers for approximate optimization. Approximate optimization is particularly critical for industrial use cases requiring real-time optimization, where finding high-quality solutions quickly is often more valuable than achieving exact solutions more slowly. Our findings indicate that quantum annealing (QA) on DWave can achieve solutions of comparable quality to our best classical solver, but with more favorable runtime scaling, showcasing an advantage. This advantage is observed when compared to solvers, such as Tabu search, simulated annealing, and the state-of-the-art solver Gurobi, in finding approximate solutions for energy community formation involving over 100 agents. DWave also surpasses 1-round QAOA on IBM hardware. Our findings represent the largest benchmark of quantum approximate optimizations for a real-world dense model beyond the hardware's native topology, where D-Wave demonstrates a scaling advantage.

arXiv:2405.11917•May 20, 2024•0 citations

Quantum Annealing based Power Grid Partitioning for Parallel Simulation

Hartmann, Carsten, Zhang, Junjie, Carlos D. Gonzalez Calaza +3 more

Graph partitioning has many applications in powersystems from decentralized state estimation to parallel simulation. Focusing on parallel simulation, optimal grid partitioning minimizes the idle time caused by different simulation times for the sub-networks and their components and reduces the overhead required to simulate the cuts. Partitioning a graph into two parts such that, for example, the cut is minimal and the subgraphs have equal size is an NP-hard problem. In this paper we show how optimal partitioning of a graph can be obtained using quantum annealing (QA). We show how to map the requirements for optimal splitting to a quadratic unconstrained binary optimization (QUBO) formulation and test the proposed formulation using a current D-Wave QPU. We show that the necessity to find an embedding of the QUBO on current D-Wave QPUs limits the problem size to under 200 buses and notably affects the time-to-solution. We finally discuss the implications on near-term implementation of QA in combination to traditional CPU or GPU based simulation.

arXiv:2408.04097•Aug 7, 2024•0 citations

BILP-Q: Quantum Coalition Structure Generation

Supreeth Mysore Venkatesh, Antonio Macaluso, Matthias Klusch

Quantum AI is an emerging field that uses quantum computing to solve typical complex problems in AI. In this work, we propose BILP-Q, the first-ever general quantum approach for solving the Coalition Structure Generation problem (CSGP), which is notably NP-hard. In particular, we reformulate the CSGP in terms of a Quadratic Binary Combinatorial Optimization (QUBO) problem to leverage existing quantum algorithms (e.g., QAOA) to obtain the best coalition structure. Thus, we perform a comparative analysis in terms of time complexity between the proposed quantum approach and the most popular classical baselines. Furthermore, we consider standard benchmark distributions for coalition values to test the BILP-Q on small-scale experiments using the IBM Qiskit environment. Finally, since QUBO problems can be solved operating with quantum annealing, we run BILP-Q on medium-size problems using a real quantum annealer (D-Wave).

arXiv:2204.13802•Apr 28, 2022•2 citations

Quantum Annealing-Based Algorithm for Efficient Coalition Formation Among LEO Satellites

Supreeth Mysore Venkatesh, Antonio Macaluso, Marlon Nuske +2 more

The increasing number of Low Earth Orbit (LEO) satellites, driven by lower manufacturing and launch costs, is proving invaluable for Earth observation missions and low-latency internet connectivity. However, as the number of satellites increases, the number of communication links to maintain also rises, making the management of this vast network increasingly challenging and highlighting the need for clustering satellites into efficient groups as a promising solution. This paper formulates the clustering of LEO satellites as a coalition structure generation (CSG) problem and leverages quantum annealing to solve it. We represent the satellite network as a graph and obtain the optimal partitions using a hybrid quantum-classical algorithm called GCS-Q. The algorithm follows a top-down approach by iteratively splitting the graph at each step using a quadratic unconstrained binary optimization (QUBO) formulation. To evaluate our approach, we utilize real-world three-line element set (TLE/3LE) data for Starlink satellites from Celestrak. Our experiments, conducted using the D-Wave Advantage annealer and the state-of-the-art solver Gurobi, demonstrate that the quantum annealer significantly outperforms classical methods in terms of runtime while maintaining the solution quality. The performance achieved with quantum annealers surpasses the capabilities of classical computers, highlighting the transformative potential of quantum computing in optimizing the management of large-scale satellite networks.

arXiv:2408.06007•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•7 citations
The transition to 100% renewable energy requires new techniques for managing energy networks, such as dividing them into sensible subsets of prosumers called micro-grids. Doing so in an optimal manner is a difficult optimization problem, as it can be abstracted to the Coalition Structure Generation problem in Induced Subgraph Games, a NP-complete problem which requires dividing an undirected, complete, weighted graph into subgraphs in a way that maximizes the sum of their internal weights. Recently, Venkatesh et al. [1] published a Quantum Annealing (QA)-based iterative algorithm called GCS-Q, which they claim to be the best currently existing solver for the problem in terms of runtime complexity. As this algorithm makes the application of QA to the problem seem promising, but is a greedy one, this work proposes several less greedy QA-based approaches and investigates whether any of them can outperform GCS-Q in terms of solution quality. While we find that this is not the case yet on D-Wave hardware, most of them do when using the classical QBSolv software as a solver. Especially an algorithm we call 4-split iterative R-QUBO shows potential here, finding all optima in our dataset while scaling favorably with the problem size in terms of runtime. Thus, it appears to be interesting for future research on quantum approaches to the problem, assuming QA hardware will become more noise-resilient over time.
Coalition Structure Generation (CSG) is an NP-Hard problem in which agents are partitioned into mutually exclusive groups to maximize their social welfare. In this work, we propose QuACS, a novel hybrid quantum-classical algorithm for Coalition Structure Generation in Induced Subgraph Games (ISGs). Starting from a coalition structure where all the agents belong to a single coalition, QuACS recursively identifies the optimal partition into two disjoint subsets. This problem is reformulated as a QUBO and then solved using QAOA. Given an n-agent ISG, we show that the proposed algorithm outperforms existing approximate classical solvers with a runtime of O(n2) and an expected approximation ratio of 92%. Furthermore, it requires a significantly lower number of qubits and allows experiments on medium-sized problems compared to existing quantum solutions. To show the effectiveness of QuACS we perform experiments on standard benchmark datasets using quantum simulation.
Abstract The formation of energy communities is pivotal for advancing decentralized and sustainable energy management. Within this context, coalition structure generation (CSG) emerges as a promising framework. The complexity of CSG grows rapidly with the number of agents, making classical solvers impractical for even moderate sizes. This suggests CSG as an ideal candidate for benchmarking quantum algorithms against classical ones. Facing ongoing challenges in attaining computational quantum advantage for exact optimization, we pivot our focus to benchmarking quantum and classical solvers for approximate optimization. Approximate optimization is particularly critical for industrial use cases requiring real-time optimization, where finding high-quality solutions quickly is often more valuable than achieving exact solutions more slowly. Our findings indicate that quantum annealing (QA) on DWave can achieve solutions of comparable quality to our best classical solver, but with more favorable runtime scaling, showcasing an advantage. This advantage is observed when compared to solvers, such as Tabu search, simulated annealing, and the state-of-the-art solver Gurobi in finding approximate solutions for energy community formation involving over 100 agents. DWave also surpasses 1-round QAOA on IBM hardware. Our findings represent the largest benchmark of quantum approximate optimizations for a real-world dense model beyond the hardware’s native topology, where D-Wave demonstrates a scaling advantage.
The formation of energy communities is pivotal for advancing decentralized and sustainable energy management. Within this context, Coalition Structure Generation (CSG) emerges as a promising framework. The complexity of CSG grows rapidly with the number of agents, making classical solvers impractical for even moderate sizes. This suggests CSG as an ideal candidate for benchmarking quantum algorithms against classical ones. Facing ongoing challenges in attaining computational quantum advantage for exact optimization, we pivot our focus to benchmarking quantum and classical solvers for approximate optimization. Approximate optimization is particularly critical for industrial use cases requiring real-time optimization, where finding high-quality solutions quickly is often more valuable than achieving exact solutions more slowly. Our findings indicate that quantum annealing (QA) on DWave can achieve solutions of comparable quality to our best classical solver, but with more favorable runtime scaling, showcasing an advantage. This advantage is observed when compared to solvers, such as Tabu search, simulated annealing, and the state-of-the-art solver Gurobi, in finding approximate solutions for energy community formation involving over 100 agents. DWave also surpasses 1-round QAOA on IBM hardware. Our findings represent the largest benchmark of quantum approximate optimizations for a real-world dense model beyond the hardware's native topology, where D-Wave demonstrates a scaling advantage.
Graph partitioning has many applications in powersystems from decentralized state estimation to parallel simulation. Focusing on parallel simulation, optimal grid partitioning minimizes the idle time caused by different simulation times for the sub-networks and their components and reduces the overhead required to simulate the cuts. Partitioning a graph into two parts such that, for example, the cut is minimal and the subgraphs have equal size is an NP-hard problem. In this paper we show how optimal partitioning of a graph can be obtained using quantum annealing (QA). We show how to map the requirements for optimal splitting to a quadratic unconstrained binary optimization (QUBO) formulation and test the proposed formulation using a current D-Wave QPU. We show that the necessity to find an embedding of the QUBO on current D-Wave QPUs limits the problem size to under 200 buses and notably affects the time-to-solution. We finally discuss the implications on near-term implementation of QA in combination to traditional CPU or GPU based simulation.
Quantum AI is an emerging field that uses quantum computing to solve typical complex problems in AI. In this work, we propose BILP-Q, the first-ever general quantum approach for solving the Coalition Structure Generation problem (CSGP), which is notably NP-hard. In particular, we reformulate the CSGP in terms of a Quadratic Binary Combinatorial Optimization (QUBO) problem to leverage existing quantum algorithms (e.g., QAOA) to obtain the best coalition structure. Thus, we perform a comparative analysis in terms of time complexity between the proposed quantum approach and the most popular classical baselines. Furthermore, we consider standard benchmark distributions for coalition values to test the BILP-Q on small-scale experiments using the IBM Qiskit environment. Finally, since QUBO problems can be solved operating with quantum annealing, we run BILP-Q on medium-size problems using a real quantum annealer (D-Wave).
The increasing number of Low Earth Orbit (LEO) satellites, driven by lower manufacturing and launch costs, is proving invaluable for Earth observation missions and low-latency internet connectivity. However, as the number of satellites increases, the number of communication links to maintain also rises, making the management of this vast network increasingly challenging and highlighting the need for clustering satellites into efficient groups as a promising solution. This paper formulates the clustering of LEO satellites as a coalition structure generation (CSG) problem and leverages quantum annealing to solve it. We represent the satellite network as a graph and obtain the optimal partitions using a hybrid quantum-classical algorithm called GCS-Q. The algorithm follows a top-down approach by iteratively splitting the graph at each step using a quadratic unconstrained binary optimization (QUBO) formulation. To evaluate our approach, we utilize real-world three-line element set (TLE/3LE) data for Starlink satellites from Celestrak. Our experiments, conducted using the D-Wave Advantage annealer and the state-of-the-art solver Gurobi, demonstrate that the quantum annealer significantly outperforms classical methods in terms of runtime while maintaining the solution quality. The performance achieved with quantum annealers surpasses the capabilities of classical computers, highlighting the transformative potential of quantum computing in optimizing the management of large-scale satellite networks.