Learning Noise-Robust Stabilizer Structure via Bell Sampling

Bell sampling can efficiently recover the stabilizer group and nullity of pure quantum states with little magic, supporting their tomography and certification. Pauli noise generally destroys exact stabilizers, undermining existing mixed-state structure learners; agnostic tomography instead incurs exponential dependence on nullity. The ideal group nevertheless remains encoded as Pauli invariances of the noisy state.

The proposed algorithms learn this group to accuracy ε for nullity at most t. A finder–verifier method extracts structure from partly corrupted sample batches and checks candidate updates, overcoming the loss of group structure in noisy samples. Under sufficiently weak global depolarizing noise, sample and runtime costs are polynomial in n, t and 1/ε when total error is of order εn/t or smaller. Up to approximately 0.16 total error, samples remain polynomial with classical processing scaling as 2^t; any error below one permits a 4^t overhead. Arbitrary Pauli channels have corresponding regimes with stricter thresholds. For weak noise, the results narrow the gap between agnostic methods such as stabilizer bootstrapping and efficient pure-state algorithms.