On State Distinguishing Without Inverse Queries

技术摘要：关于无逆向查询下的状态区分问题

问题定义

本文研究了在只能通过前向访问（forward-only access）算子这一约束下的量子态区分问题。在标准设定中，算法被给定两个迹距离为 $\epsilon$ 的态 $|\psi\rangle$ 或 $|\phi\rangle$ 的副本，并必须确定存在哪种态。虽然通过访问酉算子状态制备算子 $U$ 及其逆算子 $U^\dagger$ 可以通过振幅放大实现 $\Theta(\epsilon^{-1})$ 的查询复杂度，但在缺乏逆向算子的情况下，性能通常会退化到 $\Theta(\epsilon^{-2})$ 个副本。

作者研究了两种特定的设定，其中算子是一个无法被逆转的物理过程：

1. 离散时间设定： 一个未知的酉算子 $U$ 制备一个已知的两个态之一。算法只能获得 $U$ 的前向查询。
2. 连续时间设定： 一个未知的哈密顿量 $H$（满足 $\|H\| \le 1$）产生演化。算法可以获得任意持续时间 $t$ 的前向演化 $e^{-iHt}$，但不能应用 $e^{iHt}$（逆向演化）。

核心问题在于：在这些仅限前向的场景下，通过逆向访问获得的二次方优势（$\epsilon^{-1}$ 对比 $\epsilon^{-2}$）是否依然存在。

方法论

• 离散时间下界：
  作者强化了 Tang 和 Wright [TW25] 最近的一项结果，该结果表明区分已知态与接近的未知态需要 $\Omega(\epsilon^{-2})$ 次查询。作者证明，即使两个态都是已知的，这一下界依然成立。

  • 困难实例： 他们利用在 $d-1$ 个元素上的随机原位置换 $\pi$（固定 $|0\rangle$）构建了一个困难实例。在“YES”情况中，置换为 $P_\pi$；在“NO”情况中，置换为 $R_\epsilon P_\pi$，其中 $R_\epsilon$ 是在 $\text{span}\{|0\rangle, |1\rangle\}$ 空间内的一个微小旋转。
  • 混合论证（Hybrid Argument）： 不同于以往利用高级压缩算子技术的做法，作者采用了直接混合论证。他们利用已知的不易逆转原位置换的困难性（Fefferman 和 Kimmel [FK18]），证明算法无法在状态 $|\pi^{-1}(1)\rangle$ 上放置显著的振幅。
  • 距离分析： 他们证明了在没有能力逆转置换的情况下，两个情况之间的振幅差异不会发生相干累积。相反，差异的平方模会相加，导致总的可区分度在 $T$ 次查询后按 $\epsilon\sqrt{T}$ 的比例缩放，因此需要 $T = \Omega(\epsilon^{-2})$。

• 连续时间算法：
  对于连续时间设定，作者设计了一种算法，其总演化时间为 $O(\epsilon^{-1})$，且与维度 $d$ 无关。

  • 量子芝诺动力学（Quantum Zeno Dynamics）： 该算法通过在短时间的前向演化中穿插对子空间 $\text{span}\{|0\rangle, |1\rangle\}$ 的投影测量 $\Pi$，来防止状态泄漏到高维子空间（在该空间中，区分信号将会丢失）。
  • 收敛性： 利用温和测量引理（Gentle Measurement Lemma），他们证明随着测量次数 $n$ 的增加，演化会收敛到由投影哈密顿量 $\Pi H \Pi$ 生成的动力学过程。
  • 降至二维： 这有效地将问题简化为一个二维系统，使得区分信号可以线性累积，从而允许在仅使用前向演化的条件下实现最优的 $\Theta(\epsilon^{-1})$ 缩放。

关键结果

1. 离散时间硬度（定理 1.1）： 在足够高的维度下（$d = \Omega(\epsilon^{-8})$），通过仅限前向的酉算子算子区分两个由已知态制备的已知态，需要 $\Theta(\epsilon^{-2})$ 次查询。这证实了在离散设定中，由于缺乏逆向访问，二次方优势会丢失，即使目标态是已知的也是如此。
2. 连续时间效率（定理 1.2）： 在连续时间设定下，区分这些态仅需要 $\Theta(\epsilon^{-1})$ 的总演化时间。该结果与维度无关，并依赖于结合投影测量执行任意短时间前向演化的能力。

意义与主张

作者声称，在对固定离散酉算子的前向访问与对连续时间演化的前向访问之间存在性质上的分离。

• 离散对比连续： 虽然离散情况由于失去了二次方加速（需要 $\epsilon^{-2}$ 次查询）而受到影响，但连续类比在不需要逆向访问的情况下，依然保留了 Grover 型的加速（$\epsilon^{-1}$ 时间）。
• 方法论贡献： 作者强调，他们的离散下界是通过直接混合论证得出的，避免了以往文献中使用的复杂的“压缩算子”机制，从而简化了状态区分硬度的证明。
• 物理相关性： 这项工作解决了酉算子代表物理过程或实验室实验的情景，在这些情景中，时间反转（逆向查询）是难以实现或不可能实现的，从而为在这些现实约束下可实现性的理论边界提供了依据。

作者指出，他们的连续时间公式依赖于关于哈密顿量第一列（$H|0\rangle$）的承诺，这反映了离散问题中的承诺，但与简单地获得离散酉算子的分数次幂不同。他们总结道，尽管离散屏障是稳固的，但连续时间模型提供了一个自然的类比，即即使没有时间反转能力，量子优势依然可以存在。