技术摘要：关于近似量子电路成员资格与优化的硬度

1. 问题定义

本文研究了量子电路理论中两个基本问题的计算复杂度：近似成员资格（Approximate Membership）与近似优化（Approximate Optimization）。

• 近似成员资格 ($\text{ApproxMember}$)：给定一个基于门集 $G$ 的量子电路 $C$、一组幺正变换集合 $S$、距离度量 $m$ 以及容差 $\epsilon$，判定是否存在一个幺正变换 $U \in S$，使得距离 $d_m(C, U) \le \epsilon$。
  • 一个特例是 近似恒等（$\text{ApproxId}$），其中 $S = \{I\}$。
  • 本文考虑了三种特定的集合 $S$：
    1. $S = \{I\}$（恒等变换）。
    2. $S \subseteq S_{\text{Cliff}}$（由 Clifford 电路实现的幺正变换）。
    3. $S \subseteq S_{\text{GP}}$（广义置换矩阵，即不产生叠加态的幺正变换）。
• 近似优化 ($\text{ApproxOpt}$)：给定一个电路 $C$、一个代价函数 $f$ 和一个预算 $k$，判定是否存在一个等价电路 $C'$，满足 $d_m(C, C') \le \epsilon$ 且 $f(C') \le k$。代价函数 $f$ 由其“自由集” $S_f = \{U_{C'} \mid f(C') = 0\}$ 表征。

本研究关注的是**无承诺（promise-free）**输入，这与 Janzing, Wocjan, 和 Beth (2005) 的工作形成对比，后者在“非恒等检查”问题下，通过一个电路要么接近要么远离恒等变换的承诺，建立了 QMA 完全性。这项工作移除了该承诺，转而询问当输入电路与目标集合的距离未知时，问题是否仍然具有硬度。

作者分析了三种用于衡量幺正变换之间距离的标准度量：

1. 正弦度量（Sine Metric）：基于迹（trace），捕捉平均情况下的差异（$d_{\text{Sine}}$）。
2. 谱度量（Spectral Metric）：基于算子范数，捕捉最坏情况下的差异（$d_{\text{sp}}$）。
3. 算子度量（Operator Metric）：谱度量的全局相位不变版本（$d_{\text{op}}$）。

2. 方法论

作者通过将 PP（概率多项式时间）复杂度类归约至近似成员资格问题来建立硬度。其核心方法论包含以下步骤：

1. 源问题：他们利用了 AtMostSat，这是一个 PP-hard 问题，询问一个命题公式 $\phi$ 是否被至多 $\beta$ 比例的赋值所满足。他们引入了一个承诺版本 PromiseAtMostSat，其中满足赋值的比例被承诺至多为 $\kappa$。
2. 从承诺到近似的归约：他们证明了 PromiseApproxId（在已知电路与 $I$ 接近或远离的承诺下检查电路是否 $\epsilon$-接近 $I$）是 PP-hard 的。这是通过从公式 $\phi$ 构建 Clifford+T 电路 $C$ 来实现的，使得距离 $d_m(I, C)$ 是满足比例 $\gamma(\phi)$ 的严格递增函数 $g(\gamma(\phi))$。
   • 对于 正弦度量，他们构造了一个实现受控异或操作（controlled-XOR operation, $|x\rangle|b\rangle \mapsto |x\rangle|b \oplus \phi(x)\rangle$）的电路。
   • 对于 谱度量和算子度量，他们利用 Grover 迭代构造了特征角依赖于 $\gamma(\phi)$ 的电路。对于算子度量，他们采用这些电路的张量积来控制特征角在单位圆上的弧长。
3. 移除承诺：
   • 情况 $S = \{I\}$：承诺版本的硬度直接意味着在特定 $\epsilon$ 范围内，针对该特定集合的无承诺版本也是 PP-hard 的。
   • 情况 $S \subseteq S_{\text{Cliff}}$：他们利用三角不等式引理（Lemma 6）。他们证明了对于足够小的 $\epsilon$（具体而言 $\epsilon < \sqrt{2}/4$），如果一个电路被承诺接近 $I$，那么在 $S_{\text{Cliff}}$ 中能与 $C$ 保持 $\epsilon$-接近的元素只能是与 $I$ 距离为 0 的元素（即 $I$ 本身）。这依赖于对 $I$ 与任何其他 Clifford 幺正变换之间的最小非零距离的下界估计。
   • 情况 $S \subseteq S_{\text{GP}}$：他们构造了特定的电路，使得在较小的 $\gamma(\phi)$ 时，到广义置换矩阵集的距离恰好等于到恒等变换的距离，从而允许直接从承诺问题进行归约。该归约特别适用于恒等变换 $I$ 被包含在集合 $S$ 中的情况（即 $I \in S \subseteq S_{\text{GP}}$）。

3. 主要贡献与结果

主定理 (Theorem 1)

论文证明，只要门集 $G$ 能够精确实现 Clifford+T，则 ApproxMember 在广泛的参数范围内都是 PP-hard 的。该硬度适用于：

• 集合 $S$：$S=\{I\}$，$I \in S \subseteq S_{\text{Cliff}}$，以及 $I \in S \subseteq S_{\text{GP}}$。
• 度量：正弦、谱及算子度量。
• 容差 $\epsilon$：
  • 对于 $S=\{I\}$ 且为基于迹的（正弦）度量：对于所有 $0 < \epsilon < 1$（全直径）均为 PP-hard。
  • 对于 $S=\{I\}$ 且为谱/算子度量：对于所有 $0 < \epsilon < 2$ 均为 PP-hard。
  • 对于 $I \in S \subseteq S_{\text{Cliff}}$：对于 $0 < \epsilon < \sqrt{2}/4 \approx 0.3536$ 均为 PP-hard。
  • 对于 $I \in S \subseteq S_{\text{GP}}$：对于正弦度量 $0 < \epsilon < 1$ 且对于谱/算子度量 $0 < \epsilon < \sqrt{2}$ 均为 PP-hard。

推论 1 (优化硬度)

这些结果直接意味着，在相应的 $\epsilon$ 范围内，最小化总门深度/计数、非 Clifford 门深度/计数以及叠加态门深度/计数的 ApproxOpt 问题是 PP-hard 的。

特定技术发现

1. 经典可逆门下的硬度：即使当门集 $G$ 仅由经典可逆门（如 X, CNOT, Toffoli）组成（无法产生叠加态）时，正弦度量下的 ApproxId 问题在 $0 < \epsilon < 1$ 时仍然是 PP-hard 的。
2. 鲁棒性：硬度结果可以推广到任何通过正弦、谱或算子度量构成的严格递增函数导出的距离度量。此外，即使目标是近似最小化任何因子的代价（无论常数与否），由于硬度在最优代价为 0 时依然成立，这些问题仍然是 PP-hard 的。
3. 与前人工作的比较：本文强化了 Janzing, Wocjan, 和 Beth (2005) 的结果。虽然他们的工作展示了“非恒等检查”这一承诺问题的 QMA 完全性，但本文表明，对于更广泛的度量和集合 $S$，无承诺的问题是 PP-hard 的（PP 类被认为比 QMA 难得多）。

4. 意义与主张

作者声称，其结果表明，与基于承诺的非恒等检查的 QMA 完全性相比，近似量子电路优化在无承诺输入下在本质上更难。

• 资源无关性：无论使用何种量子资源（任何门、非 Clifford 门或叠加态），硬度依然存在。
• 度量无关性：硬度在各种距离度量（基于迹、谱或算子度量）下均成立。
• 实际影响：由于标准硬件门集（如 Clifford+T）满足这些条件，这些硬度结果直接适用于现实世界的量子编译与优化任务。结果表明，寻找一个近似等价且代价最小（例如最小 T-count 或深度）的电路对于经典计算机来说是难以处理的，即使允许近似误差，除非误差容差过大（超过度量空间的直径）。

论文最后指出，关于更大 $\epsilon$ 值（特别是对于 Clifford 集合 $\epsilon \ge \sqrt{2}/4$ 以及对于置换集合 $\epsilon \ge \sqrt{2}$）的复杂度以及匹配的上界仍是开放性问题，尽管它提到对于代数门集且在 $\epsilon = \sqrt{2}/2$ 时的正弦度量，该问题是 PP-complete 的。