BILP-Q: Quantum Coalition Structure Generation
This work addresses a complex AI problem for researchers in quantum computing and multi-agent systems, but it is incremental as it applies existing quantum methods to a new domain.
The authors tackled the NP-hard Coalition Structure Generation problem by proposing BILP-Q, the first general quantum approach, which reformulates it as a QUBO problem and leverages quantum algorithms like QAOA and quantum annealing, achieving comparative time complexity analysis and testing on small-scale and medium-size problems using IBM Qiskit and D-Wave environments.
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).