技术摘要：利用最优迹距离估计算子范数距离

问题陈述

本文研究了估计两个 $n$ 量子比特量子态 $\rho_0$ 与 $\rho_1$ 之间的算子范数距离 $T_\infty(\rho_0, \rho_1)$ 的计算复杂度。该距离定义为 $T_\infty(\rho_0, \rho_1) := \frac{1}{2}\|\rho_0 - \rho_1\|_\infty$，其中 $\|\cdot\|_\infty$ 表示算子范数（最大奇异值）。

这些量子态是通过多项式规模的态制备电路 $Q_0$ 和 $Q_1$ 提供的。目标是设计量子算法，在加性误差 $\epsilon$ 内估计该距离，且其查询复杂度应与秩（以及因此与维度 $d=2^n$）无关。这解决了关于是否存在类似于经典 $\ell_\alpha$ 距离（对于 $\alpha > 1$）的秩无关界限的开放问题。

方法论

作者采用了一个结合了酉扩张（unitary dilation）、**量子化（qubitization）和最大相位估计（maximum phase estimation）**的框架。核心策略是将 Hermite 算子 $\Delta = (\rho_0 - \rho_1)/2$ 的特征值映射到酉算子的特征相位，从而通过量子相位估计技术进行高效估计。

1. 酉扩张与量子化

给定 $\rho_0$ 和 $\rho_1$ 的态制备电路，作者使用**线性算符组合（LCU）**技术和纯化密度矩阵方法，构造了 $\Delta$ 的一个酉扩张 $U_\Delta$。

• 他们定义了一个量子化酉算符 $W = U R U^\dagger R$，其中 $R$ 是一个反射算符。
• 该构造在 $\Delta$ 的特征值 $\lambda$ 与 $W$ 的特征相位 $\theta$ 之间建立了单调对应关系，具体为 $\theta = 2 \arccos(\lambda)$（在忽略全局相位的情况下）。
• 估计 $\|\Delta\|_\infty$（最大特征值模）的问题被简化为估计 $W$ 的最大特征相位。

2. “热启动”策略

相位估计中的一个关键挑战是确保输入态与目标特征空间（$\Delta$ 的顶层特征空间）具有非零的重叠。论文区分了两种情况，取决于输入态的纯度：

• 情况 1：其中一个态是纯态（热启动引理）
  当其中一个态（例如 $\rho_0 = |\psi\rangle\langle\psi|$）是纯态时，作者证明了一个结构性引理（引理 3.1）。他们表明，纯态 $|\psi\rangle$ 本身与 $\Delta$ 最大正特征值对应的唯一特征向量的平方重叠至少为 $1/2$。

  • 直觉： 由于 $\rho$ 是半正定的，$\Delta$ 在正交于 $|\psi\rangle$ 的子空间上的限制是负半定的。因此，任何正特征值都必须对应于与 $|\psi\rangle$ 有实质性重叠的特征向量。
  • 这种“热启动”允许使用具有常数重叠参数 $\gamma = 1/2$ 的最大相位估计。

• 情况 2：一般混合态（特征值缩放重叠）
  当两个态都是混合态时，无法保证常数重叠。作者推导出了一个较弱的界限（引理 4.1），表明输入态的纯化态与顶层特征空间之间的重叠随目标特征值缩放，即 $\|\Pi_{\max} |\psi_0\rangle\|^2 \ge 2\lambda_{\max}(\Delta)$。

  • 由于目标距离为 $\epsilon$，重叠量约为 $O(\epsilon)$。
  • 为了补偿这一点，算法采用了振幅放大（通过最大相位估计程序的参数隐式实现），将成功概率提升至常数水平。

核心贡献与结果

1. 单纯态的最优估计

定理 1.1： 当其中一个态为纯态时，在加性误差 $\epsilon$ 内估计 $T_\infty(\rho, |\psi\rangle\langle\psi|)$ 或迹距离 $T(\rho, |\psi\rangle\langle\psi|)$ 的量子查询复杂度为 $\Theta(1/\epsilon)$。

• 意义： 这与纯态对纯态的情况相匹配。至关重要的是，该复杂度是与秩无关的。之前的研究方法（如 van Apeldoorn 等人，Wang 和 Zhang）其查询复杂度随秩 $r$ 线性缩放（可能达到 $O(2^n)$），而本方法在常数 $\epsilon$ 下运行时间为 $\text{poly}(n)$。
• 样本复杂度： 通过样本到查询的提升（sample-to-query lifting），样本复杂度为 $\Theta(1/\epsilon^2)$。

2. 一般态的高效估计

定理 1.2： 对于一般量子态 $\rho_0, \rho_1$，存在一种量子算法可以以 $\tilde{O}(1/\epsilon^{3/2})$ 的查询复杂度估计 $T_\infty(\rho_0, \rho_1)$。

• 意义： 这改进了之前关于 $\ell_\alpha$ 距离（对于 $\alpha > 1$）的最佳上界（这些上界通常为 $O(1/\epsilon^{\alpha+1})$ 或更差）。它与已知的 $\Omega(1/\epsilon)$ 下界之间仅剩一个平方根差距。
• 样本复杂度： 样本复杂度为 $\tilde{O}(1/\epsilon^3)$。

3. 计算复杂度类结果

本文确定了承诺问题 QSD$_\infty$（测试是否 $T_\infty \ge 2/5$ 或 $\le 1/5$）的计算复杂度：

• 推论 1.3： QSD$_\infty$ 是 BQP-完全 的。
• 推论 1.4： 受限变体 OnePureQSD$_\alpha$（至少一个态为纯态）对于所有 $\alpha \in [1, \infty]$ 都是 BQP-完全 的。
• 这些结果改进了之前的 QMA 上界，并证实了估计算子范数距离在量子计算机上是高效可解的，且不需要量子见证（quantum witness）。

意义与主张

本文声称解决了关于估计算子范数距离的秩无关性的长期开放问题。

• 结构性洞察： 作者强调了算子范数距离的一个特定结构特征：当其中一个态是纯态时，该纯态作为 $\Delta$ 差分算子的顶层特征空间的“热启动”。这是一种秩-1 扰动现象，在一般混合态中并不成立。
• 效率： 所提出的估计器实现了相对于态层析法（其随维度 $d=2^n$ 缩放）的指数级加速，以及相对于之前依赖于秩的估计器的多项式级加速。
• 层级背景： 结果表明，算子范数距离（$\alpha = \infty$）——通常被视为最宽松的接近程度概念——在量子 $\ell_\alpha$ 层级中，在查询复杂度方面实际上是“最容易”的情况，比 $\alpha=2$ 或 $\alpha=3$ 等中间情况更容易。

文章最后指出，在一般混合态情况下，上界（$\tilde{O}(1/\epsilon^{3//2})$）与下界（$\Omega(1/\epsilon)$）之间仍存在平方根差距，这使得该界限的优越性成为一个开放问题。