量子纯度与内积估计的样本复杂度获新突破，揭示内存与通信的深层关联。
On the sample complexity of purity and inner product estimation
- 提出基于受限量子通信的内积估计协议，复用纯度估计框架。
- 实现 $O(\text{median}\{1/ε^2, 2^{n/2}/ε, 2^{n-k}/ε^2\})$ 采样复杂度。
- 首次给出单拷贝投影测量下纯度估计的紧致下界，适合量子算法设计者。
本文研究量子纯度估计与量子内积估计的样本复杂度。在纯度估计中，需以加性误差 $ε$ 估算未知量子态 $ρ$ 的 $\mathrm{tr}(ρ^2)$；在内积估计中，Alice 和 Bob 在仅使用经典通信和 $k$-量子比特单向量子通信、无纠缠局部测量的前提下，估算 $\mathrm{tr}(ρσ)$。本文揭示了受限量子内存下的纯度估计与受限量子通信下的内积估计之间的强关联。我们提出一种协议，使用 $k$-量子比特单向量子通信与无纠缠局部测量，仅需 $O(\text{median}\{1/ε^2, 2^{n/2}/ε, 2^{n-k}/ε^2\})$ 个 $ρ$ 与 $σ$ 的副本即可完成内积估计。该协议可修改为使用 $k$-量子比特量子内存的纯度估计，复杂度相同。我们证明：任意使用 $k$-量子比特量子内存、误差为 $ε$ 的纯度估计协议至少需要 $Ω(\text{median}\{1/ε^2, 2^{n/2}/\sqrt{ε}, 2^{n-k}/ε^2\})$ 个副本。这表明内积估计在相同条件下也具有同等下界。对使用相同单拷贝投影测量的纯度估计，我们进一步将下界提升至 $Ω(\max\{1/ε^2, 2^{n/2}/ε\})$。此外，我们研究了无量子通信下混合态的决策型分布式内积估计，并给出了样本复杂度下界。
原文摘要 · Abstract (English)
We study the sample complexity of the prototypical tasks quantum purity estimation and quantum inner product estimation. In purity estimation, we are to estimate $tr(ρ^2)$ of an unknown quantum state $ρ$ to additive error $ε$. Meanwhile, for quantum inner product estimation, Alice and Bob are to estimate $tr(ρσ)$ to additive error $ε$ given copies of unknown quantum state $ρ$ and $σ$ using classical communication and restricted quantum communication. In this paper, we show a strong connection between the sample complexity of purity estimation with bounded quantum memory and inner product estimation with bounded quantum communication and unentangled measurements. We propose a protocol that solves quantum inner product estimation with $k$-qubit one-way quantum communication and unentangled local measurements using $O(median\{1/ε^2,2^{n/2}/ε,2^{n-k}/ε^2\})$ copies of $ρ$ and $σ$. Our protocol can be modified to estimate the purity of an unknown quantum state $ρ$ using $k$-qubit quantum memory with the same complexity. We prove that arbitrary protocols with $k$-qubit quantum memory that estimate purity to error $ε$ require $Ω(median\{1/ε^2,2^{n/2}/\sqrtε,2^{n-k}/ε^2\})$ copies of $ρ$. This indicates the same lower bound for quantum inner product estimation with one-way $k$-qubit quantum communication and classical communication, and unentangled local measurements. For purity estimation, we further improve the lower bound to $Ω(\max\{1/ε^2,2^{n/2}/ε\})$ for any protocols using an identical single-copy projection-valued measurement. Additionally, we investigate a decisional variant of quantum distributed inner product estimation without quantum communication for mixed state and provide a lower bound on the sample complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。