我们研究了在有限相干量子内存下的稳定器状态测试与学习。算法依次接收未知的 $n$-量子比特状态的副本，但在测量之间只能保留 $k$ 个量子比特的相干量子内存。在内存不受限制的情况下，Gross、Nezami 和 Walter 的开创性工作展示了如何使用 $6$ 个副本测试 $n$-量子比特稳定器状态，这与学习复杂度 $\Theta(n)$ 不同。我们表明在内存限制下，这种测试与学习的分离被打破。具体来说，我们展示了以下两点：
-
在 $k$-量子比特内存框架下，测试稳定器状态的样本复杂度为 $\Theta(n-k)$。我们的上界通过与隐藏平移问题的创新联系得到，而下界则通过对基于随机正交群的组合学的似然比平均情况界限的新方法来证明。
-
在非自适应框架中，使用 $k$ 个量子比特内存学习稳定器状态的样本复杂度为 $\Theta(n^2/k)$。作为我们技术的进一步应用，我们证明了即使在整个协议中内存保持相干，纯度测试的指数下界。我们的主要结果识别出相干量子内存是实现稳定器测试与学习之间通常分离的资源。特别是，即使在 $k=0.99n$ 个量子比特的内存下，仍然没有常数副本的稳定器测试器；此外，对于 $k=cn$ 个量子比特的内存（其中 $0 < c < 1$），情况同样如此。
博主点评： 本文深入探讨了量子内存对稳定器状态测试与学习的影响，揭示了在相干量子内存限制下的样本复杂度变化，具有重要的理论价值和实际应用前景。相较于传统方法，该研究为量子信息处理提供了新的思路，值得关注。