摘要：2024年10月9日，南京大学计算机科学与技术系的姚鹏晖教授访问北京大学前沿计算研究中心，并在静园五院举行了一场题为“Some Applications of Pauli Analysis on Quantum Algorithms and Complexit

2024年10月9日，南京大学计算机科学与技术系的姚鹏晖教授访问北京大学前沿计算研究中心，并在静园五院举行了一场题为“Some Applications of Pauli Analysis on Quantum Algorithms and Complexity”的学术报告，介绍了 Pauli analysis 的具体含义及其在量子算法和量子复杂性理论中的最新应用。此次报告由中心助理教授李彤阳老师主持。

报告伊始，姚教授从大家熟悉的傅里叶分析入手，解释了它在计算机科学领域中的重要性，尤其是在学习理论、复杂性理论、伪随机性和密码学等方向上的广泛应用。其中，Boolean analysis 为布尔函数空间上的傅里叶分析，能够有效地搭起离散数学与连续数学之间的桥梁。姚教授定义了布尔分析中空间、内积、正交基、傅里叶展开、范数等定义，由于布尔空间上的傅里叶展开式可以理解为多项式，他进而又定义了度数，以及每个坐标对整个函数的 influence 等量，并相应推导了布尔空间中的 Parseval 等式。

接下来，姚教授将傅里叶分析引入到量子计算的世界。他指出，布尔函数空间与对称厄密矩阵空间之间存在同构关系，进而提出了 Pauli analysis 的基本框架。与布尔函数空间不同，在 Pauli analysis 中，考虑的空间是由所有厄密矩阵组成的空间。由于矩阵乘法中基不可交换，Pauli analysis 比传统的布尔分析更复杂，布尔代数中简单的二元串变为了四元 (I,X,Y,Z) 串。姚教授强调，基的不可交换性正是 Pauli analysis 困难的主要来源。

在介绍完 Pauli analysis 的基础概念后，姚教授着重讲解了 Pauli analysis 在量子算法中的三个具体应用：

应用1：Noisy MIP*

首先，姚教授介绍了 MIP（多重交互证明系统）的传统问题设定，以及在量子环境下的扩展形式 MIP*。在 MIP*中，量子 prover 虽然无法交换信息，但可以共享任意的量子态。研究发现 MIP*的计算能力不逊于经典的 MIP，甚至能够解决停机问题，这表明 MIP*的复杂性是不可判定的。这个结论并不 trivial，因为在量子 setting 下诚实的和不诚实的 prover 计算能力都增强了。

姚教授的研究聚焦于 MIP* with noisy EPR states，特别是纠缠态在这一问题中的作用。他们发现，引入噪音后，理论上纠缠仍然趋向无穷大，但实际情况表明，如果共享带噪音的纠缠态，计算能力会显著下降。这一发现否定了“纠缠是计算能力提升的唯一来源”的猜想。姚教授解释了 Pauli analysis 在这个研究中的关键作用：通过在 Pauli 基上展开测量，并对测量系数进行微调，确保影响较大的项保持不变，影响较小的部分通过高斯分布近似，从而利用维数规约技术进行降维处理。

应用2：Junta Testing and Learning

在量子学习理论中，Junta testing 和 learning 是两个重要的研究课题。姚教授展示了如何利用 Pauli analysis 来处理 quantum Junta tunnel，将 operator 升为 super-operator。估算 influence 的算法步骤相对简单：首先将 n qubits 输入到 quantum channel 中，用 computational basis 测量检查输出是否与输入相同。若相同，再使用 Hadamard 基进行类似操作。姚教授还分享了他们团队与实验平台的合作，他们的实验结果表明，Pauli analysis 不仅在理论上具有重要意义，还能够在实验中验证某些物理现象。

应用3：Quantum Circuit Lower Bounds

第三个应用涉及量子电路复杂性，特别是对 QNC0 和 QAC0 电路的研究。QNC0 浅层量子电路的输出仅与有限个比特相关，因此计算能力有限。而 QAC0 电路则允许任意大小的 Toffoli 门，这使得其计算能力大大增强。然而，关于 QAC0 与经典 AC0 电路之间的关系，许多问题尚未得到充分研究。姚教授详细介绍了他们团队在 QAC0 computing parity 问题中的最新进展。他们通过 Pauli analysis 对具有有界误差的浅层 QAC0 电路的 ancilla 位数进行了下界证明，并讨论了 Pauli analysis 如何在计算复杂性中起到关键作用。

最后，姚教授列举了一些其他应用了 Pauli analysis 的问题，如 Hamiltonian property testing，predicting quantum channels 等。姚教授展望了 Pauli analysis 的未来发展方向。姚教授认为，Pauli analysis 的应用前景广阔，还有许多未解的课题值得进一步探索，如数学问题中的 quantum KKL theorem 和 Biased Pauli analysis；学习理论中的 tight bound for quantum junta testing；复杂性理论中的 decidability of local state transformation；物理学中的 application of Pauli analysis in local Hamiltonian system 等等。姚教授鼓励在座的学生积极参与这一领域的研究，他认为尽管 Pauli analysis 是一个相对年轻的研究领域，但也是一个充满潜力的方向，并且在2021年开始获得越来越多的关注。

报告结束后，现场的师生们踊跃提问，讨论了 Pauli analysis 与其它领域的关联以及其在实际量子系统中的实验效果等问题，姚教授就师生们的提问进行了深入解答，整个讲座在热烈的学术讨论氛围和掌声中圆满结束。

图文 | 杨子熠

来源：北京大学前沿计算研究中心一点号