并行逼近极大极小问题算法：竞争证明复杂性的突破

本文主要探讨了一种针对极大极小问题的有效并行逼近算法，该算法源自矩阵乘法权重更新方法，特别适用于求解经典或量子环境中的竞争性两方策略。作者们在加拿大多伦多滑铁卢大学量子计算研究所和计算机科学学院的Gus Gutoski和晓迪，以及美国密歇根大学电气工程与计算机科学系的研究人员，提出了这一创新性解决方案。 极大极小问题通常涉及在一个约束条件下找到最优化的决策，如在半定规划（SDP）框架中，目标是寻找一组矩阵X1到Xk，使得Tr(XkP)最小，同时满足一系列线性等式和矩阵非负性条件。在这个背景下，文章关注的是如何在并行环境下更高效地解决这类问题，特别是当裁判允许双方自由交换消息时。 新提出的并行逼近算法允许裁判与一方交换无限次消息，而后续一方还可以与其他任意数量的额外消息进行交互。这种设计使得算法能够处理更为复杂的互动情况，首次展示了存在一种适应性反应的并行解决方案。通过证明这些竞争证明复杂性类，如QRG(2)，SQG和新定义的DIP和DQIP，研究者揭示了这些类与PSPACE复杂性类的关系，表明它们可能被包含在PSPACE内。 其中一个关键的应用案例是半定规划的并行逼近方案，其中可行域由满足转录一致性条件的半定矩阵列表构成。将这个特殊情形应用于多消息量子交互式证明中，研究人员得以获得一个直接的多项式空间模拟，从而为QIP=PSPACE的原始证明提供了一个新的基础。 这项工作不仅提升了极大极小问题的并行求解能力，而且深化了我们对量子计算和经典计算下交互式证明复杂性的理解。这一突破性成果对于推动理论计算机科学，特别是在量子博弈论、优化算法和复杂性理论领域，具有重要的理论价值和实践意义。