arXiv:2607.02444quant-phcs.CC2026-07被引 2

受限量子内存下,稳定态测试与学习复杂度趋同,内存是关键资源。

Optimal Stabilizer Testing and Learning with Limited Quantum Memory

论文配图:Optimal Stabilizer Testing and Learning with Limited Quantum Memory
图 1 · 摘自论文原文
  • 通过关联隐移问题设计新测试算法,实现最优样本复杂度。
  • 内存为 $k$ 时,测试需 $Θ(n-k)$ 个样本,学习需 $Θ(n^2/k)$ 个。
  • 揭示内存限制打破测试与学习的分离,适合量子信息理论研究者。

我们研究在有限相干量子内存约束下的稳定态测试与学习。算法逐次接收未知 $n$-量子比特态的副本,但每次测量间仅能保留 $k$ 个量子比特的相干记忆。无内存限制时,Gross、Nezami 与 Walter 的工作表明,仅需 6 个样本即可测试 $n$-量子比特稳定态,且与维度无关;而学习复杂度为 $Θ(n)$。但在内存受限情况下,这一分离消失。本文证明:(1) 在 $k$-量子比特内存框架下,稳定态测试的样本复杂度为 $Θ(n-k)$,上界基于与隐移问题的新关联,下界通过组合学方法分析随机正交群上的似然比平均界;(2) 在非自适应框架中,$k$ 量子比特内存下稳定态学习的复杂度为 $Θ(n^2/k)$。进一步应用表明,即使全程保持相干记忆,纯度测试仍存在指数级下界。核心结论:相干量子内存是维持稳定态测试与学习分离的关键资源。即使 $k=0.99n$,也不存在常数样本的测试器;当 $k=cn$($0<c<1$)时,测试与学习均需 $Θ(n)$ 个样本,复杂度等价。

原文摘要 · Abstract (English)

We study stabilizer state testing and learning with limited coherent quantum memory. Here an algorithm sequentially receives copies of an unknown $n$-qubit state, but may keep only $k$ qubits of coherent quantum memory between measurements. With unrestricted memory, seminal work of Gross, Nezami and Walter showed how to test $n$-qubit stabilizer states using $6$ copies, which is dimension independent, unlike the learning complexity of $Θ(n)$. We show that this testing-vs-learning separation is lost under memory constraints. More concretely we show that (1) The sample complexity of testing stabilizer states in the $k$-qubit memory framework is $Θ(n-k)$. Our upper bound goes via a novel connection to the hidden shift problem and the lower bound is proven using a novel approach to average case bounds on likelihood ratios via combinatorics of the stochastic orthogonal group. (2) The sample complexity of learning stabilizer states with $k$ qubits of memory, in the non-adaptive framework, is $Θ(n^2/k)$. As a further application of our techniques, we prove an exponential lower bound for purity testing even when the memory may be left coherent throughout the protocol. Our main results identify coherent quantum memory as the resource enabling the usual separation between stabilizer testing and learning. In particular, even with $k=0.99n$ qubits of memory, there is no constant-copy stabilizer tester; furthermore for $k=cn$ qubits of memory (for $0< c < 1$), stabilizer testing is as hard as learning, with both requiring $Θ(n)$ copies.

量子测试稳定态内存限制学习复杂度

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。