Single-copy learning of noisy stabilizers by certified filtering

Overview

Abstract

We give a single-copy recovery framework for an unknown qubit stabilizer state mixed with global white noise. For every fixed ε>0, 0<γ<1 and fixed confidence, the exact target can be recovered from O(n^(1+ε)) original copies when the retained signal has a known lower bound c₀≥2^(−(log₂ n)^γ). The total number of ideal quantum operations is polynomial, while classical processing takes 2^O(n/log log n) time. A random Clifford frame and a known partial-derivative measurement reduce discovery of one complete target Pauli to classical noisy-parity search. Fresh verification and a short certified seed then amplify the signal enough for known high-fidelity single-copy learning. This avoids recovering every graph row through a noisy solver. We also obtain polynomial classical time for every fixed positive signal under a supplied fractional diagonal-subspace promise, including dense CSS states and a CSS-defect class. The latter uses finite-field subspace recovery, with an explicit proof of the required fixed-weight extension. Supporting bounds distinguish partial code measurements from full-basis readout. The measurements, classical solvers and high-fidelity endpoint are established ingredients; the contribution is their operational combination and original-copy resource accounting. No general polynomial-time learner or arbitrary-noise guarantee is asserted.

Keywords stabilizer learning · single-copy measurements · global depolarization · certified filtering · learning parity with noise · CSS states