CNOT-Distance is NP-complete under all-to-all connectivity

技术摘要：在全连接架构下，CNOT 距离问题是 NP-完全的

问题陈述
本文研究了 CNOT 距离 (CNOT-Distance) 问题的计算复杂度。给定一个显式表示的可逆二进制矩阵 $A \in GL(N, 2)$ 和一个整数 $K$，该问题询问是否可以用至多 $K$ 个 CNOT 门在 $N$ 条固定的、有标签的导线上实现 $A$，且采用 全连接 (all-to-all connectivity) 架构。该模型假设没有辅助导线（尽管也考虑了带有辅助导线的变体），不考虑无抵消约束，也不规定门的顺序。目标是确定合成 $A$ 所需的最少门数（即 $GL(N, 2)$ 中由变换矩阵生成的 Cayley 图的字长）。

虽然高斯消元法提供了 $O(N^2)$ 的上界，且针对最坏情况的改进算法已经存在，但对于特定实例寻找精确最小门数的问题仍未解决。以往的硬度结果主要集中在受限拓扑、具有特定输入编码的奇偶网络或包含 Clifford+T 的门集上。对于固定标签、全连接 CNOT 合成的特定硬度问题，此前一直是一个悬而未决的问题。

方法论
作者通过将问题归约至有限简单图上的 最小顶点覆盖 (Minimum Vertex Cover) 问题，证明了其 NP-完全性。

1. 目标矩阵的构造：
   对于给定的图 $G = (V, E)$，作者构造了一个特定的上单位三角矩阵 $A_G \in GL(2|V| + |E| + 1, 2)$。该矩阵作用于一组导线，包括一个 distinguished 导线 $z$，每个顶点 $v \in V$ 对应的一对导线 $(q_v, x_v)$，以及每个边 $e \in E$ 对应的一条导线 $y_e$。其变换定义如下：

   • $q'_v = q_v + z$
   • $x'_v = x_v + q_v$
   • $y'_e = y_e + z + x_u + x_v$ （对于边 $e=\{u,v\}$）

2. 精确距离恒等式：
   证明的核心在于确立了以下精确恒等式：
   $$\ell_{\text{CNOT}}(A_G) = 2|V| + 2|E| + \tau(G)$$
   其中 $\tau(G)$ 是图 $G$ 的最小顶点覆盖的大小。

3. 上界构造：
   作者展示了任何顶点覆盖 $C$ 都能产生一个长度为 $2|V| + 2|E| + |C|$ 的 CNOT 电路。在该构造中，被选中的顶点导线暂时承担了向关联边输出传递 $z$ 的贡献，从而有效地实现了所需的奇偶校验。

4. 通过投影-收缩实现的下界：
   下界是本文的创新贡献。作者表明，实现 $A_G$ 的任何任意 CNOT 电路（即使存在抵消和中间复用）都可以被“展开”为一个 XOR 有向无环图 (DAG)。通过应用 投影 (projection)（将特定输入设为零）和 收缩 (contraction)（合并具有相同投影值的节点），可以系统地移除电路中的“可逆簿记 (reversible bookkeeping)”组件。

   • 投影顶点输入会强制删除 $2|V|$ 个节点。
   • 投影私有边输入会强制删除 $|E|$ 个节点。
   • 剩余结构是一个计算形式集 $F_G = \{z + x_u + x_v \mid \{u,v\} \in E\}$ 的 XOR 直线程序。
   • 利用 Boyar-Matthews-Peralta 引理的二进制特化版本，证明该剩余程序的长度至少为 $|E| + \tau(G)$。
   • 结合这些步骤得出下界 $L \ge 2|V| + 2|E| + \tau(G)$。

5. 辅助导线的鲁棒性：
   作者证明，添加任何有限数量的 干净 (clean) 或 借用 (borrowed) 辅助导线都不会降低该类矩阵的最优门数。投影-收缩论证通过将辅助变量视为投影的额外输入，可以扩展到这些情况。

核心贡献与结果

• NP-完全性： CNOT 距离问题被证明是 NP-完全的。即使在以下高度受限的实例中也是如此：
  • $A$ 是上单位三角矩阵。
  • 每一行最多有 4 个汉明权重。
  • $A$ 的阶数为 4（即 $(A-I)^3=0$ 且 $A^4=I$）。
  • 门预算 $K < 2N$。
• 精确计算的硬度： 计算精确的 CNOT 距离 $\ell_{\text{CNOT}}(A)$ 是 NP-难的。
• 近似硬度：
  • 加性 (Additive)： 在任何固定加性常数 $c$ 范围内近似该距离是 NP-难的。
  • 乘性 (Multiplicative)： 该优化问题是 APX-难 (APX-hard) 的（通过从立方图上的最小顶点覆盖进行 L-归约），这意味着除非 P=NP，否则不存在多项式时间近似方案 (PTAS)。
• 辅助不变性： 对于构造的矩阵族 $A_G$，最小门数在无辅助导线、干净辅助导线和借用辅助导线模型下是相同的。
• 构造性解码器： 该归约包含一个多项式时间解码器，给定 $A_G$ 的任何 CNOT 电路，它可以提取出 $G$ 的一个顶点覆盖，其大小由电路长度减去一个常数因子来界定。这对于建立用于 APX-硬度的 L-归约至关重要。

意义与主张

本论文解决了这样一个基本问题：当移除架构约束（路由、可用门集）后，最小化规模的 CNOT 合成是否仍然具有计算难度。作者声称，这种硬度源于线性可逆实现本身的最小化过程，而非来自特定设备的几何特性。

结果明确了可处理合成与不可处理合成之间的界限：

• 即使对于稀疏、有结构的矩阵（上单位三角且具有低汉明权重），问题仍然是困难的。
• 无论使用辅助导线（干净或借用，只要必须恢复状态），这种硬度依然存在。
• 投影-收缩技术提供了一种从任意可逆实现中提取非可逆内核（如 XOR 复杂度）的通用方法，这表明抵消和中间复用并不能规避基本的组合难度。

作者指出，虽然该结果意味着任何能够嵌入完全双向图（通过归约的均匀性属性）的架构族都具有 NP-难性，但它并未确定特定固定稀疏拓扑（如路径或星型图）的复杂度，因为限制生成集会完全改变距离度量。