论文标题
BILP-Q：量子联盟结构生成
BILP-Q: Quantum Coalition Structure Generation
论文作者
论文摘要
量子AI是一个新兴领域，它使用量子计算来解决AI中的典型复杂问题。在这项工作中，我们提出了BILP-Q，这是解决联盟结构生成问题（CSGP）的第一种通用量子方法，这是NP-HARD的明显。特别是，我们根据二进制二元组合优化（QUBO）问题对CSGP进行了重新重新制定，以利用现有的量子算法（例如QAOA）获得最佳的联盟结构。因此，我们对所提出的量子方法与最流行的古典基线之间的时间复杂性进行了比较分析。此外，我们考虑使用IBM Qiskit环境对联盟值的标准基准分布来测试小型实验的BILP-Q。最后，由于可以通过量子退火来解决QUBO问题，因此我们使用实际量子退火器（D-WAVE）在中型问题上运行BILP-Q。
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).
