# GCS-Q: Quantum Graph Coalition Structure Generation

arXiv: https://arxiv.org/abs/2212.11372 · HTML: https://mlsanity.com/paper/2212.11372/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 20 references that are in the map.
- First posted on arXiv 21 Dec 2022.

## Builds on (most cited first, 3 of 3)

- [On the Emerging Potential of Quantum Annealing Hardware for Combinatorial Optimization](https://mlsanity.com/paper/2210.04291/) (2022)
- [BILP-Q: Quantum Coalition Structure Generation](https://mlsanity.com/paper/2204.13802/) (2022)
- [Coalition Structure Generation over Graphs](https://mlsanity.com/paper/1401.6428/) (2014)

## Built on by (most cited first, 8 of 8)

- [Q-Seg: Quantum Annealing-Based Unsupervised Image Segmentation](https://mlsanity.com/paper/2311.12912/) (2023)
- [Qubit-efficient Variational Quantum Algorithms for Image Segmentation](https://mlsanity.com/paper/2405.14405/) (2024)
- [Enabling Non-Linear Quantum Operations through Variational Quantum Splines](https://mlsanity.com/paper/2303.04788/) (2023)
- [MAQA: A Quantum Framework for Supervised Learning](https://mlsanity.com/paper/2303.11028/) (2023)
- [Quantum Artificial Intelligence: A Brief Survey](https://mlsanity.com/paper/2408.10726/) (2024)
- [QAL-BP: An Augmented Lagrangian Quantum Approach for Bin Packing](https://mlsanity.com/paper/2309.12678/) (2023)
- [Toward Quantum Utility in Finance: A Robust Data-Driven Algorithm for Asset Clustering](https://mlsanity.com/paper/2509.07766/) (2025)
- [Quantum-Assisted Correlation Clustering](https://mlsanity.com/paper/2509.03561/) (2025)

## Abstract (arXiv)

The problem of generating an optimal coalition structure for a given coalition game of rational agents is to find a partition that maximizes their social welfare and is known to be NP-hard. This paper proposes GCS-Q, a novel quantum-supported solution for Induced Subgraph Games (ISGs) in coalition structure generation. GCS-Q starts by considering the grand coalition as initial coalition structure and proceeds by iteratively splitting the coalitions into two nonempty subsets to obtain a coalition structure with a higher coalition value. In particular, given an n-agent ISG, the GCS-Q solves the optimal split problem O (n) times using a quantum annealing device, exploring O(2n) partitions at each step. We show that GCS-Q outperforms the currently best classical solvers with its runtime in the order of n2 and an expected worst-case approximation ratio of 93% on standard benchmark datasets.