量子科技中心_量科网

关于零和博弈中纳什均衡的计算在经典与量子情境下已有广泛研究。对于一般和博弈，纳什均衡的计算属于PPAD难题，而博弈论中更广泛研究的关联均衡概念也已被深入探索。本工作首次提出利用量子算法计算多人标准型博弈中ε-近似关联均衡（CE）与粗关联均衡（CCE）的研究。研究团队通过量子化改进的多尺度乘性权重更新（MWU）方法计算CE，在固定ε条件下实现了~O(m√n)的查询复杂度。针对CCE，该团队将零和博弈量子算法技术拓展至多人场景，获得~O(m√n/ε²⁵)的查询复杂度。两种算法在玩家数量m与策略数n维度上均展现出近乎最优的标度特性，该结论已通过量子查询下界验证得到确认。