{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T23:11:46Z","timestamp":1792797106569,"version":"4.5.0"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T00:00:00Z","timestamp":1721865600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T00:00:00Z","timestamp":1721865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat. Phys."],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Quantum error mitigation has been proposed as a means to combat unwanted and unavoidable errors in near-term quantum computing without the heavy resource overheads required by fault-tolerant schemes. Recently, error mitigation has been successfully applied to reduce noise in near-term applications. In this work, however, we identify strong limitations to the degree to which quantum noise can be effectively \u2018undone\u2019 for larger system sizes. Our framework rigorously captures large classes of error-mitigation schemes in use today. By relating error mitigation to a statistical inference problem, we show that even at shallow circuit depths comparable to those of current experiments, a superpolynomial number of samples is needed in the worst case to estimate the expectation values of noiseless observables, the principal task of error mitigation. Notably, our construction implies that scrambling due to noise can kick in at exponentially smaller depths than previously thought. Noise also impacts other near-term applications by constraining kernel estimation in quantum machine learning, causing an earlier emergence of noise-induced barren plateaus in variational quantum algorithms and ruling out exponential quantum speed-ups in estimating expectation values in the presence of noise or preparing the ground state of a Hamiltonian.<\/jats:p>","DOI":"10.1038\/s41567-024-02536-7","type":"journal-article","created":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T06:03:04Z","timestamp":1721887384000},"page":"1648-1658","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":102,"title":["Exponentially tighter bounds on limitations of quantum error mitigation"],"prefix":"10.1038","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1227-0804","authenticated-orcid":false,"given":"Yihui","family":"Quek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9699-5994","authenticated-orcid":false,"given":"Daniel","family":"Stilck Fran\u00e7a","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9858-0511","authenticated-orcid":false,"given":"Sumeet","family":"Khatri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johannes Jakob","family":"Meyer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3033-1292","authenticated-orcid":false,"given":"Jens","family":"Eisert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,7,25]]},"reference":[{"key":"2536_CR1","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/BF01886518","volume":"16","author":"RP Feynman","year":"1986","unstructured":"Feynman, R. P. Quantum mechanical computers. Found. Phys. 16, 507 (1986).","journal-title":"Found. Phys."},{"key":"2536_CR2","doi-asserted-by":"crossref","unstructured":"Shor, P. W. Algorithms for quantum computation: discrete logarithms and factoring. In Proc. 35th Annual Symposium on Foundations of Computer Science (ed. Goldwasser, S.) 124\u2013134 (IEEE, 1994).","DOI":"10.1109\/SFCS.1994.365700"},{"key":"2536_CR3","doi-asserted-by":"publisher","first-page":"R2493","DOI":"10.1103\/PhysRevA.52.R2493","volume":"52","author":"PW Shor","year":"1995","unstructured":"Shor, P. W. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A 52, R2493 (1995).","journal-title":"Phys. Rev. A"},{"key":"2536_CR4","doi-asserted-by":"crossref","unstructured":"Gottesman, D. in Quantum Information Science and Its Contributions to Mathematics (ed. Lomonaco Jr, S. J.) 13\u201360 (AMS, 2010).","DOI":"10.1090\/psapm\/068\/2762145"},{"key":"2536_CR5","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1038\/nature23460","volume":"549","author":"ET Campbell","year":"2017","unstructured":"Campbell, E. T., Terhal, B. M. & Vuillot, C. Roads towards fault-tolerant universal quantum computation. Nature 549, 172 (2017).","journal-title":"Nature"},{"key":"2536_CR6","first-page":"021050","volume":"7","author":"Y Li","year":"2017","unstructured":"Li, Y. & Benjamin, S. C. Efficient variational quantum simulator incorporating active error minimization. Phys. Rev. X 7, 021050 (2017).","journal-title":"Phys. Rev. X"},{"key":"2536_CR7","doi-asserted-by":"publisher","first-page":"180509","DOI":"10.1103\/PhysRevLett.119.180509","volume":"119","author":"K Temme","year":"2017","unstructured":"Temme, K., Bravyi, S. & Gambetta, J. M. Error mitigation for short-depth quantum circuits. Phys. Rev. Lett. 119, 180509 (2017).","journal-title":"Phys. Rev. Lett."},{"key":"2536_CR8","first-page":"031027","volume":"8","author":"S Endo","year":"2018","unstructured":"Endo, S., Benjamin, S. C. & Li, Y. Practical quantum error mitigation for near-future applications. Phys. Rev. X 8, 031027 (2018).","journal-title":"Phys. Rev. X"},{"key":"2536_CR9","doi-asserted-by":"crossref","unstructured":"Cai, Z. et al. Quantum error mitigation. Rev. Mod. Phys. 95, 045005 (2023).","DOI":"10.1103\/RevModPhys.95.045005"},{"key":"2536_CR10","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1038\/s41567-023-02042-2","volume":"19","author":"E van den Berg","year":"2023","unstructured":"van den Berg, E., Minev, Z. K., Kandala, A. & Temme, K. Probabilistic error cancellation with sparse Pauli\u2013Lindblad models on noisy quantum processors. Nat. Phys. 19, 1116 (2023).","journal-title":"Nat. Phys."},{"key":"2536_CR11","doi-asserted-by":"publisher","first-page":"023023","DOI":"10.1088\/1367-2630\/18\/2\/023023","volume":"18","author":"JR McClean","year":"2016","unstructured":"McClean, J. R., Romero, J., Babbush, R. & Aspuru-Guzik, A. The theory of variational hybrid quantum-classical algorithms. New J. Phys. 18, 023023 (2016).","journal-title":"New J. Phys."},{"key":"2536_CR12","doi-asserted-by":"publisher","unstructured":"Farhi, E., Goldstone, J. & Gutmann, S. A quantum approximate optimization algorithm. Preprint at https:\/\/doi.org\/10.48550\/arXiv.1411.4028 (2014).","DOI":"10.48550\/arXiv.1411.4028"},{"key":"2536_CR13","first-page":"041036","volume":"11","author":"WJ Huggins","year":"2021","unstructured":"Huggins, W. J. et al. Virtual distillation for quantum error mitigation. Phys. Rev. X 11, 041036 (2021).","journal-title":"Phys. Rev. X"},{"key":"2536_CR14","first-page":"031057","volume":"11","author":"B Koczor","year":"2022","unstructured":"Koczor, B. Exponential error suppression for near-term quantum devices. Phys. Rev. X 11, 031057 (2022).","journal-title":"Phys. Rev. X"},{"key":"2536_CR15","doi-asserted-by":"publisher","first-page":"592","DOI":"10.22331\/q-2021-11-26-592","volume":"5","author":"P Czarnik","year":"2022","unstructured":"Czarnik, P., Arrasmith, A., Coles, P. J. & Cincio, L. Error mitigation with Clifford quantum-circuit data. Quantum 5, 592 (2022).","journal-title":"Quantum"},{"key":"2536_CR16","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1038\/s41534-022-00618-z","volume":"8","author":"R Takagi","year":"2022","unstructured":"Takagi, R., Endo, S., Minagawa, S. & Gu, M. Fundamental limits of quantum error mitigation. npj Quantum Inf. 8, 114 (2022).","journal-title":"npj Quantum Inf."},{"key":"2536_CR17","doi-asserted-by":"crossref","unstructured":"Takagi, R., Tajima, H. & Gu, M. Universal sample lower bounds for quantum error mitigation. Phys. Rev. Lett. 131, 210602 (2023).","DOI":"10.1103\/PhysRevLett.131.210602"},{"key":"2536_CR18","doi-asserted-by":"crossref","unstructured":"Tsubouchi, K., Sagawa, T. & Yoshioka, N. Universal cost bound of quantum error mitigation based on quantum estimation theory. Phys. Rev. Lett. 131, 210601 (2023).","DOI":"10.1103\/PhysRevLett.131.210601"},{"key":"2536_CR19","doi-asserted-by":"publisher","first-page":"040329","DOI":"10.1103\/PRXQuantum.3.040329","volume":"3","author":"A Deshpande","year":"2022","unstructured":"Deshpande, A. et al. Tight bounds on the convergence of noisy random circuits to the uniform distribution. PRX Quantum 3, 040329 (2022).","journal-title":"PRX Quantum"},{"key":"2536_CR20","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1063\/1.4939560","volume":"57","author":"A M\u00fcller-Hermes","year":"2016","unstructured":"M\u00fcller-Hermes, A., Franca, D. S. & Wolf, M. M. Relative entropy convergence for depolarizing channels. J. Math. Phys. 57, 2 (2016).","journal-title":"J. Math. Phys."},{"key":"2536_CR21","doi-asserted-by":"publisher","first-page":"1221","DOI":"10.1038\/s41567-021-01356-3","volume":"17","author":"D Stilck Fran\u00e7a","year":"2021","unstructured":"Stilck Fran\u00e7a, D. & Garc\u00eda-Patr\u00f3n, R. Limitations of optimization algorithms on noisy quantum devices. Nat. Phys. 17, 1221 (2021).","journal-title":"Nat. Phys."},{"key":"2536_CR22","doi-asserted-by":"crossref","unstructured":"Tsybakov, A. B. Introduction to Non-Parametric Estimation (Springer, 2009).","DOI":"10.1007\/b13794"},{"key":"2536_CR23","doi-asserted-by":"crossref","unstructured":"De Palma, G., Marvian, M., Rouz\u00e9, C. & Stilck Franca, D. Limitations of variational quantum algorithms: a quantum optimal transport approach. PRX Quantum 4, 010309 (2023).","DOI":"10.1103\/PRXQuantum.4.010309"},{"key":"2536_CR24","doi-asserted-by":"crossref","unstructured":"Wang, S. et al. Can error mitigation improve trainability of noisy variational quantum algorithms? Quantum 8, 1287 (2024).","DOI":"10.22331\/q-2024-03-14-1287"},{"key":"2536_CR25","doi-asserted-by":"publisher","unstructured":"Thanasilp, S., Wang, S., Cerezo, M. & Holmes, Z. Exponential concentration and untrainability in quantum kernel methods. Preprint at https:\/\/doi.org\/10.48550\/arXiv.2208.11060 (2022).","DOI":"10.48550\/arXiv.2208.11060"},{"key":"2536_CR26","doi-asserted-by":"publisher","first-page":"6961","DOI":"10.1038\/s41467-021-27045-6","volume":"12","author":"S Wang","year":"2021","unstructured":"Wang, S. et al. Noise-induced barren plateaus in variational quantum algorithms. Nat. Commun. 12, 6961 (2021).","journal-title":"Nat. Commun."},{"key":"2536_CR27","doi-asserted-by":"crossref","unstructured":"Deshpande, A. et al. Tight bounds on the convergence of noisy random circuits to the uniform distribution. PRX Quantum 3, 040329 (2022).","DOI":"10.1103\/PRXQuantum.3.040329"},{"key":"2536_CR28","first-page":"721","volume":"16","author":"R Cleve","year":"2016","unstructured":"Cleve, R., Leung, D., Liu, L. & Wang, C. Near-linear constructions of exact unitary 2-designs. Quantum Inf. Comput. 16, 721\u2013756 (2016).","journal-title":"Quantum Inf. Comput."},{"key":"2536_CR29","unstructured":"Reyzin, L. Statistical queries and statistical algorithms: foundations and applications. Preprint at https:\/\/arxiv.org\/abs\/2004.00557 (2020)."},{"key":"2536_CR30","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1214\/aos\/1176349553","volume":"13","author":"YG Yatracos","year":"1985","unstructured":"Yatracos, Y. G. Rates of convergence of minimum distance estimators and Kolmogorov\u2019s entropy. Ann. Stat. 13, 768 (1985).","journal-title":"Ann. Stat."},{"key":"2536_CR31","doi-asserted-by":"crossref","unstructured":"Blum, A. et al. Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Proc. 26th Annual ACM Symposium on Theory of Computing 253\u2013262 (ACM, 1994).","DOI":"10.1145\/195058.195147"},{"key":"2536_CR32","doi-asserted-by":"publisher","first-page":"210502","DOI":"10.1103\/PhysRevLett.126.210502","volume":"126","author":"DS Fran\u00e7a","year":"2021","unstructured":"Fran\u00e7a, D. S., Strelchuk, S. & Studzi\u0144ski, M. Efficient classical simulation and benchmarking of quantum processes in the Weyl basis. Phys. Rev. Lett. 126, 210502 (2021).","journal-title":"Phys. Rev. Lett."},{"key":"2536_CR33","doi-asserted-by":"publisher","first-page":"062337","DOI":"10.1103\/PhysRevA.99.062337","volume":"99","author":"P Rall","year":"2019","unstructured":"Rall, P., Liang, D., Cook, J. & Kretschmer, W. Simulation of qubit quantum circuits via Pauli propagation. Phys. Rev. A 99, 062337 (2019).","journal-title":"Phys. Rev. A"},{"key":"2536_CR34","doi-asserted-by":"publisher","first-page":"260505","DOI":"10.1103\/PhysRevLett.125.260505","volume":"125","author":"S Bravyi","year":"2020","unstructured":"Bravyi, S., Kliesch, A., Koenig, R. & Tang, E. Obstacles to variational quantum optimization from symmetry protection. Phys. Rev. Lett. 125, 260505 (2020).","journal-title":"Phys. Rev. Lett."},{"key":"2536_CR35","doi-asserted-by":"publisher","unstructured":"Farhi, E., Gamarnik, D. & Gutmann, S. The quantum approximate optimization algorithm needs to see the whole graph: worst case examples. Preprint at https:\/\/doi.org\/10.48550\/arXiv.2005.08747 (2020).","DOI":"10.48550\/arXiv.2005.08747"},{"key":"2536_CR36","doi-asserted-by":"crossref","unstructured":"Eldar, L. & Harrow, A. W. Local Hamiltonians whose ground states are hard to approximate. In Proc. 58th Annual Symposium on Foundations of Computer Science 427\u2013438 (IEEE, 2017).","DOI":"10.1109\/FOCS.2017.46"},{"key":"2536_CR37","doi-asserted-by":"crossref","unstructured":"Anshu, A., Breuckmann, N. P. & Nirkhe, C. NLTS Hamiltonians from good quantum codes. In Proc. 55th Annual ACM Symposium on Theory of Computing 1090\u20131096 (ACM, 2023).","DOI":"10.1145\/3564246.3585114"},{"key":"2536_CR38","doi-asserted-by":"publisher","first-page":"040326","DOI":"10.1103\/PRXQuantum.3.040326","volume":"3","author":"G Gonz\u00e1lez-Garc\u0131a","year":"2022","unstructured":"Gonz\u00e1lez-Garc\u0131a, G., Trivedi, R. & Cirac, J. I. Error propagation in NISQ devices for solving classical optimization problems. PRX Quantum 3, 040326 (2022).","journal-title":"PRX Quantum"},{"key":"2536_CR39","doi-asserted-by":"publisher","first-page":"2474","DOI":"10.1109\/TIT.2011.2110050","volume":"57","author":"M Mosonyi","year":"2011","unstructured":"Mosonyi, M. & Hiai, F. On the quantum R\u00e9nyi relative entropies and related capacity formulas. IEEE Trans. Inf. Theory 57, 2474 (2011).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2536_CR40","doi-asserted-by":"publisher","first-page":"012304","DOI":"10.1103\/PhysRevA.80.012304","volume":"80","author":"C Dankert","year":"2009","unstructured":"Dankert, C., Cleve, R., Emerson, J. & Livine, E. Exact and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev. A 80, 012304 (2009).","journal-title":"Phys. Rev. A"},{"key":"2536_CR41","unstructured":"Gottesman, D. Stabilizer Codes and Quantum Error Correction (Caltech, 1997)."},{"key":"2536_CR42","doi-asserted-by":"crossref","unstructured":"Watrous, J. The Theory of Quantum Information (Cambridge Univ. Press, 2018).","DOI":"10.1017\/9781316848142"},{"key":"2536_CR43","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1038\/s42254-021-00348-9","volume":"3","author":"M Cerezo","year":"2021","unstructured":"Cerezo, M. et al. Variational quantum algorithms. Nat. Rev. Phys. 3, 625 (2021).","journal-title":"Nat. Rev. Phys."},{"key":"2536_CR44","doi-asserted-by":"publisher","first-page":"015004","DOI":"10.1103\/RevModPhys.94.015004","volume":"94","author":"K Bharti","year":"2022","unstructured":"Bharti, K. et al. Noisy intermediate-scale quantum algorithms. Rev. Mod. Phys. 94, 015004 (2022).","journal-title":"Rev. Mod. Phys."},{"key":"2536_CR45","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1145\/293347.293351","volume":"45","author":"M Kearns","year":"1998","unstructured":"Kearns, M. Efficient noise-tolerant learning from statistical queries. J. ACM 45, 983\u20131006 (1998).","journal-title":"J. ACM"},{"key":"2536_CR46","doi-asserted-by":"publisher","first-page":"240602","DOI":"10.1103\/PhysRevLett.130.240602","volume":"130","author":"M Hinsche","year":"2023","unstructured":"Hinsche, M. et al. A single T-gate makes distribution learning hard. Phys. Rev. Lett. 130, 240602 (2023).","journal-title":"Phys. Rev. Lett."},{"key":"2536_CR47","doi-asserted-by":"publisher","unstructured":"Arunachalam, S., Grilo, A. B. & Yuen, H. Quantum statistical query learning. Preprint at https:\/\/doi.org\/10.48550\/arXiv.2002.08240 (2020).","DOI":"10.48550\/arXiv.2002.08240"},{"key":"2536_CR48","doi-asserted-by":"publisher","first-page":"753","DOI":"10.22331\/q-2022-06-30-753","volume":"6","author":"DS Fran\u00e7a","year":"2022","unstructured":"Fran\u00e7a, D. S. & Garcia-Patron, R. A game of quantum advantage: linking verification and simulation. Quantum 6, 753 (2022).","journal-title":"Quantum"}],"container-title":["Nature Physics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.nature.com\/articles\/s41567-024-02536-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s41567-024-02536-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s41567-024-02536-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,24]],"date-time":"2024-11-24T15:31:18Z","timestamp":1732462278000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.nature.com\/articles\/s41567-024-02536-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,25]]},"references-count":48,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["2536"],"URL":"https:\/\/doi.org\/10.1038\/s41567-024-02536-7","relation":{},"ISSN":["1745-2473","1745-2481"],"issn-type":[{"value":"1745-2473","type":"print"},{"value":"1745-2481","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,25]]},"assertion":[{"value":"26 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}