Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.03307

Learning Noise-Robust Stabilizer Structure via Bell Sampling

Letian Tang, Thomas Steckmann

quant-phSubmitted Oct 2, 2026• Announced Oct 5, 2026• 0 citations
v1 · Oct 2, 2026v2 · Oct 5, 2026
arXivHTMLPDF

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.

Comments
50 pages, 9 figures, 3 tables

Related papers

Learning the stabilizer group of a Matrix Product State

Guglielmo Lami, Mario Collura

We present a novel classical algorithm designed to learn the stabilizer group -- namely the group of Pauli strings for which a state is a $\pm 1$ eigenvector -- of a given Matrix Product State (MPS). The algorithm is based on a clever and theoretically grounded biased sampling in the Pauli (or Bell) basis. Its output is a set of independent stabilizer generators whose total number is directly associated with the stabilizer nullity, notably a well-established nonstabilizer monotone. We benchmark our method on $T$-doped states randomly scrambled via Clifford unitary dynamics, demonstrating very accurate estimates up to highly-entangled MPS with bond dimension $χ\sim 10^3$. Our method, thanks to a very favourable scaling $\mathcal{O}(χ^3)$, represents the first effective approach to obtain a genuine magic monotone for MPS, enabling systematic investigations of quantum many-body physics out-of-equilibrium.

arXiv:2401.16481•Jan 29, 2024•1 citation

Agnostic learning of qudit stabilizer states

Wentao Qi, Boyan Xu, Shiguang Feng +1 more

Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown $n$-qudit pure state $|ψ\rangle$ that has fidelity $τ$ with some stabilizer state, our algorithm outputs a stabilizer state $|φ\rangle$ such that $\left| \braket{φ|ψ} \right|^2 \geq τ- \varepsilon$ with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as $(d/τ)^{O(d^2 \log(1/τ))} \cdot \mathrm{poly}(n, 1/\varepsilon)$, where the dimension $d$ is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime $τ> \cos^2(π/8)$, establishing a qudit analogue of the threshold-based approach in prior qubit work.

quant-pharXiv:2607.15559•Jul 20, 2026•0 citations

Noisy Quantum Learning Theory

Jordan Cotler, Weiyuan Gong, Ishaan Kannan

We develop a framework for learning from noisy quantum experiments in which fault-tolerant devices access uncharacterized systems through noisy couplings. Introducing the complexity class $\textsf{NBQP}$ ("noisy BQP''), we model noisy fault-tolerant quantum computers that cannot generally error-correct the oracle systems they query. Using this class, we prove that while noise can eliminate the exponential quantum learning advantages of unphysical, noiseless learners, a superpolynomial gap remains between $\textsf{NISQ}$ and fault-tolerant devices. Turning to canonical learning tasks in noisy settings, we find that the exponential two-copy advantage for purity testing collapses under local depolarizing noise. Nevertheless, we identify a setting motivated by AdS/CFT in which noise-resilient physical structure restores this quantum learning advantage. We then analyze noisy Pauli shadow tomography, deriving lower bounds characterizing how instance size, quantum memory and noise jointly control sample complexity, and design algorithms with parametrically matching scalings. We study similar tradeoffs in quantum metrology, and show that the Heisenberg-limited sensitivity of existing error-correction-based protocols persists only up to a timescale inverse-polynomial in the error rate per probe qubit. Together, our results demonstrate that the primitives underlying quantum-enhanced experiments are fundamentally fragile to noise, and that realizing meaningful quantum advantages in future experiments will require interfacing noise-robust physical properties with available algorithmic techniques.

quant-pharXiv:2512.10929•Nature Communications•Dec 12, 2025•0 citations

Unveiling the Stabilizer Group of a Matrix Product State

Guglielmo Lami, Mario Collura

We present a novel classical algorithm designed to learn the stabilizer group-namely, the group of Pauli strings for which a state is a ±1 eigenvector-of a given matrix product state (MPS). The algorithm is based on a clever and theoretically grounded biased sampling in the Pauli (or Bell) basis. Its output is a set of independent stabilizer generators whose total number is directly associated with the stabilizer nullity, notably a well-established nonstabilizer monotone. We benchmark our method on T-doped states randomly scrambled via Clifford unitary dynamics, demonstrating very accurate estimates up to highly entangled MPS with bond dimension χ∼10^{3}. Our method, thanks to a very favorable scaling O(χ^{3}), represents the first effective approach to obtain a genuine magic monotone for MPS, enabling systematic investigations of quantum many-body physics out of equilibrium.

Physical Review Letters•Jul 1, 2024•40 citations

Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements

L. Bittel, J. Eisert, W. Gong +2 more

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 $Ω(n^2)$ 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/\varepsilon)$ at infidelity $\varepsilon$. 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(n2^{r})$ single-copy measurements.

quant-pharXiv:2610.02031•Oct 2, 2026•0 citations

Efficient Noisy Quantum State and Process Tomography

Chenyang Li, Shengxin Zhuang, Yukun Zhang +4 more

Efficiently characterizing large quantum states and processes is a central yet notoriously challenging task in quantum information science, as conventional tomography methods typically require resources that grow exponentially with system size. Here, we introduce a structure-agnostic learning framework for noisy $n$-qubit quantum circuits under~i.i.d.~single-qubit noise. We first prove that quantum states with unital noise channels admit an efficient learnable representation in the logarithmic-depth regime. We then extend this framework to quantum process tomography under constant noise, deriving a unified protocol that applies to both unital and non-unital noisy channels and retains efficient guarantees for logarithmic-depth circuits. This process-learning formulation is input-agnostic and imposes no distributional assumptions on the input quantum states. We further study a more general regime with arbitrary noise strength. In this setting, low-weight Pauli propagation induces a terminal truncation whose threshold depends logarithmically on the inverse accuracy, leading to quasi-polynomial complexity and near-unit success probability in the average case. In contrast to the preceding two results, this arbitrary-noise guarantee does not impose any restriction on the circuit depth, and therefore covers arbitrary-depth circuits, including both the noiseless limit ($γ= 0$) and the strong-decoherence regime ($γ= Θ(1)$). Numerical simulations of two-dimensional Hamiltonian dynamics further demonstrate the accuracy and robustness of the approach, including for structured circuits beyond the random-circuit setting assumed in the theoretical analysis. These results provide a scalable and practically relevant route toward characterizing large-scale noisy quantum devices, addressing a key bottleneck in the development of quantum technologies.

quant-pharXiv:2603.01521•Quantum Science and Technology•Mar 3, 2026•0 citations
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 ttt. 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 ttt. 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/ε)\mathrm{poly}(n,t,1/\varepsilon)poly(n,t,1/ε) when the channel's total error probability is at most of order εn/t\varepsilon n/tεn/t. Up to a constant total error probability (≈0.16\approx 0.16≈0.16), samples remain polynomial while classical processing costs 2t2^t2t, and for any error probability below one a 4t4^t4t 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.
We present a novel classical algorithm designed to learn the stabilizer group -- namely the group of Pauli strings for which a state is a ±1\pm 1±1 eigenvector -- of a given Matrix Product State (MPS). The algorithm is based on a clever and theoretically grounded biased sampling in the Pauli (or Bell) basis. Its output is a set of independent stabilizer generators whose total number is directly associated with the stabilizer nullity, notably a well-established nonstabilizer monotone. We benchmark our method on TTT-doped states randomly scrambled via Clifford unitary dynamics, demonstrating very accurate estimates up to highly-entangled MPS with bond dimension χ∼103χ\sim 10^3χ∼103. Our method, thanks to a very favourable scaling O(χ3)\mathcal{O}(χ^3)O(χ3), represents the first effective approach to obtain a genuine magic monotone for MPS, enabling systematic investigations of quantum many-body physics out-of-equilibrium.
Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown nnn-qudit pure state ∣ψ⟩|ψ\rangle∣ψ⟩ that has fidelity τττ with some stabilizer state, our algorithm outputs a stabilizer state ∣φ⟩|φ\rangle∣φ⟩ such that ∣⟨φ∣ψ⟩∣2≥τ−ε\left| \braket{φ|ψ} \right|^2 \geq τ- \varepsilon∣⟨φ∣ψ⟩∣2≥τ−ε with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as (d/τ)O(d2log⁡(1/τ))⋅poly(n,1/ε)(d/τ)^{O(d^2 \log(1/τ))} \cdot \mathrm{poly}(n, 1/\varepsilon)(d/τ)O(d2log(1/τ))⋅poly(n,1/ε), where the dimension ddd is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime τ>cos⁡2(π/8)τ> \cos^2(π/8)τ>cos2(π/8), establishing a qudit analogue of the threshold-based approach in prior qubit work.
We develop a framework for learning from noisy quantum experiments in which fault-tolerant devices access uncharacterized systems through noisy couplings. Introducing the complexity class NBQP\textsf{NBQP}NBQP ("noisy BQP''), we model noisy fault-tolerant quantum computers that cannot generally error-correct the oracle systems they query. Using this class, we prove that while noise can eliminate the exponential quantum learning advantages of unphysical, noiseless learners, a superpolynomial gap remains between NISQ\textsf{NISQ}NISQ and fault-tolerant devices. Turning to canonical learning tasks in noisy settings, we find that the exponential two-copy advantage for purity testing collapses under local depolarizing noise. Nevertheless, we identify a setting motivated by AdS/CFT in which noise-resilient physical structure restores this quantum learning advantage. We then analyze noisy Pauli shadow tomography, deriving lower bounds characterizing how instance size, quantum memory and noise jointly control sample complexity, and design algorithms with parametrically matching scalings. We study similar tradeoffs in quantum metrology, and show that the Heisenberg-limited sensitivity of existing error-correction-based protocols persists only up to a timescale inverse-polynomial in the error rate per probe qubit. Together, our results demonstrate that the primitives underlying quantum-enhanced experiments are fundamentally fragile to noise, and that realizing meaningful quantum advantages in future experiments will require interfacing noise-robust physical properties with available algorithmic techniques.
We present a novel classical algorithm designed to learn the stabilizer group-namely, the group of Pauli strings for which a state is a ±1 eigenvector-of a given matrix product state (MPS). The algorithm is based on a clever and theoretically grounded biased sampling in the Pauli (or Bell) basis. Its output is a set of independent stabilizer generators whose total number is directly associated with the stabilizer nullity, notably a well-established nonstabilizer monotone. We benchmark our method on T-doped states randomly scrambled via Clifford unitary dynamics, demonstrating very accurate estimates up to highly entangled MPS with bond dimension χ∼10^{3}. Our method, thanks to a very favorable scaling O(χ^{3}), represents the first effective approach to obtain a genuine magic monotone for MPS, enabling systematic investigations of quantum many-body physics out of equilibrium.
Stabilizer states are central to quantum computing, underlying quantum error correction, benchmarking, and efficient classical simulation. Yet their learnability exhibits a striking gap: an nnn-qubit stabilizer state can be learned from Θ(n)Θ(n)Θ(n) copies using two-copy Bell measurements, whereas non-adaptive single-copy measurements require Ω(n2)Ω(n^2)Ω(n2) copies. Here we show that adaptivity completely closes this gap. We give a polynomial-time adaptive algorithm that learns an arbitrary nnn-qubit stabilizer state from Θ(n)Θ(n)Θ(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 kkk qubits of quantum memory, the optimal testing tradeoff Θ(n−k+1/ε)Θ(n-k+1/\varepsilon)Θ(n−k+1/ε) at infidelity ε\varepsilonε. Finally, we show that this adaptive mechanism extends beyond exact stabilizer states: states of stabilizer nullity at most rrr, including states prepared by Clifford circuits with a bounded number of TTT gates, can be learned using O(n2r)O(n2^{r})O(n2r) single-copy measurements.
Efficiently characterizing large quantum states and processes is a central yet notoriously challenging task in quantum information science, as conventional tomography methods typically require resources that grow exponentially with system size. Here, we introduce a structure-agnostic learning framework for noisy nnn-qubit quantum circuits under~i.i.d.~single-qubit noise. We first prove that quantum states with unital noise channels admit an efficient learnable representation in the logarithmic-depth regime. We then extend this framework to quantum process tomography under constant noise, deriving a unified protocol that applies to both unital and non-unital noisy channels and retains efficient guarantees for logarithmic-depth circuits. This process-learning formulation is input-agnostic and imposes no distributional assumptions on the input quantum states. We further study a more general regime with arbitrary noise strength. In this setting, low-weight Pauli propagation induces a terminal truncation whose threshold depends logarithmically on the inverse accuracy, leading to quasi-polynomial complexity and near-unit success probability in the average case. In contrast to the preceding two results, this arbitrary-noise guarantee does not impose any restriction on the circuit depth, and therefore covers arbitrary-depth circuits, including both the noiseless limit (γ=0γ= 0γ=0) and the strong-decoherence regime (γ=Θ(1)γ= Θ(1)γ=Θ(1)). Numerical simulations of two-dimensional Hamiltonian dynamics further demonstrate the accuracy and robustness of the approach, including for structured circuits beyond the random-circuit setting assumed in the theoretical analysis. These results provide a scalable and practically relevant route toward characterizing large-scale noisy quantum devices, addressing a key bottleneck in the development of quantum technologies.