Sample-optimal learning of stabilizer states
Abstract
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 ℤ4n × 𝔽2n(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.
Related
- Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements
- Optimal Stabilizer Testing and Learning with Limited Quantum Memory
- Optimal Lower Bound on the Sample Complexity of Coherent Classical Shadows for Mixed States
- Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
- A three-eighths upper bound on the stabilizer-rank exponent of face-center magic states
BibTeX
@misc{chang2026sampleoptimal,
title = {{Sample-optimal learning of stabilizer states}},
author = {Rebecca Chang and Matthias C. Caro and Martin Larocca and Maxwell West},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10974},
eprint = {2609.10974},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10974},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sample-optimal learning of stabilizer states
AU - Rebecca Chang
AU - Matthias C. Caro
AU - Martin Larocca
AU - Maxwell West
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.10974
UR - https://arxiv.org/abs/2609.10974
AB - 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+⌈log_2(1/δ)⌉−3≤ L_δ(n)≤ n+⌈log_2(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+⌈log_2(1/δ)⌉+4 queries, the n-dependence of which we show to be optimal. Our proof technique, which involves Fourier analysis on the abelian group ℤ_4^n × 𝔽_2^n(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.
ER -