在噪声存在的情况下，MIP*的计算优势会消失

《Journal of the ACM》：The Computational Advantage of MIP* Vanishes in the Presence of Noise

量子多证明者交互证明系统在共享态含噪声时的计算能力研究，证明噪声完全消除了纠缠优势，将复杂性从NEEEXP提升至NEXP，并对比噪声存在与否的影响，同时开发了低度傅里叶分解测试器和光滑矩阵函数不变量原理。

　　

摘要

具有量子纠缠特性的多证明者交互式证明系统（MIP^*）类比其经典对应物MIP[8, 31, 32]具有更强的计算能力：虽然MIP属于NEXP类，但量子类MIP^*属于RE类，而RE类包含了停机问题等复杂问题。这是因为MIP^*中的证明者可以共享无限制的量子纠缠。然而，最近的研究[53, 54]表明，如果证明者共享的状态中存在噪声，这种优势会显著减弱。本文试图精确描述噪声对量子多证明者交互式证明系统计算能力的影响。我们研究了量子两证明者一轮交互式系统MIP^*[poly], O(1)，其中验证者向证明者发送多项式级别的比特数，证明者则持续不断地发送比特数。我们发现，在该模型中，噪声完全破坏了由共享纠缠带来的计算优势。具体来说，我们证明了如果证明者能够共享任意数量的EPR态（每个EPR态仅受到极少量噪声的影响），那么最终的复杂性类等同于NEXP = MIP。这显著改进了之前已知的最佳界限NEEEXP（非确定性三指数时间）[53]。我们还证明了这种计算能力的下降是由于噪声所致，而非由于回答规模的O(1)特性，因为允许使用无噪声的EPR态可以使该系统的计算能力达到RE = MIP^*[polypoly]类的水平。在此过程中，我们开发了两个具有独立研究价值的技术工具：首先，我们提出了一种新的确定性测试方法，用于判断一个指数级大的矩阵是否为正矩阵（前提是该矩阵可以用Pauli矩阵进行低阶傅里叶分解）；其次，我们为具有有界三阶Fréchet导数或Lipschitz连续性的光滑矩阵函数提出了一种新的不变性原理。