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.
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.
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(n1/3) unentangled state preparations and measurements, improving on previous SPAM-tolerant algorithms that had 2n-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) uses of the channel.
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.
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.
Error mitigation in a noisy quantum device requires a very good estimate of the noise channel. The accuracy of probabilistic error cancellation is often limited by the high sample complexity of channel tomography. In principle, optimal sample complexity is attained by maximum likelihood estimation (MLE), but MLE is computationally challenging. We show that MLE can be made computationally tractable in certain cases of interest. For the common case of a 1D-local sparse Pauli-Lindblad channel, the likelihood function reduces to an efficiently-evaluable Bayesian network. We show that the resulting computation leads to substantially improved tomography. In addition, we demonstrate by simulation that this can lead to meaningful improvements to the overhead of error mitigation. We also discuss possible extensions of our algorithm to more general settings, such as non-1D circuits and non-Pauli errors.
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.