Optimal Stabilizer Testing and Learning with Limited Quantum Memory

Srinivasan Arunachalam; Louis Schatzki

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 $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.

Explore similar work

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

n

-qubit stabilizer states, we show that the optimal sample complexity of cloning is

Θ(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

N$-Qubit Stabilizer States Quantum Machine Learning Post-Quantum Cryptography Clone

Ask PDF

Oct 31, 2024quant-ph

Interactive proofs for verifying (quantum) learning and testing

We consider the problem of testing and learning from data in the presence of resource constraints, such as limited memory or weak data access, which place limitations on the efficiency and feasibility of testing or learning. In particular, we ask the following question: Could a resource-constrained learner/tester use interaction with a resource-unconstrained but untrusted party to solve a learning or testing problem more efficiently than they could without such an interaction? In this work, we answer this question both abstractly and for concrete problems, in two complementary ways: For a wide variety of scenarios, we prove that a resource-constrained learner cannot gain any advantage through classical interaction with an untrusted prover. As a special case, we show that for the vast majority of testing and learning problems in which quantum memory is a meaningful resource, a memory-constrained quantum algorithm cannot overcome its limitations via classical communication with a memory-unconstrained quantum prover. In contrast, when quantum communication is allowed, we construct a variety of interactive proof protocols, for specific learning and testing problems, which allow memory-constrained quantum verifiers to gain significant advantages through delegation to untrusted provers. These results highlight both the limitations and potential of delegating learning and testing problems to resource-rich but untrusted third parties.

Matthias C. Caro, Jens Eisert, Marcel Hinsche +3

Zero-Knowledge Proofs Verifier Untrusted Input Resource-Constrained Edge Devices

Ask PDF

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

\operatorname{tr}(ρ^t)

, but whether replica number marks a sharp information-theoretic resource boundary has remained unclear. For every fixed order

t\ge 3

, existing protocols show that

\lceil t/2\rceil

replicas already suffice for polynomial-sample estimation of

\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

\lceil t/2\rceil-1

replicas requires dimension-growing sample complexity, while

\lceil t/2\rceil

replicas suffice by prior work. Thus the exact replica threshold for fixed-order pure moments is

\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

\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

N$-Qubit Stabilizer States Optimal Sample Complexity Replicator Equations

Ask PDF