In quantum systems, the Pauli channel serves as a fundamental model of noise, making Pauli error estimation a crucial task. We present an algorithm that builds upon the Population Recovery approach introduced in [FO21]. This algorithm addresses an open question from that work and boasts a key advantage of robustness against severe state preparation and measurement (SPAM) errors. To tolerate SPAM, we analyze Population Recovery on a combined $Z$-channel and bit-flip channel, necessitating the extension of 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 upon previous SPAM-tolerant algorithms that had a $2^n$ dependence even for restricted families of Pauli channels. We also provide evidence that no SPAM-tolerant method can asymptotically require fewer than $\exp(n^{1/3})$ uses of the channel.
Blogger's Review: This algorithm presents significant advancements in the field of quantum computing, particularly in noise management. By leveraging improved complex analysis methods, it drastically reduces the requirements for state preparation and measurement, offering new insights for the practical implementation of quantum computing.