{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T04:48:01Z","timestamp":1773809281519,"version":"3.50.1"},"reference-count":30,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T00:00:00Z","timestamp":1632355200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000183","name":"US Army Research Office","doi-asserted-by":"crossref","award":["W911NF2110001"],"award-info":[{"award-number":["W911NF2110001"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]},{"name":"US National Science Foundation","award":["FET-1909310"],"award-info":[{"award-number":["FET-1909310"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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<\/mml:mi><\/mml:math>-qubit channel to precision &#x03F5;<\/mml:mi><\/mml:math> in &#x2113;<\/mml:mi>&#x221E;<\/mml:mi><\/mml:msub><\/mml:math> using just O<\/mml:mi>(<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi>2<\/mml:mn><\/mml:msup>)<\/mml:mo>log<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>n<\/mml:mi>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi>)<\/mml:mo><\/mml:math> 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<\/mml:mi>(<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi>)<\/mml:mo><\/mml:math> 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 &#x2264;<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>4<\/mml:mn><\/mml:math>.We then consider the case where the noise channel is close to the identity, meaning that the no-error outcome occurs with probability 1<\/mml:mn>&#x2212;<\/mml:mo>&#x03B7;<\/mml:mi><\/mml:math>. In the regime of small &#x03B7;<\/mml:mi><\/mml:math> we extend our algorithm to achieve multiplicative precision 1<\/mml:mn>&#x00B1;<\/mml:mo>&#x03F5;<\/mml:mi><\/mml:math> (i.e., additive precision &#x03F5;<\/mml:mi>&#x03B7;<\/mml:mi><\/mml:math>) using just O<\/mml:mi>(<\/mml:mo><\/mml:mrow>1<\/mml:mn>&#x03F5;<\/mml:mi>2<\/mml:mn><\/mml:msup>&#x03B7;<\/mml:mi><\/mml:mrow><\/mml:mfrac>)<\/mml:mo><\/mml:mrow>log<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>n<\/mml:mi>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi>)<\/mml:mo><\/mml:math> applications of the channel.<\/jats:p>","DOI":"10.22331\/q-2021-09-23-549","type":"journal-article","created":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T14:25:19Z","timestamp":1632407119000},"page":"549","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":27,"title":["Pauli error estimation via Population Recovery"],"prefix":"10.22331","volume":"5","author":[{"given":"Steven T.","family":"Flammia","sequence":"first","affiliation":[{"name":"AWS Center for Quantum Computing, USA"},{"name":"IQIM, California Institute of Technology, USA"}]},{"given":"Ryan","family":"O'Donnell","sequence":"additional","affiliation":[{"name":"Computer Science Department, Carnegie Mellon University, USA"}]}],"member":"9598","published-online":{"date-parts":[[2021,9,23]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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\u2013768, 2019, arXiv:1904.05532.","DOI":"10.1109\/FOCS.2019.00050"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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\u00e9gh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 44:1\u201344:18, Dagstuhl, Germany, 2019. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, arXiv:1907.05964.","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2019.44"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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\u2013362, 2013.","DOI":"10.1007\/978-3-642-40328-6_25"},{"key":"3","doi-asserted-by":"publisher","unstructured":"C. H. Bennett and S. J. Wiesner. Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states. Phys. Rev. Lett., 69:2881\u20132884, Nov 1992.","DOI":"10.1103\/PhysRevLett.69.2881"},{"key":"4","unstructured":"C. L. Canonne. A short note on learning discrete distributions, 2020, arXiv:2002.11457."},{"key":"5","unstructured":"C. Dankert. Efficient Simulation of Random Quantum States and Operators. PhD thesis, University of Waterloo, 2015, arXiv:quant-ph\/0512217."},{"key":"6","doi-asserted-by":"publisher","unstructured":"A. De, R. O'Donnell, and R. Servedio. Sharp bounds for population recovery. Theory of Computing, 16(6):1\u201320, 2020, arXiv:1703.01474.","DOI":"10.4086\/toc.2020.v016a006"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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\u2013684, 2016, arXiv:1602.07616.","DOI":"10.1109\/FOCS.2016.77"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Z. Dvir, A. Rao, A. Wigderson, and A. Yehudayoff. Restriction access. In Proceedings of the 3nd Annual Innovations in Theoretical Computer Science, pages 19\u201333, 2012.","DOI":"10.1145\/2090236.2090239"},{"key":"9","doi-asserted-by":"publisher","unstructured":"S. Flammia and J. Wallman. Efficient estimation of Pauli channels. ACM Transactions on Quantum Computing, 1(1):1\u201332, 2020, arXiv:1907.12976.","DOI":"10.1145\/3408039"},{"key":"10","doi-asserted-by":"publisher","unstructured":"S. T. Flammia. PauliPopRec, Github repository, 2021.","DOI":"10.5281\/ZENODO.5327656"},{"key":"11","doi-asserted-by":"publisher","unstructured":"A. Fujiwara and H. Imai. Quantum parameter estimation of a generalized Pauli channel. Journal of Physics A: Mathematical and General, 36(29):8093\u20138103, jul 2003.","DOI":"10.1088\/0305-4470\/36\/29\/314"},{"key":"12","doi-asserted-by":"publisher","unstructured":"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\u201332, 1989.","DOI":"10.1145\/73007.73010"},{"key":"13","doi-asserted-by":"publisher","unstructured":"R. Harper, S. T. Flammia, and J. J. Wallman. Efficient learning of quantum noise. Nature Physics, 16(12):1184\u20131188, Aug 2020, arXiv:1907.13022.","DOI":"10.1038\/s41567-020-0992-8"},{"key":"14","doi-asserted-by":"publisher","unstructured":"R. Harper, W. Yu, and S. T. Flammia. Fast estimation of sparse quantum noise. PRX Quantum, 2(1):010322, Feb 2021, arXiv:2007.07901.","DOI":"10.1103\/PRXQuantum.2.010322"},{"key":"15","doi-asserted-by":"publisher","unstructured":"M. Hayashi. Quantum Information Theory. Springer Berlin Heidelberg, 2nd edition, 2017.","DOI":"10.1007\/978-3-662-49725-8"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/s41534-019-0182-7"},{"key":"17","doi-asserted-by":"publisher","unstructured":"E. Knill. Quantum computing with realistically noisy devices. Nature, 434(7029):39\u201344, mar 2005, arXiv:quant-ph\/0410199.","DOI":"10.1038\/nature03350"},{"key":"18","doi-asserted-by":"publisher","unstructured":"S. Lovett and J. Zhang. Improved noisy population recovery, and reverse Bonami\u2013Beckner inequality for sparse functions. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pages 137\u2013142, 2015.","DOI":"10.1145\/2746539.2746540"},{"key":"19","unstructured":"S. Lovett and J. Zhang. Noisy population recovery from unknown noise. In Conference on Learning Theory, pages 1417\u20131431, 2017."},{"key":"20","doi-asserted-by":"publisher","unstructured":"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\u2013116, 2013, arXiv:1302.1515.","DOI":"10.1109\/FOCS.2013.20"},{"key":"21","doi-asserted-by":"publisher","unstructured":"A. Montanaro and T. J. Osborne. Quantum Boolean functions. Chicago Journal of Theoretical Computer Science, 2010(1):1\u201345, January 2010, arXiv:0810.2435.","DOI":"10.4086\/cjtcs.2010.001"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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\u20131278. Society for Industrial and Applied Mathematics, Jan. 2021, arXiv:2004.06828.","DOI":"10.1137\/1.9781611976465.77"},{"key":"23","doi-asserted-by":"publisher","unstructured":"R. O'Donnell. Analysis of Boolean functions. Cambridge University Press, 2014, arXiv:2105.10386.","DOI":"10.1017\/CBO9781139814782"},{"key":"24","unstructured":"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\u20131618, Amsterdam, Netherlands, 07\u201310 Jul 2017. PMLR, arXiv:1702.05574."},{"key":"25","doi-asserted-by":"publisher","unstructured":"B. Terhal. Quantum error correction for quantum memories. Reviews of Modern Physics, 87(2):307, 2015, arXiv:1302.3428.","DOI":"10.1103\/RevModPhys.87.307"},{"key":"26","doi-asserted-by":"publisher","unstructured":"J. ur Rehman and H. Shin. Entanglement-free parameter estimation of generalized Pauli channels. Quantum, 5:490, Jul 2021, arXiv:2102.00740.","DOI":"10.22331\/q-2021-07-01-490"},{"key":"27","doi-asserted-by":"publisher","unstructured":"M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge University Press, 2019.","DOI":"10.1017\/9781108627771"},{"key":"28","doi-asserted-by":"publisher","unstructured":"J. Wallman and J. Emerson. Noise tailoring for scalable quantum computation via randomized compiling. Physical Review A, 94(5):052325, 2016, arXiv:1512.01098.","DOI":"10.1103\/PhysRevA.94.052325"},{"key":"29","doi-asserted-by":"publisher","unstructured":"A. Wigderson and A. Yehudayoff. Population recovery and partial identification. Machine Learning, 102(1):29\u201356, 2016.","DOI":"10.1007\/s10994-015-5489-9"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-09-23-549\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,1,13]],"date-time":"2022-01-13T19:55:51Z","timestamp":1642103751000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-09-23-549\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,23]]},"references-count":30,"URL":"https:\/\/doi.org\/10.22331\/q-2021-09-23-549","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,23]]},"article-number":"549"}}