纯度与内积估计的样本复杂度

《Physical Review Research》：Sample complexity of purity and inner product estimation

　　我们研究了量子纯度估计和量子内积估计这两个原型任务的样本复杂度。前者一直是实验基准测试和熵估计的关键子程序，而后者则是跨平台验证的核心任务，用于比较不同物理平台产生的未知量子态。在纯度估计中，我们需要估计未知量子态 ρ 的 tr(ρ2) 到加性误差 ε。同时，对于量子内积估计，Alice 和 Bob 需要在给定未知量子态 ρ 和 σ 的副本的情况下，使用经典通信和受限量子通信，将 tr(ρσ) 估计到加性误差 ε。我们提出了一个协议，该协议使用 k 比特单向量子通信和非纠缠局部测量，用 O(median{1/ε2, 2^(n/2)/ε, 2^(n-k)/ε2}) 个 ρ 和 σ 的副本解决量子内积估计问题。我们的协议可以修改为使用 k 比特量子存储器估计未知量子态 ρ 的纯度，且具有相同的样本复杂度。我们还证明了，具有 k 比特量子存储器的任意协议将纯度估计到误差 ε 需要 Ω(median{1/ε2, 2^(n/2)/√ε, 2^(n-k)/ε2}) 个 ρ 的副本。这为具有单向 k 比特量子通信和经典通信以及非纠缠局部测量的量子内积估计提供了相同的样本复杂度下界。我们进一步改进了使用相同单副本投影值测量的任意纯度估计协议的样本复杂度下界。最后，我们研究了混合态无量子通信的量子分布式内积估计的判定变体，并提供了样本复杂度下界。

I. 引言

近年来，利用不同物理平台开发含噪中等规模量子器件取得了显著进展 [1]。对这些量子器件上的物理系统进行基准测试对于验证计算输出至关重要 [2]。然而，量子器件尺寸的不断增大使得标准验证方法（如态层析 [3,4] 和态认证 [5]）达到其能力极限，因为这些方法对系统尺寸的资源需求呈指数级增长。这些认证算法专注于将含噪量子态（过程）与已知目标进行比较。因此，开发具有可行资源需求的跨平台验证协议是可取的 [6–8]。这样的协议应直接比较不同设备产生的未知量子态，这是量子基准测试中的一项基本任务。

在这项工作中，我们专注于量子内积估计任务。这里，Alice 和 Bob 分别获得可能不同的量子态 ρ 和 σ 的副本。他们的目标是以高概率将内积 tr(ρσ) 估计到加性误差 ε 以内。当 Alice 和 Bob 能够共享任意量子通信信道时，联合交换测试足以有效估计 tr(ρσ)。然而，由于硬件限制，Alice 和 Bob 之间的量子通信在实践中是受限的。在极端情况下，当 Alice 和 Bob 仅限于局部量子操作和经典通信（LOCC）时，该任务被称为分布式量子内积估计 [9]。同一工作表明，即使允许联合局部量子测量，O(1/ε2) 个 ρ 和 σ 的副本对于将分布式内积估计求解到恒定精度 ε 是充分且必要的。对于具有低魔力和低纠缠的量子态，已提供了一种基于泡利采样的高效内积估计算法 [10]。文献 [11] 中提供了该协议在不同现有量子平台之间的实验演示。文献 [12] 中提出了另一种使用深度学习的跨平台协议。

II. 内积与纯度估计之间的联系

最近在实现量子局域网方面的实验进展 [13–15] 使得具有量子通信信道的跨平台验证方案成为可能 [16]。这些平台之间的量子线路容量受到联合交换测试所需的 n 比特量子通信信道的限制。然而，迄今为止，对于有界量子通信的跨平台验证的复杂性还没有严格的理论理解。这促使我们根据量子通信来表征样本复杂度 [17]。形式上，我们研究以下任务的复杂性：

问题 1（具有 k 比特单向量子通信的内积估计）。Alice 和 Bob 分别获得未知量子态 ρ 和 σ 的 N 个副本。在每一轮测量中，Alice 和 Bob 各自访问 ρ 和 σ 的一个副本，并且能够执行 k 比特单向量子通信和任意单向经典通信。目标是将量子内积 tr(ρσ) 估计到加性误差 ε 以内。

在这里，我们关注 Alice 和 Bob 仅允许执行非纠缠（即单副本）局部测量的方案，因为这足以在 k=0 时为分布式量子内积估计提供最优样本复杂度 O(1/ε2) [9]，并且局部联合测量在实验中相对不切实际。此外，我们假设 Alice 和 Bob 之间的通信限于从 Alice 到 Bob 的单向通信。允许 Alice 和 Bob 具有任意 k 比特量子通信和经典通信的设置超出了本工作的范围，仍然是一个开放问题。

虽然在分布式环境中测试多个量子系统的属性与测试单个系统非常不同，但我们展示了不同测量方案中纯度估计和量子内积估计的样本复杂度之间的强联系。纯度估计，即在给定 ρ 的副本的情况下将纯度 tr(ρ2) 估计到加性误差 ε，是许多量子信息问题中的关键子程序，例如量子基准测试 [2] 和近期设备上量子 Rényi 熵的实验估计 [18]。正如文献 [9] 所指出的，用于分布式内积估计的单副本协议（对应于 k=0 的问题 1）表明了用于纯度估计的单副本协议。此外，通过设置 σ=ρ，我们可以观察到问题 1 的任何算法都表明在 Alice 和 Bob 之间具有有界单向量子通信的分布式 tr(ρσ) 估计算法。因此，自然要问我们是否可以在问题 1 和无通信纯度估计设置之间展示样本复杂度的联系。

我们通过展示具有 k 比特单向量子通信的量子内积估计（问题 1）和具有 k 比特量子存储器的纯度估计（如图 1 所示）具有相同的样本复杂度缩放，肯定地回答了这个问题。后者定义如下：

图 1. （a）具有 k 比特单向量子通信和任意经典单向通信的量子内积估计模型（问题 1）与（b）具有 k 比特量子存储器的纯度估计模型（问题 2）的比较。

问题 2（具有 k 比特量子存储器的纯度估计，非正式）。给定未知量子态 ρ 的 N 个副本，目标是将 tr(ρ2) 估计到加性误差 ε 以内。该算法可以一次取两个 ρ 的副本，并维护 k 个工作比特和 k 比特量子存储器来存储数据。在每一轮中，算法首先对第一个副本进行量子测量，并将测量后状态的 k 比特存储在量子存储器中。然后，算法对第二个副本的 n 比特和量子存储器进行量子测量。

关于未知量子态纯度估计的现有结果，众所周知的算法包括基于单副本测量的随机基准测试（样本复杂度 O(1/ε2)）和基于两副本测量的交换测试（样本复杂度 O(1/ε2)）。文献 [19] 中还提供了单副本纯度估计协议的 Ω(1/ε2) 样本复杂度下界。然而，对于无辅助协议的最优 ε 依赖性仍存在差距。理解有界量子存储器与无界量子存储器之间纯度估计的量子存储器权衡也是一个悬而未决的问题，最近一系列工作对此进行了广泛研究，以理解量子设备的近期约束与各种量子学习任务的算法之间的关系以及潜在的统计复杂性。文献 [20] 首次证明了有无量子存储器的混合性测试之间存在多项式样本复杂度差距。后续工作 [21–26] 进一步证明了量子存储器在各种任务中的指数分离，包括影子层析、酉学习、纯度测试和量子动力学学习。特别地，量子存储器中的量子比特数与泡利可观测值估计之间的关系已在文献 [24,27] 中完全刻画。其他任务如纯度测试 [27] 和泡利信道特征值估计 [28,29] 也揭示了存储器-样本权衡。此外，最近提出了一个表现出量子存储器权衡的经典学习问题 [30]。

我们注意到，与文献 [24,27] 中具有 k 比特量子存储器的学习定义（可以接受 N 次对 ρ 的 oracle 访问，并在对 ρ 的最终测量之前将数据存储在量子存储器中）相比，这里的定义遵循文献 [27] 中具有两副本测量和 k 比特量子存储器的学习定义，该定义只允许在每轮中使用至多两个 ρ 的副本（详见定义 5）。这种测量设置在实验中更可行，并且与两个平台之间具有非纠缠局部测量的内积估计任务存在联系。

III. 上界

如上所述（并在附录 B 中严格说明），我们证明了 Alice 和 Bob 共享 k 比特单向量子通信和任意单向经典通信的内积估计协议（问题 1）表明了具有 k 比特量子存储器的纯度估计协议（问题 2），且具有相同的样本复杂度缩放。因此，反过来，具有 k 比特量子存储器的纯度估计的下界表明了 Alice 和 Bob 共享 k 比特单向量子通信和任意单向经典通信的内积估计的相同缩放下界。利用这一联系，我们的第一个主要结果为问题 1 以及问题 2 提供了一个算法：

定理 1（非正式）。给定未知量子态 ρ 和 σ，以及误差参数 ε，存在一个非自适应算法，使用 O(median{1/ε2, 2^(n/2)/ε, 2^(n-k)/ε2}) 个 ρ 和 σ 的副本，解决具有 k 比特单向量子通信的内积估计问题（问题 1）。

我们的协议是分布式内积估计协议（单副本测量）[9]（给出上界 O(1/ε2)）和部分交换测试算法（详见算法 2 和附录 D 1）在 ρ 和 σ 的前 k 个量子比特上的组合（给出上界 O(2^(n-k)/ε2)）。在 k 至少为系统大小的逆多项式的范围内，上界可以进一步降低到 O(2^(n/2)/ε)。通过将纯度估计与定理 1 中的算法结合，我们可以在受限量子通信和存储器的情况下估计保真度类度量 [6,31] 和平方 Hilbert-Schmidt 距离 tr((ρ-σ)2)。

IV. 下界

给定定理 1 中的算法，自然要问该算法的最优性。我们的下一个结果为问题 2 提供了下界，从而为问题 1 提供了下界：

定理 2（非正式）。对于任何 k，任何（可能是自适应的）具有 k 比特存储器的纯度估计协议（具有单向 k 比特量子通信的内积估计）至少需要 Ω(median{1/ε2, 2^(n/2)/√ε, 2^(n-k)/ε2}) 个 ρ 的副本（以及 σ 的副本）。

详细证明在技术上很复杂，因此留待附录 C 1 和 C 2。我们证明的高层策略是将学习树框架 [24,25] 与鞅技巧 [27,29,32] 结合起来。我们将学习协议建模为决策树，深度表示样本数量，未知量子态 ρ 的任何选择对应于叶子上的一种分布。然后，我们考虑区分最大混合态 I/2^n（纯度为 1/2^n）与从系综中选择的状态 ρ，使得 tr(ρ2) 以高概率偏离 1/2^n。我们证明，除非决策树足够深，否则对应于这两种情况的叶子上的诱导概率分布在统计上不可区分。我们在定理 2 中用于证明有界量子存储器策略的纯度估计样本复杂度下界的系综与先前的工作 [20,24] 显著不同。在这些先前工作中使用学习树技术证明下界时，所考虑的区分任务是比较最大混合态和通过向最大混合态添加微小随机扰动 ρ' 构造的量子态系综，形式为 ρ = (1-α)I/2^n + α ρ'。为了确保扰动态与最大混合态至少有 ε 的偏差，扰动的幅度 α 必须至少为 Ω(ε)。然而，这一区分任务将利用学习树框架得出一个样本复杂度下界，该下界比我们的结果更宽松。相比之下，我们的随机系综是通过在扩大的希尔伯特空间中添加随机扰动并部分迹除辅助系统来构建的。我们注意到，在 \(\epsilon\) 处，定理2提供的使用单副本测量的纯度测试样本复杂度下界为 \(\Omega(1/\epsilon^2)\)。该下界弱于现有文献[9]中仅使用LOCC的分布式内积估计下界 \(\Omega(1/\epsilon)\)。然而，用于内积估计的困难实例无法直接推广到纯度估计，因为内积估计涉及不同的状态 \(\rho\) 和 \(\sigma\)，这表明后者的下界比前者更难以获得。

同样自然要问的是，纯度估计的难度是否会像量子态认证[21]那样，在不同的纯度区间内有所变化。为此，我们提供了负面证据：给定任意纯度值，我们都可以构造一个困难实例，使得在该值附近以精度 \(\epsilon\) 估计纯度时，任何使用单副本测量的策略都需要 \(\Omega(1/\epsilon^2)\) 个副本，详见附录C.3。换言之，对于使用单副本测量的策略，纯度估计的难度在任何恒定纯度值附近都是普适的。

命题1（非正式）：对于任意 \(\rho\) 和常数 \(p \in (0,1)\)，在接近 \(p\) 的纯度估计中，单副本策略需要 \(\Omega(1/\epsilon^2)\) 个样本。

首先在 \(\epsilon = \Theta(1)\) 的区间内解释这一点是有帮助的。在该区间内，对于纯度估计和内积估计，样本复杂度的下界进一步缩减为 \(\Omega(1)\)。我们的结果表明，当存在 \(m\) 比特量子存储器和量子通信时，没有任何协议能够分别超越单副本测量和带单副本局域测量的分布式内积估计所达到的样本复杂度。这种样本-存储器权衡类似于纯度测试的样本-存储器权衡[24,27,33]，后者可以通过纯度估计来解决。然而，定理2中样本复杂度下界的证明与获得 \(1/\epsilon^2\) 依赖性的方法有显著不同。对于一般的 \(\epsilon\)，该下界也可写作 \(\Omega(1/\epsilon^2)\)，可以近似理解为小精度区间 \(\epsilon = O(1)\) 下的界 \(\Omega(1)\) 与使用 \(m\) 比特量子存储器（单向量子通信）的估计权衡界 \(\Omega(1/\epsilon^2)\) 的组合。

对于无辅助系统的情况（\(m=0\)），人们可能会倾向于采用混合态测试任务[21]的困难实例，该任务测试一个态是否在迹距离意义下是最大混合态或与最大混合态相差 \(\epsilon\)。鉴于任何单副本策略的混合态测试样本复杂度下界为 \(\Omega(1/\epsilon^2)\)，我们根据迹距离与希尔伯特-施密特范数之间的 \(\sqrt{d}\) 因子来固定纯度估计的精度要求 \(\epsilon'\)，从而得到 \(\Omega(1/\epsilon^2)\) 的样本复杂度下界。然而，我们必须指出，通过这种归约所需的精度始终小于 \(\Omega(1/\sqrt{d})\)。在该区间内，通过归约到混合态测试得到的样本复杂度下界 \(\Omega(1/\epsilon^2)\) 并不是最优的，因为它始终小于我们的结果，即 \(\Omega(1/\epsilon^2)\) 且下界为 \(\Omega(1/\epsilon^2)\)。

我们注意到，与给出 \(O(1/\epsilon^2)\) 样本复杂度上界的定理1相比，定理2中的下界与上界中的 \(1/\epsilon^2\) 项存在一个 \(m\) 因子差距。虽然对于一般量子协议，弥合这一差距仍然是一个开放问题，但我们证明了对纯度估计（从而也对分布式内积估计）使用每次迭代中相同的投影值测量（PVM）时，可以得到一个改进的下界：

定理3（非正式）：对于任意 \(\epsilon\)，任何在每轮中使用相同单副本PVM的纯度估计和分布式内积估计协议，都需要至少 \(\Omega(1/\epsilon^2)\) 个 \(\rho\) 的副本。

尽管算法在整个协议中仅实现一个相同PVM的假设看起来过于严格，但它涵盖了已知的分布式内积估计和纯度估计算法[6,9]，并表明这些协议在此测量限制下是最优的。

虽然我们证明纯度估计下界的方法也隐含了内积估计的下界，但它对问题的判定版本几乎没有说明。特别地，这留下了高效判定两个设备是否处于相同状态的可能性，后者是跨平台验证的关键目标。我们还研究了量子分布式内积估计的判定变体，即混合态判定内积估计（DIPE）[34]。我们针对以下版本获得了最强的下界：

问题3（DIPE：哈尔随机态的凸混合）：Alice和Bob获得状态的副本，承诺以下两种情况之一成立：
（1）Alice和Bob都拥有状态 \(\rho\)，其中状态 \(\rho\) 是从 \(\mathrm{Haar}\) 测度中独立同分布（iid）抽取的。
（2）Alice拥有状态 \(\rho\)，而Bob拥有状态 \(\sigma\)，其中状态 \(\rho\) 和 \(\sigma\) 是从 \(\mathrm{Haar}\) 测度中独立同分布抽取的。
他们的目标是在仅使用LOCC的情况下，以高概率决定他们处于哪种情况。

当 \(\epsilon = 0\) 且 \(\rho\)、\(\sigma\) 为纯态时，问题3简化为判定内积估计，对于该问题，当Alice和Bob仅能使用LOCC时，已经证明 \(\Omega(1/\epsilon)\) 个副本是充分且必要的[9]。在问题3中，第一种情况下Alice和Bob状态之间的内积为 \(1\)，而在第二种情况下内积近似为 \(0\)。假设 \(\epsilon = O(1/\sqrt{d})\)，我们可以使用精度为 \(\epsilon\) 的分布式量子内积估计算法来解决它，该算法使用 \(O(1/\epsilon^2)\) 个副本。我们在附录D.2中证明了以下定理：

定理4：任何用于混合态DIPE的协议，即使允许Alice和Bob执行任意交互协议（或任意LOCC操作），也需要至少 \(\Omega(1/\epsilon^2)\) 个副本。

此外，我们在附录D.2中考虑了混合DIPE的另一个版本，其中Alice和Bob要么拥有相同的状态 \(\rho\)，要么拥有两个独立状态 \(\rho\) 和 \(\sigma\)，分别对应于两个独立的哈尔随机酉 \(U\) 和 \(V\)。对于该变体，我们限制为Alice和Bob之间的单向经典通信，但我们利用测度集中现象获得了一个特别直接的证明。

V. 展望

在本工作中，我们提出了有限量子通信和未纠缠测量下的量子内积估计协议，以及有限量子存储器下的量子纯度估计协议，并证明了它们在最多一个 \(m\) 因子意义下接近最优。在这里，我们想指出与文献[9]的以下区别和改进。首先，先前的工作关注于带经典通信的分布式内积估计任务，而我们的工作同时关注带有界量子存储器的纯度估计和带有界量子通信的分布式内积估计任务，并揭示了这两种模型之间的联系。我们用于上界和下界的算法及困难实例与先前的工作有显著不同。此外，我们还研究了无量子通信的混合态量子分布式内积估计的判定变体，并给出了样本复杂度下界。

仍有若干开放问题有待解决。在问题1中，我们考虑了Alice和Bob拥有 \(m\) 比特单向通信和单向经典通信时的量子内积估计。因此，一个自然的问题是，本工作中的下界是否适用于Alice和Bob拥有 \(m\) 比特任意量子通信和任意LOCC的情况。虽然我们的协议在 \(m\) 比特量子通信和未纠缠测量下为内积估计以及 \(m\) 比特量子存储器下为量子纯度估计提供了样本复杂度上界 \(O(1/\epsilon^2)\)，但与我们在本工作中得到的下界 \(\Omega(1/\epsilon^2)\) 之间存在一个 \(m\) 因子差距。类似的 \(m\) 因子差距也出现在混合态DIPE问题中。一个亟待解决的开放问题是找到这两个任务样本复杂度的真实 \(m\) 和 \(\epsilon\) 依赖关系。此外，我们考虑了Alice和Bob仅允许执行未纠缠局域测量，并且对于每一对 \((m, \epsilon)\) 共享 \(m\) 比特量子通信的设置。受限量子通信的另一种模型是Alice和Bob可以执行局域联合测量，但只能总共发送 \(m\) 比特量子通信。在这种模型下查看样本复杂度是很有意思的。最后，一个有趣的未来方向是探索我们的技术是否能够为其他形式为 \(\mathrm{Tr}(O \rho)\) 的分布式量子属性估计问题（其中 \(O\) 是某些两体算符）在仅有经典通信或受限量子通信的情况下提供协议或下界。