It is well-known that learning a pure
n-qubit stabilizer state
∣ψ⟩ both requires, and can be accomplished with, access to a number of copies of
∣ψ⟩ linear in
n. However, the precise constant coefficient of this scaling does not appear to have been determined. Here we prove that
Lδ(n), the smallest number of copies from which a quantum procedure can identify any stabilizer state with failure probability at most
0<δ<1/8, satisfies
n+⌈log2(1/δ)⌉−3≤Lδ(n)≤n+⌈log2(1/δ)⌉+4. We present a polynomial-time quantum learning algorithm that saturates this bound, achieving a constant factor improvement in sample-complexity over previously known approaches. As an immediate corollary, we obtain via the Choi-Jamiolkowski isomorphism an algorithm for learning an unknown
n-qubit Clifford unitary from
2n+⌈log2(1/δ)⌉+4 queries, the
n-dependence of which we show to be optimal. Our proof technique, which involves Fourier analysis on the abelian group
Z4n×F2n(n−1)/2, seems to be qualitatively different to previous approaches to stabilizer state learning, and may be of some independent interest; in particular, it admits natural generalisations to further problems in quantum learning theory.
Bell sampling is a simple yet powerful measurement primitive that has recently attracted a lot of attention, and has proven to be a valuable tool in studying stabiliser states. Unfortunately, however, it is known that Bell sampling fails when used on qu\emph{d}its of dimension
d>2. In this paper, we explore and quantify the limitations of Bell sampling on qudits, and propose new quantum algorithms to circumvent the use of Bell sampling in solving two important problems: learning stabiliser states and providing pseudorandomness lower bounds on qudits. More specifically, as our first result, we characterise the output distribution corresponding to Bell sampling on copies of a stabiliser state and show that the output can be uniformly random, and hence reveal no information. As our second result, for
d=p prime we devise a quantum algorithm to identify an unknown stabiliser state in
(Cp)⊗n that uses
O(n) copies of the input state and runs in time
O(n4). As our third result, we provide a quantum algorithm that efficiently distinguishes a Haar-random state from a state with non-negligible stabiliser fidelity. As a corollary, any Clifford circuit on qudits of dimension
d using
O(logn/logd) auxiliary non-Clifford single-qudit gates cannot prepare computationally pseudorandom quantum states.
Stabilizer states are central to quantum computing, underlying quantum error correction, benchmarking, and efficient classical simulation. Yet their learnability exhibits a striking gap: an
n-qubit stabilizer state can be learned from
Θ(n) copies using two-copy Bell measurements, whereas non-adaptive single-copy measurements require
Ω(n2) copies. Here we show that adaptivity completely closes this gap. We give a polynomial-time adaptive algorithm that learns an arbitrary
n-qubit stabilizer state from
Θ(n) single-copy Clifford measurements, matching the optimal sample complexity of Bell sampling without any multi-copy measurements. The same ideas yield a sample-optimal single-copy tolerant tester and, with
k qubits of quantum memory, the optimal testing tradeoff
Θ(n−k+1/ε) at infidelity
ε. Finally, we show that this adaptive mechanism extends beyond exact stabilizer states: states of stabilizer nullity at most
r, including states prepared by Clifford circuits with a bounded number of
T gates, can be learned using
O(n2r) single-copy measurements.
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
Θ(n2/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.
Efficiently characterizing quantum error correcting codes is a key challenge on the path to fault-tolerant quantum computation. Stabilizer codes, a central class of such codes, are defined by a set of stabilizer generators. Here, we present an algorithm that uses random single-qubit measurements to learn the stabilizer generators of any stabilizer code from
N copies of stabilizer states in its codespace, requiring no prior knowledge of the code's structure. This also enables verification that a device implements its intended code. We derive a lower bound on
N needed to recover the stabilizer generators with high probability, together with a bound on the algorithm's overall probability of success. When applied to quantum low-density parity-check (qLDPC) codes, a leading candidate for practical fault-tolerant architectures, our approach requires a number of states that scales polylogarithmically with
n, the number of qubits.
Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown
n-qudit pure state
∣ψ⟩ that has fidelity
τ with some stabilizer state, our algorithm outputs a stabilizer state
∣φ⟩ such that
∣⟨φ∣ψ⟩∣2≥τ−ε with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as
(d/τ)O(d2log(1/τ))⋅poly(n,1/ε), where the dimension
d is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime
τ>cos2(π/8), establishing a qudit analogue of the threshold-based approach in prior qubit work.