SPAM Tolerance for Pauli Error Estimation
This work addresses the open problem of robust Pauli error estimation under severe SPAM errors, which is critical for quantum error correction and noise characterization.
The authors present a SPAM-tolerant algorithm for Pauli error estimation that requires only exp(n^{1/3}) unentangled state preparations and measurements, improving on previous algorithms with 2^n dependence. They also provide a lower bound showing that asymptotically fewer than exp(n^{1/3}) channel uses is impossible.
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.