arXiv:2610.03307
Learning Noise-Robust Stabilizer Structure via Bell Sampling
Letian Tang, Thomas Steckmann
Abstract
Bell sampling efficiently learns the stabilizer group, and hence the stabilizer nullity, of pure states with little magic, a primitive underlying tomography and certification of low-magic states. Real devices, however, only prepare noisy images of the target, which we model as a Pauli channel acting on the ideal state; the resulting noisy state generically has no exact Pauli stabilizers. Existing structure learners for mixed states rely on such exact stabilizers. Agnostic tomography does not, but its guarantees scale exponentially in the nullity $t$. We show that the ideal stabilizer group remains encoded in the noisy state as the set of Pauli operators under which it is invariant. We give Bell-sampling algorithms that learn the group to accuracy $\varepsilon$ for states of nullity at most $t$. The difficulty is that noisy samples break the group structure pure-state learners rely on, so more samples can erase structure rather than reveal it. We resolve this with a finder-verifier scheme that extracts stabilizer structure from partially corrupted sample batches while certifying proposed updates. For sufficiently weak global depolarizing noise, both samples and runtime are $\mathrm{poly}(n,t,1/\varepsilon)$ when the channel's total error probability is at most of order $\varepsilon n/t$. Up to a constant total error probability ($\approx 0.16$), samples remain polynomial while classical processing costs $2^t$, and for any error probability below one a $4^t$ overhead suffices. Arbitrary Pauli channels exhibit the same three regimes, with more restrictive thresholds. For weak Pauli noise, this closes much of the gap between agnostic learners such as stabilizer bootstrapping and polynomial pure-state algorithms.
AI Summary
Bell-sampling learners recover stabilizer structure efficiently for pure low-nullity states, but Pauli noise generally removes exact unit-expectation stabilizers. This paper asks whether the ideal state's unsigned stabilizer group can nevertheless be learned from noisy copies. It targets weak Pauli symmetries—operators commuting with the density matrix—which equal the ideal stabilizer group under support-preserving Pauli noise. The output is a commuting supergroup of the target whose Pauli twirl loses at most $\varepsilon$ purity, giving an approximate compression rather than full state reconstruction. For ideal nullity at most $t$, global depolarizing noise admits polynomial samples and runtime when, to leading order, $\lambda<\min\{1-2^{-1/4},n\varepsilon/(4t)\}$, where $1-2^{-1/4}\approx0.159$. Below $0.159$, samples remain polynomial with a $2^t$ classical overhead; any $\lambda<1$ permits a $4^t$ overhead, with additional noise-dependent costs. Arbitrary Pauli channels have more restrictive thresholds: polynomial runtime requires roughly $\lambda=O(\varepsilon/[t\min\{t,\ln(1/\delta)\}])$, the intermediate regime requires $O(1/t)$ noise, and the noisy regime covers $\lambda<1/2$. The algorithms combine proposals from radicals of noisy Bell-difference-sample spans with a purity-loss verifier reusing one dataset across adaptive queries. Proofs bound corruption of the radical and connect purity loss to samples escaping candidate centralizers; depolarizing-noise post-selection suppresses contamination after accepted updates. The thresholds are sufficient conditions, not optimality bounds. Noise strength denotes total error probability, so independent per-qubit noise must scale as $O(1/n)$ for the constant-total-noise guarantees. Coherent errors and noisy Bell measurements remain untreated. Simulations mainly test finders with exact purities; ideal-state reconstruction requires additional channel information.
Error found: The abstract's approximately 0.16 depolarizing-noise threshold omits its small-t/n qualification, whereas the body's leading-order sufficient threshold decreases to zero as t/n approaches one. The abstract identifies the ideal stabilizer group with all Pauli invariances of the noisy state without requiring support preservation, although arbitrary Pauli channels can erase coefficients and create additional invariances.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 57 pages, 12 figures, 3 tables