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

该研究提出了 BILP-Q，这是第一个解决合作联盟结构生成问题的通用量子方法。利用 QUBO 问题重新定义合作联盟结构生成问题，并通过比较分析量子方法和传统方法的时间复杂度，以及在 IBM Qiskit 环境中对标准联盟价值基准分布进行了小规模实验测试和在 D-Wave 上的中等规模问题的实现。