量子时序叠加的模拟复杂度：量子电路无法高效模拟量子交换作用

《Nature Communications》：Simulating the quantum switch with quantum circuits is computationally hard

本研究针对量子高阶变换中因果序不确定的量子开关(quantum switch)是否可被量子电路有效模拟这一核心问题展开。研究人员通过理论证明与计算机辅助验证，首次确立了量子开关在量子查询复杂度上相对于传统量子电路的指数级优势，即模拟n量子比特信道的量子开关至少需要2n次查询。该结果揭示了因果序不确定的量子过程拥有远超经典因果序量子信息处理能力的本质特征，对理解量子计算的终极极限具有重要意义。

　　

在量子信息科学的前沿探索中，因果序不确定的量子过程一直被视为挑战传统计算范式的重要概念。量子开关作为这类过程的典型代表，能够以量子叠加的方式控制两个量子信道的作用顺序，从而在信道鉴别、量子计量等任务中展现出潜在优势。然而，一个长期悬而未决的根本问题是：这种源于因果序不确定性的优势是否本质？或者说，能否通过增加传统量子电路对基本信道的调用次数来精确模拟量子开关的行为？这一问题的答案关乎我们对量子计算资源本质的理解，也决定了因果序不确定过程是否真正拥有超越传统量子计算模型的潜力。

以往的研究表明，对于特殊的酉信道，量子开关确实可以被仅增加一次查询的量子电路所模拟。但这仅限于理想情况。当面对更一般的量子信道（包括噪声信道和非酉演化）时，量子开关的模拟复杂度问题始终迷雾重重。是否存在一种通用的、确定性的量子电路，能够通过有限次额外调用任意输入信道，来完美复现量子开关的行为？这个问题构成了量子计算复杂性理论中的一个关键挑战。

发表在《Nature Communications》上的这项研究，通过严谨的理论证明和创新的计算机辅助验证方法，对上述问题给出了明确的否定答案。研究团队证明了，对于作用在两个n量子比特信道上的量子开关，任何采用固定顺序或经典控制因果序的量子电路，如果对其中一个信道的调用次数k小于2ⁿ，则不可能实现对其的确定性精确模拟。这首次确立了因果序不确定过程与量子电路之间在查询复杂度上存在指数级分离。更有甚者，研究还发现即使为两个信道各增加一次调用（即k_A=k_B=2），这样的模拟仍然是不可能的。这一结论在概率性模拟和近似模拟的场景下也展现出很强的鲁棒性。

为了开展这项研究，作者们主要运用了以下几项关键技术方法：首先，他们基于Choi-Jamiolkowski同构和链积（link product）理论，建立了高阶量子变换的严格数学框架。其次，他们将量子开关的模拟问题转化为半定规划（Semidefinite Programming, SDP）问题进行形式化表述和求解。尤为关键的是，他们开发了一套创新的计算机辅助证明方法，能够将数值SDP求解器得到的近似解转化为包含有理数的严格上界证明，从而确保了研究结论的数学严谨性。此外，研究还针对不同信道调用次数（k_A, k_B）和不同因果序结构（量子组合（quantum comb）与经典控制量子电路（QC-CC））等多种场景进行了系统分析。

量子开关模拟

量子开关S是一个高阶变换，它以两个任意量子信道A和B作为输入，并生成一个新的作用于量子比特控制系统和量子比特目标系统的信道S(A, B)。其核心特征在于操作顺序由控制系统的量子态相干控制。一个确定性且精确的量子开关模拟，要求找到一个遵守因果约束的高阶变换C，该变换使用有限次（k_A和k_B）对信道A和B的调用，使得对于所有量子信道A和B，都有C(A^?k_A, B^?k_B) = S(A, B)成立。研究所考虑的因果约束包括固定顺序的量子电路（即量子组合）以及更一般的允许经典控制因果序的量子电路（QC-CC）。

可行性定理：一个显式的非通用模拟

研究首先指出，对于某些特定类型的输入信道，非通用的模拟是存在的。例如，当输入信道限制为酉信道时，存在一个仅需对其中一个信道增加一次调用的量子电路可以模拟量子开关。此外，研究还通过定理1证明，当量子开关仅作用于二分信道的一部分，且其中一个信道（如A）被限制为酉信道，而另一个信道（B）是任意信道时，其作用可以被一个量子电路确定性模拟，该电路需要k_A=2次调用A和k_B=1次调用B。这通过显式地构建一个量子电路来实现。

不可行性定理：确定性精确模拟

然而，上述可行性结果并不能推广到一般情况。研究的主要结论体现在定理2中：对于作用于任意n量子比特混合酉信道A和酉信道B的量子开关，如果k_A ≤ max(2, 2ⁿ-1)，那么不存在任何由固定或经典控制因果序量子电路描述的(k_A+1)槽高阶变换C能够模拟量子开关。这意味着，当仅允许一次调用信道B时，模拟量子开关所需对信道A的调用次数随量子比特数n呈指数增长。该定理进而表明，这样的模拟对于所有n量子比特量子信道A和B也都是不可能的。这一定理揭示了在量子查询复杂度上，因果序不确定过程相对于量子电路存在指数级优势。

不可行性定理：概率性模拟

研究进一步探讨了当允许更多信道调用时的情况。定理3表明，即使当k_A=k_B=2时，也不存在能够确定性模拟作用于任意量子信道的量子开关的量子电路。甚至对于单量子比特信道，以及在输入态固定且目标输出系统被丢弃的受限模拟场景下，其成功模拟的概率p也严格小于1。研究通过计算机辅助证明，为多种不同信道调用次数组合（如(1,1), (2,1), (2,2), (3,1)）和不同操作顺序下的最大成功概率提供了严格的数值上界。

不可行性定理：近似模拟

研究还考察了近似模拟的鲁棒性。即使考虑输出信道与量子开关在Choi算子保真度上接近（即ε>0），对于某些特定的调用次数（如(k_A, k_B)为(1,1)或(2,1)），以概率1成功模拟这些近似变换仍然是不可能的。数值分析显示，只有当近似误差ε足够大时，成功概率p才可能达到1。

一个猜想

基于所有证据，研究者提出了一个猜想：对于所有n量子比特量子信道A和B，如果max(k_A, k_B) ≤ g(n)，且g(n) = Θ(2ⁿ)，那么不存在任何由固定或经典控制因果序量子电路描述的(k_A+k_B)槽高阶变换C能够模拟量子开关。这意味着，即使允许对两个信道进行多次（但亚指数次）调用，确定性模拟量子开关也可能是不可能的。

综上所述，这项研究通过一系列严格的不可行性定理，强有力地证明了量子开关所代表的因果序不确定量子过程拥有内在的、无法被传统量子电路有效模拟的计算优势。这不仅深化了我们对高阶量子计算和理解量子计算资源本质的理解，也为未来探索量子优势的新形式奠定了重要的理论基础。研究所开发的计算机辅助证明方法也为复杂量子信息问题的严格分析提供了新的工具。该成果预示着，因果序不确定性可能是一种真正有别于且超越传统量子计算资源的、具有指数级优势的量子资源。