期刊
出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3528416.3530235
关键词
Quantum AI; Quantum Computing; Coalition Game Theory
资金
- German Ministry for Education and Research (BMB+F) [QAI2-QAICO, 13N15586]
This paper proposes a new quantum method, BILP-Q, for solving the Coalition Structure Generation problem. By reformulating the problem as a Quadratic Binary Combinatorial Optimization problem and leveraging existing quantum algorithms, the best coalition structure can be obtained. Comparative analysis on time complexity is conducted between the proposed quantum approach and classical methods. Small-scale experiments using IBM Qiskit and medium-scale problems on a real quantum annealer (D-Wave) are also performed.
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).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据