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:2309.14326 · PRX Quantum

Efficient Pauli Channel Estimation with Logarithmic Quantum Memory

Sitan Chen, Weiyuan Gong

Published May 2, 2025• 6 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/prxquantum.6.020323

Related papers

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

Quantum advantages for Pauli channel estimation

Senrui Chen, Sisi Zhou, Alireza Seif +1 more

We show that entangled measurements provide an exponential advantage in sample complexity for Pauli channel estimation, which is both a fundamental problem and a practically important subroutine for benchmarking near-term quantum devices. The specific task we consider is to simultaneously learn all the eigenvalues of an $n$-qubit Pauli channel to $\ifmmode\pm\else\textpm\fi{}\ensuremath{\varepsilon}$ precision. We give an estimation protocol with an $n$-qubit ancilla that succeeds with high probability using only $O(n/{\ensuremath{\varepsilon}}^{2})$ copies of the Pauli channel, while proving that any ancilla-free protocol (possibly with adaptive control and channel concatenation) would need at least $\mathrm{\ensuremath{\Omega}}({2}^{n/3})$ rounds of measurement. We further study the advantages provided by a small number of ancillas. For the case that a $k$-qubit ancilla ($k\ensuremath{\le}n$) is available, we obtain a sample complexity lower bound of $\mathrm{\ensuremath{\Omega}}({2}^{(n\ensuremath{-}k)/3})$ for any nonconcatenating protocol, and a stronger lower bound of $\mathrm{\ensuremath{\Omega}}(n{2}^{n\ensuremath{-}k})$ for any nonadaptive, nonconcatenating protocol, which is shown to be tight. We also show how to apply the ancilla-assisted estimation protocol to a practical quantum benchmarking task in a noise-resilient and sample-efficient manner, given reasonable noise assumptions. Our results provide a practically interesting example for quantum advantages in learning and also bring insights for quantum benchmarking.

arXiv:2108.08488•Physical Review A•Mar 22, 2022•57 citations

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

Tight Bounds on Pauli Channel Learning without Entanglement

Senrui Chen, Changhun Oh, Sisi Zhou +2 more

Quantum entanglement is a crucial resource for learning properties from nature, but a precise characterization of its advantage can be challenging. In this Letter, we consider learning algorithms without entanglement to be those that only utilize states, measurements, and operations that are separable between the main system of interest and an ancillary system. Interestingly, we show that these algorithms are equivalent to those that apply quantum circuits on the main system interleaved with mid-circuit measurements and classical feedforward. Within this setting, we prove a tight lower bound for Pauli channel learning without entanglement that closes the gap between the best-known upper and lower bound. In particular, we show that Θ(2^{n}ϵ^{-2}) rounds of measurements are required to estimate each eigenvalue of an n-qubit Pauli channel to ϵ error with high probability when learning without entanglement. In contrast, a learning algorithm with entanglement only needs Θ(ϵ^{-2}) copies of the Pauli channel. The tight lower bound strengthens the foundation for an experimental demonstration of entanglement-enhanced advantages for Pauli noise characterization.

arXiv:2309.13461•Physical Review Letters•May 1, 2024•16 citations

Quantum memory advantage for quantum process tomography

Carlos Bravo-Prieto, Weiyuan Gong, Antonio Anna Mele

Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be $Θ(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$, where $d_{\mathrm{in}}$ and $d_{\mathrm{out}}$ are the channel input and output dimensions, respectively, and $\varepsilon$ is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires $Ω(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$ queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound $O(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$. Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case $d_{\mathrm{in}}=1$. By contrast, coherent protocols with quantum memory achieve query complexity $Θ(d_{\mathrm{in}}^2 d_{\mathrm{out}}^2/\varepsilon^2)$. Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.

quant-pharXiv:2607.13476•Jul 16, 2026•0 citations

Lower Bounds on Learning Pauli Channels With Individual Measurements

Omar Fawzi, Aadil Oufkir, Daniel Stilck França

Understanding the noise affecting a quantum device is of fundamental importance for scaling quantum technologies. A particularly important class of noise models is that of Pauli channels, as randomized compiling techniques can effectively bring any quantum channel to this form and are significantly more structured than general quantum channels. In this paper, we show fundamental lower bounds on the sample complexity for learning Pauli channels in diamond norm. We consider strategies that may not use auxiliary systems entangled with the input to the unknown channel and have to perform a measurement before reusing the channel. For non-adaptive algorithms, we show a lower bound of Ω(23nε−2) to learn an n-qubit Pauli channel. In particular, this shows that the recently introduced learning procedure by [1] is essentially optimal. In the adaptive setting, we show a lower bound of Ω(22.5nε−2) for ε = O(2−n), and a lower bound of Ω(22nε−2) for any ε > 0. This last lower bound holds even in a stronger model where in each step, before performing the measurement, the unknown channel may be used arbitrarily many times sequentially interspersed with unital operations.

arXiv:2301.09192•IEEE Transactions on Information Theory•Jan 9, 2025•5 citations
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.
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.
We show that entangled measurements provide an exponential advantage in sample complexity for Pauli channel estimation, which is both a fundamental problem and a practically important subroutine for benchmarking near-term quantum devices. The specific task we consider is to simultaneously learn all the eigenvalues of an nnn-qubit Pauli channel to $\ifmmode\pm\else\textpm\fi{}\ensuremath{\varepsilon}$ precision. We give an estimation protocol with an nnn-qubit ancilla that succeeds with high probability using only $O(n/{\ensuremath{\varepsilon}}^{2})$ copies of the Pauli channel, while proving that any ancilla-free protocol (possibly with adaptive control and channel concatenation) would need at least $\mathrm{\ensuremath{\Omega}}({2}^{n/3})$ rounds of measurement. We further study the advantages provided by a small number of ancillas. For the case that a kkk-qubit ancilla ($k\ensuremath{\le}n$) is available, we obtain a sample complexity lower bound of $\mathrm{\ensuremath{\Omega}}({2}^{(n\ensuremath{-}k)/3})$ for any nonconcatenating protocol, and a stronger lower bound of $\mathrm{\ensuremath{\Omega}}(n{2}^{n\ensuremath{-}k})$ for any nonadaptive, nonconcatenating protocol, which is shown to be tight. We also show how to apply the ancilla-assisted estimation protocol to a practical quantum benchmarking task in a noise-resilient and sample-efficient manner, given reasonable noise assumptions. Our results provide a practically interesting example for quantum advantages in learning and also bring insights for quantum benchmarking.
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.
Quantum entanglement is a crucial resource for learning properties from nature, but a precise characterization of its advantage can be challenging. In this Letter, we consider learning algorithms without entanglement to be those that only utilize states, measurements, and operations that are separable between the main system of interest and an ancillary system. Interestingly, we show that these algorithms are equivalent to those that apply quantum circuits on the main system interleaved with mid-circuit measurements and classical feedforward. Within this setting, we prove a tight lower bound for Pauli channel learning without entanglement that closes the gap between the best-known upper and lower bound. In particular, we show that Θ(2^{n}ϵ^{-2}) rounds of measurements are required to estimate each eigenvalue of an n-qubit Pauli channel to ϵ error with high probability when learning without entanglement. In contrast, a learning algorithm with entanglement only needs Θ(ϵ^{-2}) copies of the Pauli channel. The tight lower bound strengthens the foundation for an experimental demonstration of entanglement-enhanced advantages for Pauli noise characterization.
Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be Θ(din3dout3/ε2)Θ(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)Θ(din3​dout3​/ε2), where dind_{\mathrm{in}}din​ and doutd_{\mathrm{out}}dout​ are the channel input and output dimensions, respectively, and ε\varepsilonε is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires Ω(din3dout3/ε2)Ω(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)Ω(din3​dout3​/ε2) queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound O(din3dout3/ε2)O(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)O(din3​dout3​/ε2). Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case din=1d_{\mathrm{in}}=1din​=1. By contrast, coherent protocols with quantum memory achieve query complexity Θ(din2dout2/ε2)Θ(d_{\mathrm{in}}^2 d_{\mathrm{out}}^2/\varepsilon^2)Θ(din2​dout2​/ε2). Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.
Understanding the noise affecting a quantum device is of fundamental importance for scaling quantum technologies. A particularly important class of noise models is that of Pauli channels, as randomized compiling techniques can effectively bring any quantum channel to this form and are significantly more structured than general quantum channels. In this paper, we show fundamental lower bounds on the sample complexity for learning Pauli channels in diamond norm. We consider strategies that may not use auxiliary systems entangled with the input to the unknown channel and have to perform a measurement before reusing the channel. For non-adaptive algorithms, we show a lower bound of Ω(23nε−2) to learn an n-qubit Pauli channel. In particular, this shows that the recently introduced learning procedure by [1] is essentially optimal. In the adaptive setting, we show a lower bound of Ω(22.5nε−2) for ε = O(2−n), and a lower bound of Ω(22nε−2) for any ε > 0. This last lower bound holds even in a stronger model where in each step, before performing the measurement, the unknown channel may be used arbitrarily many times sequentially interspersed with unital operations.