Equivalence of non-local computation tasks beyond Clifford operations

技术摘要：超越 Clifford 操作的非局部计算任务等价性

问题陈述
非局部量子计算（NLQC）研究的是两个空间分离的参与者（Alice 和 Bob）如何仅通过单轮同步量子通信和共享纠缠，在分布式系统中实现一个联合量子信道。虽然已知任何量子信道都可以通过 NLQC 实现，但资源成本——特别是预共享纠缠的量——在不同任务之间存在显著差异。

研究 NLQC 的一个主要动机是其在量子位置验证（QPV）中的应用。在 QPV 中，证明者试图向验证者证明其物理位置。一个位于他处的欺骗性证明者必须使用 NLQC 来模拟诚实证明者的局部操作。一个 QPV 方案的安全性依赖于该 NLமாகக் NLQC 任务的难度：如果欺骗性证明者需要指数级大量的纠缠来模拟该任务，则该方案被认为是安全的。

本文解决的核心问题是缺乏对不同 NLQC 任务相对难度的统一理解。具体而言，虽然“$f$-routing”任务（经典控制的量子系统路由）已被广泛研究，但不清楚其他可能的 QPV 协议——特别是涉及受控量子测量或简单路由之外的酉操作的任务——是否能提供更高的安全性。作者旨在确定这些看似不同的任务是否可以相互归约，从而建立它们是否具有相同的渐近纠缠成本。

方法论
作者采用了一种在 NLQC 任务族之间进行**归约（Reductions）**的框架，类似于计算复杂度理论中的归约。他们定义了两种类型的归约：

1. 资源态归约（Resource State Reduction）： 如果任务 $G$ 可以使用实现任务 $F$ 所需的少量副本来实现，则称任务 $G$ 归约为任务 $F$。
2. 算子归约（Oracle Reduction）： 如果任务 $G$ 可以通过使用少量实现任务 $F$ 的黑盒算子调用，加上局部操作和少量额外的共享资源来实现，则称任务 $G$ 归约为任务 $F$。

本文侧重于 $f$-受控 2→2 任务，其中执行的操作取决于给定给 Alice ($x$) 和 Bob ($y$) 的布尔函数 $f(x, y)$。输入系统通常为常数大小（$O(1)$ 量子比特），而经典输入可以很大（$n$ 比特）。

技术方法包括：

• 门遥测（Gate Teleportation）与基于测量的量子计算（MBQC）： 作者利用受门遥测和非自适应 MBQC 启发的组件（gadgets），构建将一种 NLQC 任务转换为另一种任务的协议。
• 角度表征与操纵： 对于单量子比特测量，作者通过布洛赫球上的旋转角来表征任务。他们开发了技术，通过组合更简单的协议（例如，将带有角度 $\theta_1$ 和 $\theta_2$ 的 $f$-测量协议结合起来以模拟 $\theta_1 + \theta_2$）来添加、拆分和逼近这些角度。
• 基于端口的遥测（Port-Based Teleportation）： 用于在附录中证明量子输入的空间分布（无论是在 Alice 侧、Bob 侧还是拆分状态）在输入大小为常数的情况下，不会显著改变任务的难度。

关键贡献与结果

1. 单量子比特 $f$-测量协议的等价性：
   作者证明了所有非平凡的单量子比特 $f$-测量协议（其中测量基是在两个任意基 $U$ 和 $V$ 之间根据 $f(x,y)$ 选择）在 $O(1)$ 算子归约下是等价的。

   • 具体而言，任何 $f\text{-measure}(U, V)$ 都可以归约为规范情况 $f\text{-measure}(I, H)$（在计算基或 Hadamard 基中进行测量）。
   • 这意味着没有任何单量子比特投影测量协议能提供比最简单的 $f$-routing 更好的安全性，因为它们都继承了 $f$-routing 已知的亚指数纠缠上界。

2. 受控 Clifford 酉操作的归约：
   论文证明了 $f$-受控 Clifford 酉操作和在 Clifford 相关基下的测量可以归约为 $f\text{-measure}(I, H)$。

   • 通过建立 $f\text{-measure}(I, H)$ 与 $f\text{-Bell}$ 测量（在 Bell 基下测量）之间的等价关系，作者表明受控 Clifford 操作可以通过使用 $f\text{-Bell}$ 算子的门遥测策略来实现。
   • 这扩展了可归约为 $f$-routing 的任务类别，确认了即使是多量子比特 Clifford 受控操作，其本质上也并不比基础的路由任务需要更多的纠缠。

3. 向受控对角酉操作的扩展：
   一个重要的结果是将 形式为 $U = C_1 D C_0$ 的 $f$-受控酉操作 进行归约，其中 $C_0, C_1$ 是 Clifford 电路，$D$ 是任意对角酉操作。

   • 作者表明，$f\text{-unitary}(I, U)$ 可以通过 $O(n_Q)$ 的开销（其中 $n_Q$ 是量子比特数）归约为 $f\text{-measure}(I, H)$。
   • 这令人惊讶，因为 $D$ 可能具有很高的 T-深度，使得 $U$ 是高度非 Clifford 的。然而，其实现成本仍然与较简单的基于 Clifford 的 $f$-测量任务挂钩。
   • 该构造依赖于“Z-旋转注入组件”，该组件将受控单量子比特 X-旋转（可通过 $f$-测量实现）与通过 CZ 门实现的受控多量子比特 Z-旋转联系起来。

意义与主张
论文声称，可行的 QPV 协议图景比此前认为的更为受限。通过建立丰富的归约结构，作者证明了：

• 安全性限制： 许多提出的涉及受控单量子比特测量、Clifford 操作甚至某些非 Clifford 对角酉操作的 QPV 方案 并不能提供比基础 $f$-routing 任务更高的安全性。它们都具有相同的渐近纠缠成本缩放（在经典输入规模下是亚指数级的）。
• 统一的难度： 这些任务的相对难度是统一的；如果存在针对 $f$-routing 的亚指数攻击，则通过已建立的归约，该攻击可以扩展到这些更广泛的类别。
• 技术进步： 这项工作引入了新的 NLQC 策略，例如特定的门遥测组件和角度拆分技术，这些技术对于为其他 NLQC 任务构建纠缠成本上界可能具有独立的价值。

作者对其研究范围保持谦逊，指出虽然他们涵盖了广泛的“可行”协议（大型经典输入，小型量子输入），但是否两层对角门或其他更复杂的酉结构可以提供能够规避这些归约的高安全性水平，仍是一个悬而未决的问题。这些结果并非声称证明了超线性下界，而是阐明了许多直觉上的 $f$-routing 扩展并不能逃脱已知的上界。