# QuACS: Variational Quantum Algorithm for Coalition Structure Generation in Induced Subgraph Games

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2023.

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

- [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)

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.