---
title: "有限量子记忆下的最优稳定子态测试与学习"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2607.02444v1"
permalink: "https://feed.astralor.com/items/itm_150efbfb2edc6e9e7dc3a6fc"
published: "2026-07-02T17:11:38.000Z"
score: 59
channel: "tech"
tags: ["样本复杂度","稳定子态","量子学习","量子测试","量子记忆"]
---

# 有限量子记忆下的最优稳定子态测试与学习

## 速览

该论文研究了在有限相干量子记忆下对n量子比特稳定子态进行测试与学习的问题。作者发现，当记忆受限时，稳定子态测试与学习之间的样本复杂度分离消失。具体地，在k量子比特记忆框架下，测试的样本复杂度为Θ(n-k)，而非适应性学习的样本复杂度为Θ(n²/k)。此外，论文还证明即使在整个协议中保持记忆相干，纯度测试的样本复杂度也有指数级下界。主要结论揭示了相干量子记忆是导致稳定子态测试与学习分离的关键资源。

## 关键点

- 测试稳定子态所需样本数与可用量子记忆大小k线性相关：Θ(n-k)。
- 非适应性学习稳定子态的样本复杂度为Θ(n²/k)，远高于测试。
- 纯度测试即使在全记忆相干条件下也需要指数级样本数。
- 相干量子记忆是稳定子态测试与学习性能分离的根本资源。

## 全文

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.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_150efbfb2edc6e9e7dc3a6fc