quant-phJul 2, 2026

Optimal Stabilizer Testing and Learning with Limited Quantum Memory

Authors: Srinivasan Arunachalam, Louis Schatzki

Abstract

We study stabilizer state testing and learning with limited coherent quantum memory. Here an algorithm sequentially receives copies of an unknown nn-qubit state, but may keep only kk qubits of coherent quantum memory between measurements. With unrestricted memory, seminal work of Gross, Nezami and Walter showed how to test nn-qubit stabilizer states using 66 copies, which is dimension independent, unlike the learning complexity of Θ(n)Θ(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 kk-qubit memory framework is Θ(n−k)Θ(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 kk qubits of memory, in the non-adaptive framework, is Θ(n2/k)Θ(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.99nk=0.99n qubits of memory, there is no constant-copy stabilizer tester; furthermore for k=cnk=cn qubits of memory (for 0<c<10< c < 1), stabilizer testing is as hard as learning, with both requiring Θ(n)Θ(n) copies.

Explore similar work

CardsList
Apr 16, 2026quant-ph

Cloning is as Hard as Learning for Stabilizer States

The impossibility of simultaneously cloning non-orthogonal states lies at the foundations of quantum theory. Even when allowing for approximation errors, cloning an arbitrary unknown pure state requires as many initial copies as needed to fully learn the state. Rather than arbitrary unknown states, modern quantum learning theory often considers structured classes of states and exploits such structure to develop learning algorithms that outperform general-state tomography. This raises the question: How do the sample complexities of learning and cloning relate for such structured classes? We answer this question for an important class of states. Namely, for nn-qubit stabilizer states, we show that the optimal sample complexity of cloning is Θ(n)Θ(n). Thus, also for this structured class of states, cloning is as hard as learning. To prove these results, we use representation-theoretic tools in the recently proposed Abelian State Hidden Subgroup framework and a new structured version of the recently introduced random purification channel to relate stabilizer state cloning to a variant of the sample amplification problem for probability distributions that was recently introduced in classical learning theory. This allows us to obtain our cloning lower bounds by proving new sample amplification lower bounds for classes of distributions with an underlying linear structure. Our results provide a more fine-grained perspective on No-Cloning theorems, opening up connections from foundations to quantum learning theory and quantum cryptography.
Nikhil Bansal, Matthias C. Caro, Gaurav Mahajan
Quantum LearningQuantumQuantum AlgorithmsCopying
AskPDF
Apr 24, 2026quant-ph

The Exact Replica Threshold for Nonlinear Moments of Quantum States

Joint measurements on multiple copies of a quantum state provide access to nonlinear observables such as tr⁡(ρt)\operatorname{tr}(ρ^t), but whether replica number marks a sharp information-theoretic resource boundary has remained unclear. For every fixed order t≥3t\ge 3, existing protocols show that ⌈t/2⌉\lceil t/2\rceil replicas already suffice for polynomial-sample estimation of tr⁡(ρt)\operatorname{tr}(ρ^t), yet it has remained open whether one fewer replica must necessarily incur a sample-complexity barrier growing with the dimension. We prove that this is indeed the case in the sample/copy-access model with replica-limited joint measurements: any protocol restricted to ⌈t/2⌉−1\lceil t/2\rceil-1 replicas requires dimension-growing sample complexity, while ⌈t/2⌉\lceil t/2\rceil replicas suffice by prior work. Thus the exact replica threshold for fixed-order pure moments is ⌈t/2⌉\lceil t/2\rceil. Equivalently, for fixed-order pure moments, one additional coherent replica is not merely useful but marks the exact threshold between polynomial-sample estimation and a dimension-growing regime in the replica-limited model. We further show that the same threshold law extends to a broad family of observable-weighted moments tr⁡(Oρt)\operatorname{tr}(Oρ^t), including Pauli observables and other observables with bounded operator norm and macroscopic trace norm. Coherent replica number therefore acts as a genuinely discrete resource for nonlinear quantum-state estimation.
Shuai Zeng
Optimal Sample Complexity
AskPDF
May 9, 2026quant-ph

Learning Pure Quantum States in Any Dimension (Almost) Without Regret

We extend quantum state tomography with minimal cumulative disturbance, first investigated in [arXiv:2406.18370], to arbitrary finite-dimensional pure states. A learner sequentially receives fresh copies of an unknown pure state, chooses a rank-one projector for each copy using the previous outcomes, and performs the corresponding two-outcome projective measurement. The goal is to learn the state while keeping the chosen projectors close to the unknown state in order to minimize disturbance. The qubit solution relies on the special geometry of the Bloch sphere and does not extend directly to qudits, where pure states form a curved manifold. We show that this obstruction can be overcome by working locally on the pure-state manifold. The algorithm proceeds in epochs. In each epoch, it fixes a current estimate, measures pairs of nearby rank-one projectors obtained by moving in opposite tangent directions, and takes differences of the corresponding outcomes. This gives an exact linear observation of the tangent component of the error. The resulting local linear models are combined with a robust variance-adaptive estimator and a hot-start regularization that transfers precision across epochs. For every unknown pure state in dimension dd, after TT measured copies, our protocol achieves cumulative regret O(d3log⁡2T)\mathcal{O}(d^3\log^2 T), and at each intermediate time t≤Tt\leq T its current estimate has online infidelity O(d3log⁡(T)/t)\mathcal{O}(d^3\log(T)/t). Hence, pure-state tomography with essentially no cumulative disturbance is not a peculiarity of qubits but a geometric phenomenon that persists for qudits.
Josep Lumbreras, Marco Tomamichel
QuantumO(T^Β)$ Simultaneous RegretRegret
AskPDF