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:2510.00230

SPAM Tolerance for Pauli Error Estimation

Ryan O’Donnell, Samvitti Sharma

Published Sep 30, 2025• 0 citations
arXivHTMLPDF

Abstract

The Pauli channel is a fundamental model of noise in quantum systems, motivating the task of Pauli error estimation. We present an algorithm that builds on the reduction to Population Recovery introduced in [FO21]. Addressing an open question from that work, our algorithm has the key advantage of robustness against even severe state preparation and measurement (SPAM) errors. To tolerate SPAM, we must analyze Population Recovery on a combined $Z$-channel/bit-flip channel, which necessitates extending the complex analysis techniques from [PSW17, DOS17]. For $n$-qubit channels, our Pauli error estimation algorithm requires only $\exp(n^{1/3})$ unentangled state preparations and measurements, improving on previous SPAM-tolerant algorithms that had $2^n$-dependence even for restricted families of Pauli channels. We also give evidence that no SPAM-tolerant method can make asymptotically fewer than $\exp(n^{1/3})$ uses of the channel.

DOI
10.48550/arxiv.2510.00230

Related papers

Pauli error estimation via Population Recovery

Steven T. Flammia, Ryan O’Donnell

Motivated by estimation of quantum noise models, we study the problem of learning a Pauli channel, or more generally the Pauli error rates of an arbitrary channel. By employing a novel reduction to the "Population Recovery" problem, we give an extremely simple algorithm that learns the Pauli error rates of an n -qubit channel to precision ϵ in ℓ∞ using just O(1/ϵ2)log⁡(n/ϵ) applications of the channel. This is optimal up to the logarithmic factors. Our algorithm uses only unentangled state preparation and measurements, and the post-measurement classical runtime is just an O(1/ϵ) factor larger than the measurement data size. It is also impervious to a limited model of measurement noise where heralded measurement failures occur independently with probability ≤1/4 .We then consider the case where the noise channel is close to the identity, meaning that the no-error outcome occurs with probability 1−η . In the regime of small η we extend our algorithm to achieve multiplicative precision 1±ϵ (i.e., additive precision ϵη ) using just O(1ϵ2η)log⁡(n/ϵ) applications of the channel.

arXiv:2105.02885•Quantum•Sep 23, 2021•30 citations

Efficient Estimation of Pauli Channels

Steven T. Flammia, Joel J. Wallman

Pauli channels are ubiquitous in quantum information, both as a dominant noise source in many computing architectures and as a practical model for analyzing error correction and fault tolerance. Here, we prove several results on efficiently learning Pauli channels and more generally the Pauli projection of a quantum channel. We first derive a procedure for learning a Pauli channel on n qubits with high probability to a relative precision ϵ using O (ϵ -2 n2 n ) measurements, which is efficient in the Hilbert space dimension. The estimate is robust to state preparation and measurement errors, which, together with the relative precision, makes it especially appropriate for applications involving characterization of high-accuracy quantum gates. Next, we show that the error rates for an arbitrary set of s Pauli errors can be estimated to a relative precision ϵ using O (ϵ -4 log s log s/ϵ) measurements. Finally, we show that when the Pauli channel is given by a Markov field with at most k -local correlations, we can learn an entire n -qubit Pauli channel to relative precision ϵ with only O k (ϵ -2 n 2 log n ) measurements, which is efficient in the number of qubits. These results enable a host of applications beyond just characterizing noise in a large-scale quantum system: they pave the way to tailoring quantum codes, optimizing decoders, and customizing fault tolerance procedures to suit a particular device.

arXiv:1907.12976•ACM Transactions on Quantum Computing•Dec 7, 2020•140 citations

Achieving the Heisenberg limit using fault-tolerant quantum error correction

Himanshu Sahu, Qian Xu, Sisi Zhou

Quantum effect enables enhanced estimation precision in metrology, with the Heisenberg limit (HL) representing the ultimate limit allowed by quantum mechanics. Although the HL is generally unattainable in the presence of noise, quantum error correction (QEC) can recover the HL in various scenarios. A notable example is estimating a Pauli-$Z$ signal under bit-flip noise using the repetition code, which is both optimal for metrology and robust against noise. However, previous protocols often assume noise affects only the signal accumulation step, while the QEC operations -- including state preparation and measurement -- are noiseless. To overcome this limitation, we study fault-tolerant quantum metrology where all qubit operations are subject to noise. We focus on estimating a Pauli-$Z$ signal under bit-flip noise, together with state preparation and measurement errors in all QEC operations. We propose a fault-tolerant metrological protocol where a repetition code is prepared via repeated syndrome measurements, followed by a fault-tolerant logical measurement. We demonstrate the existence of an error threshold, below which errors are effectively suppressed and the HL is attained.

quant-pharXiv:2601.05457•Jan 12, 2026•0 citations

Fast Estimation of Sparse Quantum Noise

Robin Harper, Wenjun Yu, Steven T. Flammia

As quantum computers approach the fault-tolerance threshold, diagnosing and characterizing the noise on large-scale quantum devices is increasingly important.One of the most important classes of noise channels is the class of Pauli channels, for reasons of both theoretical tractability and experimental relevance.Here we present a practical algorithm for estimating the s nonzero Pauli error rates in an s-sparse, n-qubit Pauli noise channel, or more generally the s largest Pauli error rates.The algorithm comes with rigorous recovery guarantees and uses only O(n 2 ) measurements, O(sn 2 ) classical processing time, and Clifford quantum circuits.We experimentally validate a heuristic version of the algorithm that uses simplified Clifford circuits on data from an IBM 14-qubit superconducting device and our open-source implementation.These data show that accurate and precise estimation of the probability of arbitrary-weight Pauli errors is possible even when the signal is 2 orders of magnitude below the measurement noise floor.

arXiv:2007.07901•PRX Quantum•Feb 10, 2021•47 citations

Biased-noise qubits: a guide to efficient fault-tolerance using the hierarchy of errors

Diego Ruiz, Jérémie Guillaud, Christophe Vuillot +1 more

Qubits with strongly biased noise, in which phase-flip errors are orders of magnitude more frequent than bit-flips, arise both naturally, as in electron and nuclear spins, and by engineering, as in stabilized cat qubits. This noise structure holds the promise of reducing the daunting hardware overhead of fault-tolerant quantum computing, but exploiting it requires physical operations that do not convert frequent phase-flips into rare bit-flips. In this review, we analyze the most prominent fault-tolerant protocols for biased-noise qubits, organized according to the available set of such bias-preserving operations. When this set is restricted to the CZ gate together with preparation and measurement in the X basis, we show that the complexity of the required syndrome extraction gadgets essentially cancels the benefit of the noise bias: at experimentally relevant error rates, one may as well ignore the bias and rely on standard error correction designed for depolarizing noise. The situation changes drastically when a bias-preserving CX gate is available: the hierarchy of errors can then be reflected in the structure of the code, with frequent phase-flips corrected by a dedicated high-threshold code and rare bit-flips by concatenation with a high-rate code. The same hierarchy also enables hardware-efficient preparation of magic states. Finally, as a bias-preserving CX is forbidden in naturally biased platforms and challenging in engineered ones, we present a measurement-based architecture in which a high-fidelity quantum non-demolition readout of multi-qubit Pauli Z operators takes its place, extending these overhead reductions to a much broader range of physical platforms.

quant-pharXiv:2607.20143•Jul 23, 2026•0 citations

Efficient Pauli Channel Estimation with Logarithmic Quantum Memory

Sitan Chen, Weiyuan Gong

In this work, we consider one of the prototypical tasks for characterizing the structure of noise in quantum devices: estimating eigenvalues of an n -qubit Pauli noise channel. Prior work [Chen , Phys. Rev. A 105, 032435 (2022)] has proved no-go theorems for this task in the practical regime in which one has a limited amount of quantum memory; i.e., any protocol with ≤ 0.99 n ancilla qubits of quantum memory must make exponentially many measurements, provided that it is . Such protocols can only interact with the channel by repeatedly preparing a state, passing it through the channel, and measuring immediately afterward. Surprisingly, in this work we show that protocols with an extremely small amount of quantum memory achieve an exponential advantage for this task. We give a protocol that can estimate any prescribed set of eigenvalues A of a Pauli channel to error ε using only O ( log  log  ( | A | ) / ε 2 ) ancilla qubits, O ~ ( n 2 / ε 2 ) measurements, and O ( n 2 | A | / ε 2 ) queries to the Pauli channel. In contrast, we show that any protocol with zero ancilla—even a concatenating one—must make Ω ( 2 n / ε 2 ) measurements. We also prove that the number of queries cannot be improved significantly: with k ancilla qubits, Ω ( 2 ( n − k ) / 3 ) queries to the channel are necessary to learn all eigenvalues, even for concatenating protocols.

arXiv:2309.14326•PRX Quantum•May 2, 2025•6 citations
The Pauli channel is a fundamental model of noise in quantum systems, motivating the task of Pauli error estimation. We present an algorithm that builds on the reduction to Population Recovery introduced in [FO21]. Addressing an open question from that work, our algorithm has the key advantage of robustness against even severe state preparation and measurement (SPAM) errors. To tolerate SPAM, we must analyze Population Recovery on a combined ZZZ-channel/bit-flip channel, which necessitates extending the complex analysis techniques from [PSW17, DOS17]. For nnn-qubit channels, our Pauli error estimation algorithm requires only exp⁡(n1/3)\exp(n^{1/3})exp(n1/3) unentangled state preparations and measurements, improving on previous SPAM-tolerant algorithms that had 2n2^n2n-dependence even for restricted families of Pauli channels. We also give evidence that no SPAM-tolerant method can make asymptotically fewer than exp⁡(n1/3)\exp(n^{1/3})exp(n1/3) uses of the channel.
Motivated by estimation of quantum noise models, we study the problem of learning a Pauli channel, or more generally the Pauli error rates of an arbitrary channel. By employing a novel reduction to the "Population Recovery" problem, we give an extremely simple algorithm that learns the Pauli error rates of an n -qubit channel to precision ϵ in ℓ∞ using just O(1/ϵ2)log⁡(n/ϵ) applications of the channel. This is optimal up to the logarithmic factors. Our algorithm uses only unentangled state preparation and measurements, and the post-measurement classical runtime is just an O(1/ϵ) factor larger than the measurement data size. It is also impervious to a limited model of measurement noise where heralded measurement failures occur independently with probability ≤1/4 .We then consider the case where the noise channel is close to the identity, meaning that the no-error outcome occurs with probability 1−η . In the regime of small η we extend our algorithm to achieve multiplicative precision 1±ϵ (i.e., additive precision ϵη ) using just O(1ϵ2η)log⁡(n/ϵ) applications of the channel.
Pauli channels are ubiquitous in quantum information, both as a dominant noise source in many computing architectures and as a practical model for analyzing error correction and fault tolerance. Here, we prove several results on efficiently learning Pauli channels and more generally the Pauli projection of a quantum channel. We first derive a procedure for learning a Pauli channel on n qubits with high probability to a relative precision ϵ using O (ϵ -2 n2 n ) measurements, which is efficient in the Hilbert space dimension. The estimate is robust to state preparation and measurement errors, which, together with the relative precision, makes it especially appropriate for applications involving characterization of high-accuracy quantum gates. Next, we show that the error rates for an arbitrary set of s Pauli errors can be estimated to a relative precision ϵ using O (ϵ -4 log s log s/ϵ) measurements. Finally, we show that when the Pauli channel is given by a Markov field with at most k -local correlations, we can learn an entire n -qubit Pauli channel to relative precision ϵ with only O k (ϵ -2 n 2 log n ) measurements, which is efficient in the number of qubits. These results enable a host of applications beyond just characterizing noise in a large-scale quantum system: they pave the way to tailoring quantum codes, optimizing decoders, and customizing fault tolerance procedures to suit a particular device.
Quantum effect enables enhanced estimation precision in metrology, with the Heisenberg limit (HL) representing the ultimate limit allowed by quantum mechanics. Although the HL is generally unattainable in the presence of noise, quantum error correction (QEC) can recover the HL in various scenarios. A notable example is estimating a Pauli-ZZZ signal under bit-flip noise using the repetition code, which is both optimal for metrology and robust against noise. However, previous protocols often assume noise affects only the signal accumulation step, while the QEC operations -- including state preparation and measurement -- are noiseless. To overcome this limitation, we study fault-tolerant quantum metrology where all qubit operations are subject to noise. We focus on estimating a Pauli-ZZZ signal under bit-flip noise, together with state preparation and measurement errors in all QEC operations. We propose a fault-tolerant metrological protocol where a repetition code is prepared via repeated syndrome measurements, followed by a fault-tolerant logical measurement. We demonstrate the existence of an error threshold, below which errors are effectively suppressed and the HL is attained.
As quantum computers approach the fault-tolerance threshold, diagnosing and characterizing the noise on large-scale quantum devices is increasingly important.One of the most important classes of noise channels is the class of Pauli channels, for reasons of both theoretical tractability and experimental relevance.Here we present a practical algorithm for estimating the s nonzero Pauli error rates in an s-sparse, n-qubit Pauli noise channel, or more generally the s largest Pauli error rates.The algorithm comes with rigorous recovery guarantees and uses only O(n 2 ) measurements, O(sn 2 ) classical processing time, and Clifford quantum circuits.We experimentally validate a heuristic version of the algorithm that uses simplified Clifford circuits on data from an IBM 14-qubit superconducting device and our open-source implementation.These data show that accurate and precise estimation of the probability of arbitrary-weight Pauli errors is possible even when the signal is 2 orders of magnitude below the measurement noise floor.
Qubits with strongly biased noise, in which phase-flip errors are orders of magnitude more frequent than bit-flips, arise both naturally, as in electron and nuclear spins, and by engineering, as in stabilized cat qubits. This noise structure holds the promise of reducing the daunting hardware overhead of fault-tolerant quantum computing, but exploiting it requires physical operations that do not convert frequent phase-flips into rare bit-flips. In this review, we analyze the most prominent fault-tolerant protocols for biased-noise qubits, organized according to the available set of such bias-preserving operations. When this set is restricted to the CZ gate together with preparation and measurement in the X basis, we show that the complexity of the required syndrome extraction gadgets essentially cancels the benefit of the noise bias: at experimentally relevant error rates, one may as well ignore the bias and rely on standard error correction designed for depolarizing noise. The situation changes drastically when a bias-preserving CX gate is available: the hierarchy of errors can then be reflected in the structure of the code, with frequent phase-flips corrected by a dedicated high-threshold code and rare bit-flips by concatenation with a high-rate code. The same hierarchy also enables hardware-efficient preparation of magic states. Finally, as a bias-preserving CX is forbidden in naturally biased platforms and challenging in engineered ones, we present a measurement-based architecture in which a high-fidelity quantum non-demolition readout of multi-qubit Pauli Z operators takes its place, extending these overhead reductions to a much broader range of physical platforms.
In this work, we consider one of the prototypical tasks for characterizing the structure of noise in quantum devices: estimating eigenvalues of an n -qubit Pauli noise channel. Prior work [Chen , Phys. Rev. A 105, 032435 (2022)] has proved no-go theorems for this task in the practical regime in which one has a limited amount of quantum memory; i.e., any protocol with ≤ 0.99 n ancilla qubits of quantum memory must make exponentially many measurements, provided that it is . Such protocols can only interact with the channel by repeatedly preparing a state, passing it through the channel, and measuring immediately afterward. Surprisingly, in this work we show that protocols with an extremely small amount of quantum memory achieve an exponential advantage for this task. We give a protocol that can estimate any prescribed set of eigenvalues A of a Pauli channel to error ε using only O ( log  log  ( | A | ) / ε 2 ) ancilla qubits, O ~ ( n 2 / ε 2 ) measurements, and O ( n 2 | A | / ε 2 ) queries to the Pauli channel. In contrast, we show that any protocol with zero ancilla—even a concatenating one—must make Ω ( 2 n / ε 2 ) measurements. We also prove that the number of queries cannot be improved significantly: with k ancilla qubits, Ω ( 2 ( n − k ) / 3 ) queries to the channel are necessary to learn all eigenvalues, even for concatenating protocols.