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\le t\le n$ bound the stabilizer nullity, let $\varepsilon>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 $\varepsilon$. 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\to1$. 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\le t\le 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/\varepsilon,\log(1/δ)$, with degrees and constants depending on the fixed noise promise.
AI Summary
The paper asks whether stabilizer learning from globally depolarized copies can achieve polynomial copy complexity and $2^t$-times-polynomial classical time beyond a previously established noise threshold of at most approximately $0.159$. Here $t$ bounds the underlying pure state's stabilizer nullity. The target is an unsigned commuting Pauli group containing every ideal stabilizer, with at most $\varepsilon$ additive purity loss when the observed noisy state is twirled over that group.
For every fixed noise ceiling $\lambda_{\max}<1$, the paper gives a learner using only destructive two-copy Bell measurements. With probability at least $1-\delta$, it meets this target using polynomially many copies and polynomial working storage in $n,1/\varepsilon,\log(1/\delta)$, and $2^t$ times such a polynomial classical time. Resource caps hold on every execution. The result covers $0\le t\le n$, including a single promised independent stabilizer. A known gap between nonstabilizer Pauli expectations and magnitude one yields exact unsigned recovery.
The proof combines polynomial-feature filtering at fixed relative stabilizer dimension with two Fourier-moment constructions for smaller dimensions: random spectral isolation and affine decoding at low moment, and collision sampling at high moment. Candidate radicals feed a separate Bell-data purity verifier.
The polynomial degrees and constants depend on the fixed noise promise. Even for $\lambda\le1/2$, stated construction cutoffs include $n\ge2.59\times10^{22}$ and $n\ge2^{321}$; corresponding smaller-dimensional branches use exhaustive search. The result does not provide stabilizer signs, uniform polynomial dependence on inverse noise strength, or guarantees for general noise channels.
No sign of AI-generated textStrong assumptions
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Stabilizer Learning under Global Depolarizing Noise with Polynomial Copies and 2t Time
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.
The paper asks whether stabilizer learning from globally depolarized copies can achieve polynomial copy complexity and 2t-times-polynomial classical time beyond a previously established noise threshold of at most approximately 0.159. Here t bounds the underlying pure state's stabilizer nullity. The target is an unsigned commuting Pauli group containing every ideal stabilizer, with at most ε additive purity loss when the observed noisy state is twirled over that group.
For every fixed noise ceiling λmax<1, the paper gives a learner using only destructive two-copy Bell measurements. With probability at least 1−δ, it meets this target using polynomially many copies and polynomial working storage in n,1/ε,log(1/δ), and 2t times such a polynomial classical time. Resource caps hold on every execution. The result covers 0≤t≤n, including a single promised independent stabilizer. A known gap between nonstabilizer Pauli expectations and magnitude one yields exact unsigned recovery.
The proof combines polynomial-feature filtering at fixed relative stabilizer dimension with two Fourier-moment constructions for smaller dimensions: random spectral isolation and affine decoding at low moment, and collision sampling at high moment. Candidate radicals feed a separate Bell-data purity verifier.
The polynomial degrees and constants depend on the fixed noise promise. Even for λ≤1/2, stated construction cutoffs include n≥2.59×1022 and n≥2321; corresponding smaller-dimensional branches use exhaustive search. The result does not provide stabilizer signs, uniform polynomial dependence on inverse noise strength, or guarantees for general noise channels.
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 ε 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 poly(n,t,1/ε) when the channel's total error probability is at most of order εn/t. Up to a constant total error probability (≈0.16), samples remain polynomial while classical processing costs 2t, and for any error probability below one a 4t 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.
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 Z4n×F2n(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.
Stabilizer states are central to quantum computing, underlying quantum error correction, benchmarking, and efficient classical simulation. Yet their learnability exhibits a striking gap: an n-qubit stabilizer state can be learned from Θ(n) copies using two-copy Bell measurements, whereas non-adaptive single-copy measurements require Ω(n2) copies. Here we show that adaptivity completely closes this gap. We give a polynomial-time adaptive algorithm that learns an arbitrary n-qubit stabilizer state from Θ(n) single-copy Clifford measurements, matching the optimal sample complexity of Bell sampling without any multi-copy measurements. The same ideas yield a sample-optimal single-copy tolerant tester and, with k qubits of quantum memory, the optimal testing tradeoff Θ(n−k+1/ε) at infidelity ε. Finally, we show that this adaptive mechanism extends beyond exact stabilizer states: states of stabilizer nullity at most r, including states prepared by Clifford circuits with a bounded number of T gates, can be learned using O(n2r) single-copy measurements.
We study stabilizer state testing and learning with limited coherent quantum memory. Here an algorithm sequentially receives copies of an unknown n-qubit state, but may keep only k qubits of coherent quantum memory between measurements. With unrestricted memory, seminal work of Gross, Nezami and Walter showed how to test n-qubit stabilizer states using 6 copies, which is dimension independent, unlike the learning complexity of Θ(n). We show that this testing-vs-learning separation is lost under memory constraints. More concretely we show that
(1) The sample complexity of testing stabilizer states in the k-qubit memory framework is Θ(n−k). Our upper bound goes via a novel connection to the hidden shift problem and the lower bound is proven using a novel approach to average case bounds on likelihood ratios via combinatorics of the stochastic orthogonal group.
(2) The sample complexity of learning stabilizer states with k qubits of memory, in the non-adaptive framework, is Θ(n2/k).
As a further application of our techniques, we prove an exponential lower bound for purity testing even when the memory may be left coherent throughout the protocol. Our main results identify coherent quantum memory as the resource enabling the usual separation between stabilizer testing and learning. In particular, even with k=0.99n qubits of memory, there is no constant-copy stabilizer tester; furthermore for k=cn qubits of memory (for 0<c<1), stabilizer testing is as hard as learning, with both requiring Θ(n) copies.
We consider an unknown pure stabilizer state of n qudits with a fixed prime local dimension p, together with prescribed commuting Pauli observables. Rather than learning the whole state, the learner must recover only complementary stabilizers that commute with the prescribed observables, together with their eigenvalues. Once the prescribed measurement is performed, this information and the observed outcome determine the corresponding conditional stabilizer state. We compare the number k of copies available to the learner with the number n of qudits and refer to their ratio k/n as the copy rate.
Suppose that the dimension m of the requested complementary stabilizer subspace satisfies m=βn+o(n) for a fixed 0<β≤1. If the copy rate converges to a value below one, the optimal exact recovery probabilities and verification scores converge to zero, both in the worst case and under the uniform prior. Conversely, if the number k of copies minus the number n of qudits tends to positive infinity, the entire stabilizer state can be identified with probability tending to one, and the requested complementary information can then be extracted.
Thus, restricting the learning target to the stabilizer information needed after the prescribed measurement yields no copy-rate discount.
We present an efficient protocol for learning an unknown k-local Lindblad generator on n qubits using only product-state preparations, short-time evolution, and single-qubit Pauli measurements, without prior knowledge of the interaction structure. For fixed k and a supplied weighted interaction-strength bound αˉ, the protocol estimates all Hamiltonian and dissipative Pauli--GKSL coefficients with total coefficient error at each site at most ε with probability at least 1−δ using Ok(αˉ2n2k−2ε−2log(n/δ)) samples and polylogarithmically many distinct evolution times. This guarantee requires no degree, sparsity, or tail promise. A convex optimization converts these estimates into a valid k-local Lindblad generator with diamond-norm error at most ε using Ok(αˉ2n2kε−2log(n/δ)) samples and polynomial-time classical postprocessing. With a supplied local effective-sparsity bound r and a sufficiently small sitewise subthreshold tail Ok(ε), coefficient recovery requires only Ok(αˉ2r2ε−2log(n/δ)) samples, without a supplied threshold or coefficient locations and without a coefficient-gap assumption. In particular, exactly sparse bounded-degree models have logarithmic sample dependence on n. We also provide guard-band support recovery and complementary supplied-candidate guarantees, extend the guarantees to model misspecification, and prove complementary sample-complexity lower bounds.