# BILP-Q: Quantum Coalition Structure Generation

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 18 references that are in the map.
- First posted on arXiv 28 Apr 2022.

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

- [Game Theory for Multi-Access Edge Computing: Survey, Use Cases, and Future Trends](https://mlsanity.com/paper/1704.00323/) (2017)
- [Optimizing Ansatz Design in QAOA for Max-cut](https://mlsanity.com/paper/2106.02812/) (2021)
- [Algorithms for Graph-Constrained Coalition Formation in the Real World](https://mlsanity.com/paper/1612.04299/) (2016)

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

- [Q-Seg: Quantum Annealing-Based Unsupervised Image Segmentation](https://mlsanity.com/paper/2311.12912/) (2023)
- [GCS-Q: Quantum Graph Coalition Structure Generation](https://mlsanity.com/paper/2212.11372/) (2022)
- [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)

## Abstract (arXiv)

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