研究非独立同分布下的假设检验，发现量子场景下仅需单拷贝即可高效验证状态平均。
Non-iid hypothesis testing: from classical to quantum
- 针对非独立分布的样本设计新检验方法，突破经典情形下所需样本数限制。
- 量子场景中仅用每个态1个拷贝，即可在T ≫ d/ε²条件下区分平均态与目标态。
- 揭示量子优势：经典不可行的问题在量子框架下可解，适合量子信息研究者。
我们研究非独立同分布下的假设检验（又称状态认证）问题。近期工作（Garg等，2023）考虑了经典情形：给定T个未知概率分布 $p_1, \\. p_T$ on $[d]$，每个分布提供 $c = 2$ 个独立样本，目标是判断其平均分布 $p_{\mathrm{avg}}$ 是否等于已知分布 $q$。当 $T \gg \frac{\sqrt{d}}{ε^2} + \frac{1}{ε^4}$ 时，可以以高概率区分 $p_{\mathrm{avg}} = q$ 与 $d_{\mathrm{TV}}(p_{\mathrm{avg}},q) > ε$，接近经典iid情形的最优界。本文进一步优化该结果并推广至容错测试。更重要的是，我们研究了非独立量子态的类似问题：对于任意$d$维目标态 $σ$，若每个未知态 $ρ_1, \\. ρ_T$ 仅提供一个拷贝 ($c = 1$)，则当 $T \gg d/ε^2$ 时，仍可区分 $ρ_{\mathrm{avg}} = σ$ 与 $D_{\mathrm{tr}}(ρ_{\mathrm{avg}},σ) > ε$。此结果匹配iid情形的最优界，而经典情况下 $c=1$ 明确不可能。我们还证明了该现象在非独立身份测试中同样成立。技术上引入了量子版Efron-Stein不等式与分解，可能具有独立价值。
原文摘要 · Abstract (English)
We study hypothesis testing (aka state certification) in the non-identically distributed setting. A recent work (Garg et al. 2023) considered the classical case, in which one is given (independent) samples from $T$ unknown probability distributions $p_1, \dots, p_T$ on $[d] = \{1, 2, \dots, d\}$, and one wishes to accept/reject the hypothesis that their average $p_{\mathrm{avg}}$ equals a known hypothesis distribution $q$. Garg et al. showed that if one has just $c = 2$ samples from each $p_i$, and provided $T \gg \frac{\sqrt{d}}{ε^2} + \frac{1}{ε^4}$, one can (whp) distinguish $p_{\mathrm{avg}} = q$ from $d_{\mathrm{TV}}(p_{\mathrm{avg}},q) > ε$. This nearly matches the optimal result for the classical iid setting (namely, $T \gg \frac{\sqrt{d}}{ε^2}$). Besides optimally improving this result (and generalizing to tolerant testing with more stringent distance measures), we study the analogous problem of hypothesis testing for non-identical quantum states. Here we uncover an unexpected phenomenon: for any $d$-dimensional hypothesis state $σ$, and given just a single copy ($c = 1$) of each state $ρ_1, \dots, ρ_T$, one can distinguish $ρ_{\mathrm{avg}} = σ$ from $D_{\mathrm{tr}}(ρ_{\mathrm{avg}},σ) > ε$ provided $T \gg d/ε^2$. (Again, we generalize to tolerant testing with more stringent distance measures.) This matches the optimal result for the iid case, which is surprising because doing this with $c = 1$ is provably impossible in the classical case. We also show that the analogous phenomenon happens for the non-iid extension of identity testing between unknown states. A technical tool we introduce may be of independent interest: an Efron-Stein inequality, and more generally an Efron-Stein decomposition, in the quantum setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。