# Pauli error estimation via Population Recovery

Steven T. Flammia1,2 and Ryan O'Donnell3

1AWS Center for Quantum Computing, USA
2IQIM, California Institute of Technology, USA
3Computer Science Department, Carnegie Mellon University, USA

### Abstract

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 $\epsilon$ in $\ell_\infty$ using just $O(1/\epsilon^2) \log(n/\epsilon)$ 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/\epsilon)$ 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 $\le 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-\eta$. In the regime of small $\eta$ we extend our algorithm to achieve multiplicative precision $1 \pm \epsilon$ (i.e., additive precision $\epsilon \eta$) using just $O\bigl(\frac{1}{\epsilon^2 \eta}\bigr) \log(n/\epsilon)$ applications of the channel.

The term "population recovery" is usually understood in the context of biology, where an endangered species (such as the gray wolf pictured here) is protected and their numbers begin to rebound. In the context of computer science, however, it refers to the ability to learn a probability distribution given only access to noisy samples. The "population" that we wish to learn ("recover") is an unknown distribution on bit strings, and our ability to sample from this distribution is subject to independent noise, such as an erasure channel or a bit-flip channel.

In this work, we consider the problem of learning a probability distribution over Pauli operators; that is, we wish to learn a Pauli channel. Furthermore, we wish to do so using only very simple (product state) preparations and basis measurements. Learning Pauli channels with minimal resources is important for learning the errors in a noisy quantum computer and finding better ways to fix or otherwise mitigate those errors.

Our work shows that this problem reduces to the classical problem of population recovery with a certain type of asymmetric noise. We then show that the standard algorithms known in the literature for population recovery apply unchanged to this type of noise. This gives us very sample-efficient algorithms for learning Pauli channels that use very simple state preparations and measurements.

We also show a few other interesting tidbits. First, the algorithm is naturally robust to certain types of additional measurement noise. We can also extend the algorithm to handle the case where most of the time only a single Pauli occurs (say, the identity Pauli), and we wish to recover the remaining population with a precision that is relative to the frequency of the remainder population (a more stringent task). We show an interesting connection to Fourier analysis on boolean variables. Finally, we give an open source implementation in Julia of one of the algorithms.

### ► References

[1] F. Ban, X. Chen, A. Freilich, R. Servedio, and S. Sinha. Beyond trace reconstruction: Population recovery from the deletion channel. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science, pages 745–768, 2019, arXiv:1904.05532.
https:/​/​doi.org/​10.1109/​FOCS.2019.00050
arXiv:1904.05532

[2] F. Ban, X. Chen, R. A. Servedio, and S. Sinha. Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions. In D. Achlioptas and L. A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/​RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 44:1–44:18, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, arXiv:1907.05964.
https:/​/​doi.org/​10.4230/​LIPIcs.APPROX-RANDOM.2019.44
arXiv:1907.05964

[3] L. Batman, R. Impagliazzo, C. Murray, and R. Paturi. Finding heavy hitters from lossy or noisy data. In Proceedings of the 16th Annual International Conference on Approximation Algorithms for Combinatorial Optimization Problems, pages 347–362, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-40328-6_25

[4] C. H. Bennett and S. J. Wiesner. Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states. Phys. Rev. Lett., 69:2881–2884, Nov 1992.
https:/​/​doi.org/​10.1103/​PhysRevLett.69.2881

[5] C. L. Canonne. A short note on learning discrete distributions, 2020, arXiv:2002.11457.
arXiv:2002.11457

[6] C. Dankert. Efficient Simulation of Random Quantum States and Operators. PhD thesis, University of Waterloo, 2015, arXiv:quant-ph/​0512217.
arXiv:quant-ph/0512217

[7] A. De, R. O'Donnell, and R. Servedio. Sharp bounds for population recovery. Theory of Computing, 16(6):1–20, 2020, arXiv:1703.01474.
https:/​/​doi.org/​10.4086/​toc.2020.v016a006
arXiv:1703.01474

[8] A. De, M. Saks, and S. Tang. Noisy population recovery in polynomial time. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, pages 675–684, 2016, arXiv:1602.07616.
https:/​/​doi.org/​10.1109/​FOCS.2016.77
arXiv:1602.07616

[9] Z. Dvir, A. Rao, A. Wigderson, and A. Yehudayoff. Restriction access. In Proceedings of the 3nd Annual Innovations in Theoretical Computer Science, pages 19–33, 2012.
https:/​/​doi.org/​10.1145/​2090236.2090239

[10] S. Flammia and J. Wallman. Efficient estimation of Pauli channels. ACM Transactions on Quantum Computing, 1(1):1–32, 2020, arXiv:1907.12976.
https:/​/​doi.org/​10.1145/​3408039
arXiv:1907.12976

[11] S. T. Flammia. PauliPopRec, Github repository, 2021.
https:/​/​doi.org/​10.5281/​ZENODO.5327656

[12] A. Fujiwara and H. Imai. Quantum parameter estimation of a generalized Pauli channel. Journal of Physics A: Mathematical and General, 36(29):8093–8103, jul 2003.
https:/​/​doi.org/​10.1088/​0305-4470/​36/​29/​314

[13] O. Goldreich and L. Levin. A hard-core predicate for all one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 25–32, 1989.
https:/​/​doi.org/​10.1145/​73007.73010

[14] R. Harper, S. T. Flammia, and J. J. Wallman. Efficient learning of quantum noise. Nature Physics, 16(12):1184–1188, Aug 2020, arXiv:1907.13022.
https:/​/​doi.org/​10.1038/​s41567-020-0992-8
arXiv:1907.13022

[15] R. Harper, W. Yu, and S. T. Flammia. Fast estimation of sparse quantum noise. PRX Quantum, 2(1):010322, Feb 2021, arXiv:2007.07901.
https:/​/​doi.org/​10.1103/​PRXQuantum.2.010322
arXiv:2007.07901

[16] M. Hayashi. Quantum Information Theory. Springer Berlin Heidelberg, 2nd edition, 2017.
https:/​/​doi.org/​10.1007/​978-3-662-49725-8

[17] J. Helsen, X. Xue, L. M. K. Vandersypen, and S. Wehner. A new class of efficient randomized benchmarking protocols. npj Quantum Information, 5(1):71, Aug. 2019, arXiv:1806.02048.
https:/​/​doi.org/​10.1038/​s41534-019-0182-7
arXiv:1806.02048

[18] E. Knill. Quantum computing with realistically noisy devices. Nature, 434(7029):39–44, mar 2005, arXiv:quant-ph/​0410199.
https:/​/​doi.org/​10.1038/​nature03350
arXiv:quant-ph/0410199

[19] S. Lovett and J. Zhang. Improved noisy population recovery, and reverse Bonami–Beckner inequality for sparse functions. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pages 137–142, 2015.
https:/​/​doi.org/​10.1145/​2746539.2746540

[20] S. Lovett and J. Zhang. Noisy population recovery from unknown noise. In Conference on Learning Theory, pages 1417–1431, 2017.

[21] A. Moitra and M. Saks. A polynomial time algorithm for lossy population recovery. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pages 110–116, 2013, arXiv:1302.1515.
https:/​/​doi.org/​10.1109/​FOCS.2013.20
arXiv:1302.1515

[22] A. Montanaro and T. J. Osborne. Quantum Boolean functions. Chicago Journal of Theoretical Computer Science, 2010(1):1–45, January 2010, arXiv:0810.2435.
https:/​/​doi.org/​10.4086/​cjtcs.2010.001
arXiv:0810.2435

[23] S. Narayanan. Improved algorithms for population recovery from the deletion channel. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1259–1278. Society for Industrial and Applied Mathematics, Jan. 2021, arXiv:2004.06828.
https:/​/​doi.org/​10.1137/​1.9781611976465.77
arXiv:2004.06828

[24] R. O'Donnell. Analysis of Boolean functions. Cambridge University Press, 2014, arXiv:2105.10386.
https:/​/​doi.org/​10.1017/​CBO9781139814782
arXiv:2105.10386

[25] Y. Polyanskiy, A. T. Suresh, and Y. Wu. Sample complexity of population recovery. In S. Kale and O. Shamir, editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1589–1618, Amsterdam, Netherlands, 07–10 Jul 2017. PMLR, arXiv:1702.05574.
arXiv:1702.05574

[26] B. Terhal. Quantum error correction for quantum memories. Reviews of Modern Physics, 87(2):307, 2015, arXiv:1302.3428.
https:/​/​doi.org/​10.1103/​RevModPhys.87.307
arXiv:1302.3428

[27] J. ur Rehman and H. Shin. Entanglement-free parameter estimation of generalized Pauli channels. Quantum, 5:490, Jul 2021, arXiv:2102.00740.
https:/​/​doi.org/​10.22331/​q-2021-07-01-490
arXiv:2102.00740

[28] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge University Press, 2019.
https:/​/​doi.org/​10.1017/​9781108627771

[29] J. Wallman and J. Emerson. Noise tailoring for scalable quantum computation via randomized compiling. Physical Review A, 94(5):052325, 2016, arXiv:1512.01098.
https:/​/​doi.org/​10.1103/​PhysRevA.94.052325
arXiv:1512.01098

[30] A. Wigderson and A. Yehudayoff. Population recovery and partial identification. Machine Learning, 102(1):29–56, 2016.
https:/​/​doi.org/​10.1007/​s10994-015-5489-9

### Cited by

[1] Yunchao Liu, Matthew Otten, Roozbeh Bassirianjahromi, Liang Jiang, and Bill Fefferman, "Benchmarking near-term quantum computers via random circuit sampling", arXiv:2105.05232.

[2] Thomas Wagner, Hermann Kampermann, Dagmar Bruß, and Martin Kliesch, "Pauli channels can be estimated from syndrome measurements in quantum error correction", arXiv:2107.14252.

[3] Steven T. Flammia, "Averaged circuit eigenvalue sampling", arXiv:2108.05803.

[4] Senrui Chen, Sisi Zhou, Alireza Seif, and Liang Jiang, "Quantum advantages for Pauli channel estimation", arXiv:2108.08488.

The above citations are from SAO/NASA ADS (last updated successfully 2021-10-22 16:46:51). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2021-10-22 16:46:50).