全新电路网络系统可以实现快速求解双人零和博弈问题 求解速度超过传统经典博弈算法

北京理工大学张向东教授的团队了提出并实现了一种全新的电路网络系统，证明可以实现快速求解双人零和博弈问题，其求解速度超过了传统经典博弈算法。相关成果以“Quantum Two-Player Games and Realizations with Circuits”为题发表在Research上（Research 2024; 7: Article 0480. https://doi.org/10.34133/research.0480）。

研究背景

博弈论问题广泛应用于计算机科学和金融等许多研究领域，它所关心的问题是在已知场景下如何快速做出决策。博弈论中的一个典型问题是双人博弈。通过将双人博弈转化为决策树模型，求解该树中的最优值函数来确定博弈的胜负。博弈树可以形式化为与或树(AND-OR Tree)，此时博弈问题的极小极大值对应于与或树中最优解的值。如何高效地评估与或树的最优解成为博弈问题解决的核心。传统上的Alpha-Beta 剪枝等经典算法虽然可以在有限时间内以零误差计算出平衡二分叉与或树的最优值；但在复杂度较高的情况下，该方法的计算效率仍有待提高。

研究进展

针对传统博弈算法计算复杂度高等问题，北京理工大学的张向东教授、陈天副教授和研究生张金良等提出了一种基于与或树结构实现量子双人博弈的新方案。研究人员采用子博弈设计技术，基于连续时间量子行走设计了一种新的双人博弈量子算法。如图1所示，他们提出的算法显示，用于评估近似平衡与或树的查询时间t与输入数据N满足的复杂度。这一速度远快于经典最优博弈算法的时间复杂度，.

紧接着，研究人员利用薛定谔方程的波函数与基尔霍夫定律中的电压的对应，将量子博弈树的设计有效地映射到经典电路网络，如图2所示。在研究中，他们选择五输入的双人博弈树作为例子，并将其按博弈的先后顺序划分为四输入的子博弈树和三输入的子博弈树。他们的结果验证了子博弈树的最优路径与整个博弈树的最优路径之间的一致性。更重要的是，从博弈树中获得输出结果的时间t与输入数据N满足，这与量子算法中的时间复杂度有着很好的对应关系。这说明不仅可以从理论上模拟出满足双人博弈的快速运算结果；还通过设计经典电路网络，在实验上验证相应的量子加速效果。

未来展望

现有的研究关注了使用经典电路网络实现双人博弈问题的快速求解。从研究问题上来说，可以使用博弈树来实现更复杂的、具有量子加速的博弈问题。这些问题包括但不限于如国际象棋、经济学、网络安全、计算机科学和金融等。而从实现方式来说，可以将现有在传统电路网络的实现方式映射到集成电路平台。相对于传统电路网络，集成电路平台具有更小的误差、更低的功耗、更易于大规模生产等特点，这使得集成电路平台能够展示更多数据输入下的博弈问题快速求解。这些将为大数据时代的计算能力提高提供新的思路，并将在各个领域得到广泛应用。