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).
翻译:量子计算是一个新兴领域,它使用量子计算来解决AI 中典型的复杂问题。 在这项工作中,我们建议采用BILP-Q(BILP-Q)(BILP-Q ), 这是解决联合结构生成问题的首个通用量子方法(CSGP ), 主要是NP- 硬的。 特别是,我们重新配置了CSGP(CSGP), 以“ 二次二次组合组合优化” (QUBO) 问题为例, 以利用现有量子算法(例如QAOA) 获得最佳联合结构。 因此, 我们从拟议量子法和最受欢迎的古典基线之间的时间复杂性角度进行了比较分析。 此外,我们考虑使用IBM Qiskit 环境测试BIILP-Q 小规模实验的联盟值标准基准分布。 最后,由于QUBO问题可以用量子射线操作解决,我们使用实际量子射器(D-Weve)在中等规模问题上运行 BILP-Q。