{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T08:22:42Z","timestamp":1772180562940,"version":"3.50.1"},"reference-count":84,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T00:00:00Z","timestamp":1607299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Centre of Excellence for Engineered Quantum Systems, Australian Research Council","award":["CE170100009"],"award-info":[{"award-number":["CE170100009"]}]},{"name":"Transformative Quantum Technologies"},{"name":"Natural Sciences and Engineering Research Council (NSERC), Industry Canada"},{"DOI":"10.13039\/501100010785","name":"Canada First Research Excellence Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100010785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"U.S. Army Research Office","doi-asserted-by":"crossref","award":["W911NF-14-1-0098"],"award-info":[{"award-number":["W911NF-14-1-0098"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-14-1-0103"],"award-info":[{"award-number":["W911NF-14-1-0103"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>\n            Pauli channels are ubiquitous in quantum information, both as a dominant noise source in many computing architectures and as a practical model for analyzing error correction and fault tolerance. Here, we prove several results on efficiently learning Pauli channels and more generally the Pauli projection of a quantum channel. We first derive a procedure for learning a Pauli channel on\n            <jats:italic>n<\/jats:italic>\n            qubits with high probability to a\n            <jats:italic>relative<\/jats:italic>\n            precision \u03f5 using\n            <jats:italic>O<\/jats:italic>\n            (\u03f5\n            <jats:sup>-2<\/jats:sup>\n            <jats:italic>n2<\/jats:italic>\n            <jats:sup>n<\/jats:sup>\n            ) measurements, which is efficient in the Hilbert space dimension. The estimate is robust to state preparation and measurement errors, which, together with the relative precision, makes it especially appropriate for applications involving characterization of high-accuracy quantum gates. Next, we show that the error rates for an arbitrary set of\n            <jats:italic>s<\/jats:italic>\n            Pauli errors can be estimated to a relative precision \u03f5 using\n            <jats:italic>O<\/jats:italic>\n            (\u03f5\n            <jats:sup>-4<\/jats:sup>\n            log\n            <jats:italic>s<\/jats:italic>\n            log s\/\u03f5) measurements. Finally, we show that when the Pauli channel is given by a Markov field with at most\n            <jats:italic>k<\/jats:italic>\n            -local correlations, we can learn an entire\n            <jats:italic>n<\/jats:italic>\n            -qubit Pauli channel to relative precision \u03f5 with only\n            <jats:italic>\n              O\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            (\u03f5\n            <jats:sup>-2<\/jats:sup>\n            n\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) measurements, which is efficient in the number of qubits. These results enable a host of applications beyond just characterizing noise in a large-scale quantum system: they pave the way to tailoring quantum codes, optimizing decoders, and customizing fault tolerance procedures to suit a particular device.\n          <\/jats:p>","DOI":"10.1145\/3408039","type":"journal-article","created":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T18:55:56Z","timestamp":1607367356000},"page":"1-32","source":"Crossref","is-referenced-by-count":117,"title":["Efficient Estimation of Pauli Channels"],"prefix":"10.1145","volume":"1","author":[{"given":"Steven T.","family":"Flammia","sequence":"first","affiliation":[{"name":"Centre for Engineered Quantum Systems, School of Physics, University of Sydney; Yale Quantum Institute, Yale University; Quantum Benchmark Inc., Ontario, Canada"}]},{"given":"Joel J.","family":"Wallman","sequence":"additional","affiliation":[{"name":"Quantum Benchmark Inc., Ontario, Canada; Institute for Quantum Computing and Department of Applied Mathematics, University of Waterloo"}]}],"member":"320","published-online":{"date-parts":[[2020,12,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.87.307"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.94.052325"},{"key":"e_1_2_1_3_1","first-page":"012002","article-title":"New J","volume":"18","author":"Sanders Y. R.","year":"2015","journal-title":"Phys."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.117.170502"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"022313","DOI":"10.1103\/PhysRevA.99.022313","volume":"99","author":"Huang E.","year":"2019","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.121.190501"},{"key":"e_1_2_1_7_1","unstructured":"M. Ware G. Ribeill D. Riste C. A. Ryan B. Johnson and M. P. da Silva. 2018. arXiv:1803.01818.  M. Ware G. Ribeill D. Riste C. A. Ryan B. Johnson and M. P. da Silva. 2018. arXiv:1803.01818."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"021004","DOI":"10.1103\/PhysRevX.2.021004","author":"Bombin H.","year":"2012","journal-title":"Phys. Rev."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"N. H. Nickerson and B. J. Brown. 2019. Quantum 3 (2019) 131.  N. H. Nickerson and B. J. Brown. 2019. Quantum 3 (2019) 131.","DOI":"10.22331\/q-2019-04-08-131"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"040502","DOI":"10.1103\/PhysRevLett.119.040502","volume":"119","author":"Darmawan A. S.","year":"2017","journal-title":"Phys. Rev. Lett."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"052351","DOI":"10.1103\/PhysRevA.99.052351","volume":"99","author":"Maskara N.","year":"2019","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"050505","DOI":"10.1103\/PhysRevLett.120.050505","volume":"120","author":"Tuckett D. K.","year":"2018","journal-title":"Phys. Rev. Lett."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"041031","DOI":"10.1103\/PhysRevX.9.041031","author":"Tuckett D. K.","year":"2019","journal-title":"Phys. Rev."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"130501","DOI":"10.1103\/PhysRevLett.124.130501","volume":"124","author":"Tuckett D. K.","year":"2020","journal-title":"Phys. Rev. Lett."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"064004","DOI":"10.1103\/PhysRevApplied.8.064004","volume":"8","author":"Robertson A.","year":"2017","journal-title":"Phys. Rev. Appl."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.78.052331"},{"key":"e_1_2_1_17_1","unstructured":"C. T. Chubb and S. T. Flammia. 2018. arXiv:1809.10704.  C. T. Chubb and S. T. Flammia. 2018. arXiv:1809.10704."},{"key":"e_1_2_1_18_1","first-page":"S347","article-title":"J","volume":"7","author":"Emerson J.","year":"2005","journal-title":"Opt. B"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.80.012304"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.77.012307"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"J. Helsen X. Xue L. M. Vandersypen and S. Wehner. 2019. npj Quantum Inf. 5 (2019) 71.  J. Helsen X. Xue L. M. Vandersypen and S. Wehner. 2019. npj Quantum Inf. 5 (2019) 71.","DOI":"10.1038\/s41534-019-0182-7"},{"key":"e_1_2_1_22_1","unstructured":"A. Erhard J. J. Wallman L. Postler M. Meth R. Stricker E. A. Martinez P. Schindler T. Monz J. Emerson and R. Blatt. 2019. arXiv e-prints (2019).  A. Erhard J. J. Wallman L. Postler M. Meth R. Stricker E. A. Martinez P. Schindler T. Monz J. Emerson and R. Blatt. 2019. arXiv e-prints (2019)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.92.042333"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.119.130502"},{"key":"e_1_2_1_25_1","volume-title":"47","author":"Wallman J.","year":"2018"},{"key":"e_1_2_1_26_1","unstructured":"S. T. Merkel E. J. Pritchett and B. H. Fong. 2018. arXiv:1804.05951.  S. T. Merkel E. J. Pritchett and B. H. Fong. 2018. arXiv:1804.05951."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.220501"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"J. Emerson M. Silva O. Moussa C. Ryan M. Laforest J. Baugh D. G. Cory and R. Laflamme. 2007. Science 317 (2007) 1893.  J. Emerson M. Silva O. Moussa C. Ryan M. Laforest J. Baugh D. G. Cory and R. Laflamme. 2007. Science 317 (2007) 1893.","DOI":"10.1126\/science.1145699"},{"key":"e_1_2_1_29_1","first-page":"013034","article-title":"New J","volume":"11","author":"Ryan C. A.","year":"2009","journal-title":"Phys."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.109.240504"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"030303","DOI":"10.1103\/PhysRevA.90.030303","volume":"90","author":"Barends R.","year":"2014","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.92.060302"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"A. W. Cross E. Magesan L. S. Bishop J. A. Smolin and J. M. Gambetta. 2016. npj Quant. Info. 2 (2016).  A. W. Cross E. Magesan L. S. Bishop J. A. Smolin and J. M. Gambetta. 2016. npj Quant. Info. 2 (2016).","DOI":"10.1038\/npjqi.2016.12"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"A. K. Hashagen S. T. Flammia D. Gross and J. J. Wallman. 2018. Quantum 2 (2018) 85.  A. K. Hashagen S. T. Flammia D. Gross and J. J. Wallman. 2018. Quantum 2 (2018) 85.","DOI":"10.22331\/q-2018-08-22-85"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"062323","DOI":"10.1103\/PhysRevA.97.062323","volume":"97","author":"Brown W. G.","year":"2018","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_36_1","first-page":"395302","article-title":"J","volume":"51","author":"Fran\u00e7a D. S.","year":"2018","journal-title":"Phys. A: Math. Theor."},{"key":"e_1_2_1_37_1","unstructured":"R. Harper I. Hincks C. Ferrie S. T. Flammia and J. J. Wallman. 2019. Phys. Rev. A (2019).  R. Harper I. Hincks C. Ferrie S. T. Flammia and J. J. Wallman. 2019. Phys. Rev. A (2019)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","first-page":"022326","DOI":"10.1103\/PhysRevA.92.022326","volume":"92","author":"Fogarty M. A.","year":"2015","journal-title":"Phys. Rev. A"},{"key":"e_1_2_1_39_1","unstructured":"J. M. Hammersley and P. Clifford. 1971. Markov fields on finite graphs and lattices (1971) retrieved from http:\/\/www.statslab.cam.ac.uk\/ grg\/books\/hammfest\/hamm-cliff.pdf.  J. M. Hammersley and P. Clifford. 1971. Markov fields on finite graphs and lattices (1971) retrieved from http:\/\/www.statslab.cam.ac.uk\/ grg\/books\/hammfest\/hamm-cliff.pdf."},{"key":"e_1_2_1_40_1","unstructured":"R. Harper S. T. Flammia and J. J. Wallman. 2019. arXiv:1907.13022.  R. Harper S. T. Flammia and J. J. Wallman. 2019. arXiv:1907.13022."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.90.144504"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.105.150401"},{"key":"e_1_2_1_43_1","first-page":"095022","article-title":"New J","volume":"14","author":"Flammia S. T.","year":"2012","journal-title":"Phys."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.106.100401"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1080\/09500349708231894"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"J. Haah A. W. Harrow Z. Ji X. Wu and N. Yu. 2017. IEEE Trans. Info. Theory1 (2017).  J. Haah A. W. Harrow Z. Ji X. Wu and N. Yu. 2017. IEEE Trans. Info. Theory1 (2017).","DOI":"10.1109\/TIT.2017.2719044"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC\u201916)","author":"O\u2019Donnell R."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201917)","author":"O\u2019Donnell R."},{"key":"e_1_2_1_49_1","volume-title":"In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201918)","author":"Aaronson S.","year":"2018"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms1147"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.91.042129"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.87.062119"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"R. Blume-Kohout J. K. Gamble E. Nielsen K. Rudinger J. Mizrahi K. Fortier and P. Maunz. 2016. Nature Commun. 8 (2016).  R. Blume-Kohout J. K. Gamble E. Nielsen K. Rudinger J. Mizrahi K. Fortier and P. Maunz. 2016. Nature Commun. 8 (2016).","DOI":"10.1038\/ncomms14485"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.4.011050"},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","first-page":"170502","DOI":"10.1103\/PhysRevLett.121.170502","volume":"121","author":"Roth I.","year":"2018","journal-title":"Phys. Rev. Lett."},{"key":"e_1_2_1_56_1","volume-title":"Proceedings of the 27th International Conference on Neural Information Processing Systems\u2014Volume 1 (NIPS\u201914)","author":"Bresler G."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054142"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/1248547.1248611"},{"key":"e_1_2_1_59_1","first-page":"563","article-title":"SIAM J","volume":"42","author":"Bresler G.","year":"2013","journal-title":"Comput."},{"key":"e_1_2_1_60_1","volume-title":"In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC\u201915)","author":"Bresler G.","year":"2015"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS\u201917)","author":"Hamilton L."},{"key":"e_1_2_1_62_1","volume-title":"Proceedings of the IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS\u201917)","author":"Klivans A."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4916(89)90322-9"},{"key":"e_1_2_1_67_1","doi-asserted-by":"crossref","first-page":"030503","DOI":"10.1103\/PhysRevLett.123.030503","volume":"123","author":"Proctor T. J.","year":"2019","journal-title":"Phys. Rev. Lett."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176342611"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.885507"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2404441"},{"key":"e_1_2_1_74_1","article-title":"ACM","volume":"13","author":"Cheraghchi M.","year":"2017","journal-title":"Trans. Algor."},{"key":"e_1_2_1_75_1","volume-title":"Proceedings of the IEEE International Symposium on Information Theory. IEEE.","author":"Li X."},{"key":"e_1_2_1_76_1","volume-title":"Advances in Intelligent Systems and Computing","author":"Lu Y. J."},{"key":"e_1_2_1_77_1","unstructured":"D. Koller and N. Friedman. 2009. Probabilistic Graphical Models: Principles and Techniques. MIT Press Cambridge MA.  D. Koller and N. Friedman. 2009. Probabilistic Graphical Models: Principles and Techniques. MIT Press Cambridge MA."},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1974.tb00999.x"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/15\/10\/028"},{"key":"e_1_2_1_80_1","first-page":"1087","article-title":"SIAM J","volume":"22","author":"Jerrum M.","year":"1993","journal-title":"Comput."},{"key":"e_1_2_1_81_1","unstructured":"M. Pinsker. 1964. Information and Information Stability of Random Variables and Processes. Holden-Day.  M. Pinsker. 1964. Information and Information Stability of Random Variables and Processes. Holden-Day."},{"key":"e_1_2_1_82_1","doi-asserted-by":"crossref","unstructured":"T. M. Cover and J. A. Thomas. 1991. Elements of Information Theory. Wiley.  T. M. Cover and J. A. Thomas. 1991. Elements of Information Theory. Wiley.","DOI":"10.1002\/0471200611"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.109.080505"},{"key":"e_1_2_1_84_1","first-page":"113038","article-title":"New J","volume":"21","author":"Ferracin S.","year":"2019","journal-title":"Phys."},{"key":"e_1_2_1_85_1","first-page":"013042","article-title":"New J","volume":"17","author":"Granade C.","year":"2015","journal-title":"Phys."},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.93.207204"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.93.207205"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3408039","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3408039","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3408039","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:33Z","timestamp":1750197693000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3408039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,7]]},"references-count":84,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3408039"],"URL":"https:\/\/doi.org\/10.1145\/3408039","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,7]]}}}