Fast Estimation of Sparse Quantum Noise

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.