Stabilizer Learning under Global Depolarizing Noise with Polynomial Copies and 2t Time
Abstract
We study learning the stabilizer structure of an unknown pure n-qubit state observed through global depolarizing noise of unknown strength, with a fixed promised upper bound below one, using destructive two-copy Bell measurements. Let 0≤ t≤ n bound the stabilizer nullity, let ε>0 be the accuracy, and let 0<δ<1 be the failure tolerance. With probability at least 1−δ, a learner must return a commuting unsigned Pauli group containing every stabilizer of the pure state; averaging conjugation by that group must decrease the purity of the observed noisy state by at most ε. Tang and Steckmann gave such a learner with polynomially many copies and 2t times polynomial time when the noise strength is below a threshold of at most about $0.16$, which tends to zero as t/n→1. They asked whether other algorithms with these resources can exceed this threshold. We answer this question affirmatively for every fixed bound on global depolarizing noise below one and every 0≤ t≤ n, including states with only one promised independent stabilizer. Our learner uses polynomially many copies and 2t times polynomial classical running time. All resource bounds hold on every execution. Their polynomial factors depend on n,1/ε,log(1/δ), with degrees and constants depending on the fixed noise promise.
Related
- Learning unknown stabilizer codes using product measurements
- Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements
- Partial Stabilizer Learning under Fixed Commuting Constraints and the Absence of a Copy-Rate Discount
- Sample-optimal learning of stabilizer states
- Optimal Stabilizer Testing and Learning with Limited Quantum Memory
BibTeX
@misc{zabokritskiy2026stabilizer,
title = {{Stabilizer Learning under Global Depolarizing Noise with Polynomial Copies and $2^t$ Time}},
author = {Aryeh Lev Zabokritskiy},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03324},
eprint = {2611.03324},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03324},
}
RIS
TY - UNPB
TI - Stabilizer Learning under Global Depolarizing Noise with Polynomial Copies and 2^t Time
AU - Aryeh Lev Zabokritskiy
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03324
UR - https://arxiv.org/abs/2611.03324
AB - We study learning the stabilizer structure of an unknown pure n-qubit state observed through global depolarizing noise of unknown strength, with a fixed promised upper bound below one, using destructive two-copy Bell measurements. Let 0≤ t≤ n bound the stabilizer nullity, let ε>0 be the accuracy, and let 0<δ<1 be the failure tolerance. With probability at least 1−δ, a learner must return a commuting unsigned Pauli group containing every stabilizer of the pure state; averaging conjugation by that group must decrease the purity of the observed noisy state by at most ε. Tang and Steckmann gave such a learner with polynomially many copies and 2^t times polynomial time when the noise strength is below a threshold of at most about $0.16$, which tends to zero as t/n→1. They asked whether other algorithms with these resources can exceed this threshold. We answer this question affirmatively for every fixed bound on global depolarizing noise below one and every 0≤ t≤ n, including states with only one promised independent stabilizer. Our learner uses polynomially many copies and 2^t times polynomial classical running time. All resource bounds hold on every execution. Their polynomial factors depend on n,1/ε,log(1/δ), with degrees and constants depending on the fixed noise promise.
ER -