最优 matchgate-Clifford 合成何时可高效求解？

门集连通性决定问题是否可解

论文提出的问题很窄且定义明确：给定一个目标 matchgate-Clifford 酉算子和一个由 Majorana 编织构成的门集，能否输出用最少操作实现该目标的 n 量子比特电路，这个问题有多难？答案取决于编织的连通图。对路径图和完全图，该问题可在 O(n^2) 时间内经典求解，作者给出了显式的门最优编译器。对任意树形连通图，该问题的判定版本变为 NP 完全。

这是一个复杂度分离，而不是单一算法。整篇论文使用同一个目标群和同一类生成元，改变的只是允许编织沿其边作用的图。正因如此，结果被表述为关于生成集、尤其是其连通性如何进入问题的论断。

为什么用带符号置换代替酉矩阵

Matchgate-Clifford 酉算子是 matchgate 群与 Clifford 群的交集。它们在 2n 个 Majorana 算子上的伴随作用，同构于行列式为 +1 的 2n x 2n 带符号置换矩阵群，记作 B_2n ∩ SO(2n)。在这一表示下工作可以避开酉矩阵的指数级规模，这正是复杂度分析得以有意义的前提。

生成集中的一个门是一次 Majorana 编织，它表现为连通图某条边所连接的两个 Majorana 之间的带符号对换。合成问题于是变成一个词问题：把目标带符号置换表示为沿允许边的最短编织乘积。判定版本问的是是否存在长度不超过 k 的词；只要最优长度是 n 的多项式，该问题就属于 NP，因为候选词可以通过矩阵相乘来验证。

路径图上最优长度有闭式表达

对开放路径上的最近邻编织，作者使用的生成元由单量子比特相位门 S 和双量子比特 R_xx(pi/2) 门构成，它们生成 matchgate-Clifford 群，并且在一些中性原子和离子阱平台上属于原生门。最优长度由一个势函数给出：Phi(w) = inv(pi) + 2 nu(w)，其中 inv(pi) 是底层置换的逆序数，nu(w) 统计负缺陷，即满足 Delta_c(w) = -1 的割点 c。

逆序项与已知的无符号置换最近邻对换长度一致。额外的 2 nu(w) 项是符号修正代价：由于每个生成元的行列式都为正，行列式为 -1 的块无法从块内部修正，因此算法把符号放在块的边界，并在割点处施加 r_c^2。证明先说明单个生成元至多让 Phi(w) 改变一，从而给出下界，再给出与之匹配的算法，得到 O(n^2) 时间内 l_R(w) = Phi(w)。

基准测试显示门数取得常数倍改进

路径编译器与四种替代方案进行了基准比较：基于冒泡排序的先排序后修正策略、Givens 消元策略，以及通用编译器 Qiskit 和 pytket。目标电路是在生成集上以长度 10n 的随机游走生成的 matchgate-Clifford 电路，编译规模为最多 n = 80 量子比特的链。

在总门数上，最优编译器产生的电路比所有替代方案都短，相对 matchgate 专用方法的改进约为 1.5 倍，相对通用编译器最高约为 2.6 倍。具体到 Qiskit 和 Tket，摘要报告总门数分别改进 x2.57 和 x2.28。论文还给出了最少双量子比特门数的界，并指出存在一个电路能同时达到该双量子比特门数和最优总门数。这些是常数倍改进，不是渐近增益，而且是在路径连通情形下测得的。

完全连通同样可在多项式时间内求解

当连通图是完全图，即允许任意一对 Majorana 之间的编织时，作者同样证明可在 O(n^2) 时间内经典求解，并给出最优词长的闭式表达。其机制与路径情形不同：算法通过识别缺陷环并排序环与符号来工作，每次迭代把到恒等元的距离增加一。由于 Cayley 图直径为 2n，至多需要 2n 次这样的迭代，由此得到 O(n^2) 的界。

因此路径图和完全图都位于这一分离的可解一侧，但原因在结构上不同。论文把它们作为两个独立的定理给出，而不是一个一般性结果，闭式长度也各自针对相应的连通性。

树形图从令牌交换路由继承困难性

当作为输入的连通图是任意树时，门最优 matchgate-Clifford 合成的判定版本是 NP 完全的。该归约来自树上的路由问题：它要求用最少的沿树边交换次数实现顶点上令牌的指定置换，而该问题本身是 NP 完全的。

路由与合成之间的差距在于 Majorana 编织引入的符号。作者证明，对任意置换都能高效地找到一种符号配置，使得所得带符号置换的最短编织序列长度恰好等于原置换的最少交换次数。关键在于，符号配置必须仅由置换本身确定，而不能预先知道最优路由。树上的合成长度存在多项式上界，这使问题落入 NP，从而完成 NP 完全性证明。同一归约还表明树上的深度最优合成是 NP 完全的，一个推论把这两个结果推广到一般连通图。

这一分离覆盖与未覆盖的范围

可解性结果针对的是在特定固定连通性下、matchgate-Clifford 群内的精确最优合成，基准测试覆盖的是最多 n = 80 量子比特链上的路径情形。NP 完全性结果针对的是连通图作为输入一部分时的判定版本，这与编译某个固定硬件拓扑是不同的问题。论文指出，找出哪些固定连通性允许高效最优合成仍是开放问题。

作者还指出，完整 matchgate 群的最优合成复杂度（无论精确还是近似）仍然未知，因此这些结果不应被理解为已经解决了 matchgate 编译的一般问题。词长公式适用于本文研究的 Majorana 编织生成元；B 型和 D 型 Coxeter 群的标准长度函数使用不同的生成集，并不包含额外的符号修正项。

实际优先级落在哪里

本文中最具决策意义的分界是固定连通性与输入连通性之别。如果编织连通性是路径图或完全图，最优电路可在 O(n^2) 时间内找到，并在最多 n = 80 量子比特的链上以总门数 x2.57 和 x2.28 的常数倍优于 Qiskit 和 Tket。如果连通性是作为输入的任意树，则除非 P = NP，不存在最坏情况下的多项式时间算法。

对正在选择费米子架构或编译策略的读者而言，论文自身的变量指向同一个优先级：决定门最优合成能否达成的是可用编织的连通图，而不是目标酉算子。作者特别指出路径情形对实际 matchgate 电路最相关，因为在 Jordan-Wigner 映射下其生成元对应单量子比特 S 门和双量子比特 R_xx(pi/2) 旋转。

本文引用的文献