Reduced Sampling Overhead for Probabilistic Error Cancellation by Pauli Error Propagation

Timon Scheiber; Paul Haubenwallner; Matthias Heller

doi:10.22331/q-2025-08-29-1840

Reduced Sampling Overhead for Probabilistic Error Cancellation by Pauli Error Propagation

Timon Scheiber, Paul Haubenwallner, and Matthias Heller

Fraunhofer Institute for Computer Graphics Research IGD
Technical University of Darmstadt, Interactive Graphics Systems Group

Published:	2025-08-29, volume 9, page 1840
Editor:	Xin Wang
Eprint:	arXiv:2412.01311v3
Doi:	https://doi.org/10.22331/q-2025-08-29-1840
Citation:	Quantum 9, 1840 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Quantum error mitigation is regarded as a possible path to near-term quantum utility. The methods under the quantum error mitigation umbrella term, such as probabilistic error cancellation (PEC), zero-noise extrapolation (ZNE) or Clifford data regression (CDR) are able to significantly reduce the error for the estimation of expectation values, although at an exponentially scaling cost, i.e., in the sampling overhead. In this work, we present a method to reduce the sampling overhead of PEC through Pauli error propagation combined with classical preprocessing. Our findings indicate that this method significantly reduces sampling overheads for Clifford circuits, leveraging the well-defined interaction between the Clifford group and Pauli noise.
Additionally, we show that the method is applicable to non-Clifford circuits, though with more limited effectiveness, primarily constrained by the number of non-Clifford gates present in the circuit. We further provide examples of Clifford sub-circuits commonly encountered in relevant calculations, such as resource state generation in measurement-based quantum computing.

► BibTeX data

@article{Scheiber2025reducedsampling,
  doi = {10.22331/q-2025-08-29-1840},
  url = {https://doi.org/10.22331/q-2025-08-29-1840},
  title = {Reduced {S}ampling {O}verhead for {P}robabilistic {E}rror {C}ancellation by {P}auli {E}rror {P}ropagation},
  author = {Scheiber, Timon and Haubenwallner, Paul and Heller, Matthias},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1840},
  month = aug,
  year = {2025}
}

► References

[1] Andrew J Daley, Immanuel Bloch, Christian Kokail, Stuart Flannigan, Natalie Pearson, Matthias Troyer, and Peter Zoller. Practical quantum advantage in quantum simulation. Nature, 607 (7920): 667–676, 2022. 10.1038/s41586-022-04940-6.
https://doi.org/10.1038/s41586-022-04940-6

[2] Alberto Di Meglio, Karl Jansen, Ivano Tavernelli, Constantia Alexandrou, Srinivasan Arunachalam, Christian W Bauer, Kerstin Borras, Stefano Carrazza, Arianna Crippa, Vincent Croft, et al. Quantum computing for high-energy physics: State of the art and challenges. Prx quantum, 5 (3): 037001, 2024. 10.1103/PRXQuantum.5.037001.
https://doi.org/10.1103/PRXQuantum.5.037001

[3] Craig Gidney and Martin Ekerå. How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits. Quantum, 5: 433, 2021. 10.22331/q-2021-04-15-433.
https://doi.org/10.22331/q-2021-04-15-433

[4] Markus Reiher, Nathan Wiebe, Krysta M Svore, Dave Wecker, and Matthias Troyer. Elucidating reaction mechanisms on quantum computers. Proceedings of the national academy of sciences, 114 (29): 7555–7560, 2017. 10.1073/pnas.1619152114.
https://doi.org/10.1073/pnas.1619152114

[5] Sergey Bravyi, Andrew W Cross, Jay M Gambetta, Dmitri Maslov, Patrick Rall, and Theodore J Yoder. High-threshold and low-overhead fault-tolerant quantum memory. Nature, 627 (8005): 778–782, 2024. 10.1038/s41586-024-07107-7.
https://doi.org/10.1038/s41586-024-07107-7

[6] Qian Xu, J Pablo Bonilla Ataides, Christopher A Pattison, Nithin Raveendran, Dolev Bluvstein, Jonathan Wurtz, Bane Vasić, Mikhail D Lukin, Liang Jiang, and Hengyun Zhou. Constant-overhead fault-tolerant quantum computation with reconfigurable atom arrays. Nature Physics, pages 1–7, 2024. 10.1038/s41567-024-02479-z.
https://doi.org/10.1038/s41567-024-02479-z

[7] Dolev Bluvstein, Simon J Evered, Alexandra A Geim, Sophie H Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, et al. Logical quantum processor based on reconfigurable atom arrays. Nature, 626 (7997): 58–65, 2024. 10.1038/s41586-023-06927-3.
https://doi.org/10.1038/s41586-023-06927-3

[8] VV Sivak, Alec Eickbusch, Baptiste Royer, Shraddha Singh, Ioannis Tsioutsios, Suhas Ganjam, Alessandro Miano, BL Brock, AZ Ding, Luigi Frunzio, et al. Real-time quantum error correction beyond break-even. Nature, 616 (7955): 50–55, 2023. 10.1038/s41586-023-05782-6.
https://doi.org/10.1038/s41586-023-05782-6

[9] Google Quantum AI. Suppressing quantum errors by scaling a surface code logical qubit. Nature, 614 (7949): 676–681, 2023. 10.1038/s41586-022-05434-1.
https://doi.org/10.1038/s41586-022-05434-1

[10] Google Quantum AI. Quantum error correction below the surface code threshold. Nature, 638 (8052): 920–926, 2025. 10.1038/s41586-024-08449-y.
https://doi.org/10.1038/s41586-024-08449-y

[11] Alexis Morvan, B Villalonga, X Mi, S Mandrà, A Bengtsson, PV Klimov, Z Chen, S Hong, C Erickson, IK Drozdov, et al. Phase transitions in random circuit sampling. Nature, 634 (8033): 328–333, 2024. 10.1038/s41586-024-07998-6.
https://doi.org/10.1038/s41586-024-07998-6

[12] Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout Van Den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, et al. Evidence for the utility of quantum computing before fault tolerance. Nature, 618 (7965): 500–505, 2023. 10.1038/s41586-023-06096-3.
https://doi.org/10.1038/s41586-023-06096-3

[13] Kazuya Shinjo, Kazuhiro Seki, Tomonori Shirakawa, Rong-Yang Sun, and Seiji Yunoki. Unveiling clean two-dimensional discrete time quasicrystals on a digital quantum computer. arXiv preprint arXiv:2403.16718, 2024. 10.48550/arXiv.2403.16718.
https://doi.org/10.48550/arXiv.2403.16718
arXiv:2403.16718

[14] Piotr Czarnik, Andrew Arrasmith, Patrick J Coles, and Lukasz Cincio. Error mitigation with clifford quantum-circuit data. Quantum, 5: 592, 2021. 10.22331/q-2021-11-26-592.
https://doi.org/10.22331/q-2021-11-26-592

[15] Kristan Temme, Sergey Bravyi, and Jay M Gambetta. Error mitigation for short-depth quantum circuits. Physical review letters, 119 (18): 180509, 2017. 10.1103/physrevlett.119.180509.
https://doi.org/10.1103/physrevlett.119.180509

[16] Zhenyu Cai, Ryan Babbush, Simon C Benjamin, Suguru Endo, William J Huggins, Ying Li, Jarrod R McClean, and Thomas E O’Brien. Quantum error mitigation. Reviews of Modern Physics, 95 (4): 045005, 2023. 10.1103/revmodphys.95.045005.
https://doi.org/10.1103/revmodphys.95.045005

[17] Yihui Quek, Daniel Stilck França, Sumeet Khatri, Johannes Jakob Meyer, and Jens Eisert. Exponentially tighter bounds on limitations of quantum error mitigation. Nature Physics, 20 (10): 1648–1658, 2024. 10.1038/s41567-024-02536-7.
https://doi.org/10.1038/s41567-024-02536-7

[18] Ryuji Takagi, Suguru Endo, Shintaro Minagawa, and Mile Gu. Fundamental limits of quantum error mitigation. npj Quantum Information, 8 (1): 114, 2022. 10.1038/s41534-022-00618-z.
https://doi.org/10.1038/s41534-022-00618-z

[19] Suguru Endo, Simon C Benjamin, and Ying Li. Practical quantum error mitigation for near-future applications. Physical Review X, 8 (3): 031027, 2018. 10.1103/physrevx.8.031027.
https://doi.org/10.1103/physrevx.8.031027

[20] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala, and Kristan Temme. Probabilistic error cancellation with sparse pauli–lindblad models on noisy quantum processors. Nature Physics, pages 1–6, 2023. 10.1038/s41567-023-02042-2.
https://doi.org/10.1038/s41567-023-02042-2

[21] Minh C Tran, Kunal Sharma, and Kristan Temme. Locality and error mitigation of quantum circuits. arXiv preprint arXiv:2303.06496, 2023. 10.48550/arXiv.2303.06496.
https://doi.org/10.48550/arXiv.2303.06496
arXiv:2303.06496

[22] Prasanth Shyamsundar and Wern Yeen Yeong. Cv4quantum: Reducing the sampling overhead in probabilistic error cancellation using control variates. arXiv preprint arXiv:2502.08735, 2025. 10.48550/arXiv.2502.08735.
https://doi.org/10.48550/arXiv.2502.08735
arXiv:2502.08735

[23] Benchi Zhao, Mingrui Jing, Lei Zhang, Xuanqiang Zhao, Yu-Ao Chen, Kun Wang, and Xin Wang. Retrieving nonlinear features from noisy quantum states. PRX Quantum, 5 (2): 020357, 2024. 10.1103/prxquantum.5.020357.
https://doi.org/10.1103/prxquantum.5.020357

[24] Jiaqing Jiang, Kun Wang, and Xin Wang. Physical implementability of linear maps and its application in error mitigation. Quantum, 5: 600, 2021. 10.22331/q-2021-12-07-600.
https://doi.org/10.22331/q-2021-12-07-600

[25] Yuchen Guo and Shuo Yang. Quantum error mitigation via matrix product operators. PRX Quantum, 3 (4): 040313, 2022. 10.1103/prxquantum.3.040313.
https://doi.org/10.1103/prxquantum.3.040313

[26] Sergei Filippov, Matea Leahy, Matteo AC Rossi, and Guillermo García-Pérez. Scalable tensor-network error mitigation for near-term quantum computing. arXiv preprint arXiv:2307.11740, 2023. 10.48550/arXiv.2307.11740.
https://doi.org/10.48550/arXiv.2307.11740
arXiv:2307.11740

[27] Mathys Rennela and Harold Ollivier. Low bit-flip rate probabilistic error cancellation. arXiv preprint arXiv:2411.06422, 2024. 10.48550/arXiv.2411.06422.
https://doi.org/10.48550/arXiv.2411.06422
arXiv:2411.06422

[28] Joel J Wallman and Joseph Emerson. Noise tailoring for scalable quantum computation via randomized compiling. Physical Review A, 94 (5): 052325, 2016. 10.1103/physreva.94.052325.
https://doi.org/10.1103/physreva.94.052325

[29] Alexander Erhard, Joel J Wallman, Lukas Postler, Michael Meth, Roman Stricker, Esteban A Martinez, Philipp Schindler, Thomas Monz, Joseph Emerson, and Rainer Blatt. Characterizing large-scale quantum computers via cycle benchmarking. Nature communications, 10 (1): 5347, 2019. 10.1038/s41467-019-13068-7.
https://doi.org/10.1038/s41467-019-13068-7

[30] Senrui Chen, Yunchao Liu, Matthew Otten, Alireza Seif, Bill Fefferman, and Liang Jiang. The learnability of pauli noise. Nature Communications, 14 (1): 52, 2023. 10.1038/s41467-022-35759-4.
https://doi.org/10.1038/s41467-022-35759-4

[31] Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C Mckay, and Jay M Gambetta. Mitigating measurement errors in multiqubit experiments. Physical Review A, 103 (4): 042605, 2021. 10.1103/physreva.103.042605.
https://doi.org/10.1103/physreva.103.042605

[32] Paul D Nation, Hwajung Kang, Neereja Sundaresan, and Jay M Gambetta. Scalable mitigation of measurement errors on quantum computers. PRX Quantum, 2 (4): 040326, 2021. 10.1103/prxquantum.2.040326.
https://doi.org/10.1103/prxquantum.2.040326

[33] Lena Funcke, Tobias Hartung, Karl Jansen, Stefan Kühn, Paolo Stornati, and Xiaoyang Wang. Measurement error mitigation in quantum computers through classical bit-flip correction. Physical Review A, 105 (6): 062404, 2022. 10.1103/physreva.105.062404.
https://doi.org/10.1103/physreva.105.062404

[34] Bo Yang, Rudy Raymond, and Shumpei Uno. Efficient quantum readout-error mitigation for sparse measurement outcomes of near-term quantum devices. Physical Review A, 106 (1): 012423, 2022. 10.1103/physreva.106.012423.
https://doi.org/10.1103/physreva.106.012423

[35] Ewout Van Den Berg, Zlatko K Minev, and Kristan Temme. Model-free readout-error mitigation for quantum expectation values. Physical Review A, 105 (3): 032620, 2022. 10.1103/physreva.105.032620.
https://doi.org/10.1103/physreva.105.032620

[36] Daniel Gottesman. The heisenberg representation of quantum computers. 1998. 10.48550/arXiv.quant-ph/9807006.
https://doi.org/10.48550/arXiv.quant-ph/9807006
arXiv:quant-ph/9807006

[37] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014. 10.48550/arXiv.1411.4028.
https://doi.org/10.48550/arXiv.1411.4028
arXiv:1411.4028

[38] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5 (1): 4213, 2014. 10.1038/ncomms5213.
https://doi.org/10.1038/ncomms5213

[39] Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi, and Frederic T Chong. Minimizing state preparations in variational quantum eigensolver by partitioning into commuting families. arXiv preprint arXiv:1907.13623, 2019. 10.48550/arXiv.1907.13623.
https://doi.org/10.48550/arXiv.1907.13623
arXiv:1907.13623

[40] Hans J Briegel, David E Browne, Wolfgang Dür, Robert Raussendorf, and Maarten Van den Nest. Measurement-based quantum computation. Nature Physics, 5 (1): 19–26, 2009. 10.1038/nphys1157.
https://doi.org/10.1038/nphys1157

[41] Robert Raussendorf, Daniel E Browne, and Hans J Briegel. Measurement-based quantum computation on cluster states. Physical review A, 68 (2): 022312, 2003. 10.1103/physreva.68.022312.
https://doi.org/10.1103/physreva.68.022312

[42] Riddhi S Gupta, Ewout Van Den Berg, Maika Takita, Diego Riste, Kristan Temme, and Abhinav Kandala. Probabilistic error cancellation for dynamic quantum circuits. Physical Review A, 109 (6): 062617, 2024. 10.1103/physreva.109.062617.
https://doi.org/10.1103/physreva.109.062617

[43] Jiace Sun, Lixue Cheng, and Weitang Li. Toward chemical accuracy with shallow quantum circuits: A clifford-based hamiltonian engineering approach. Journal of Chemical Theory and Computation, 20 (2): 695–707, 2024. 10.1021/acs.jctc.3c00886.
https://doi.org/10.1021/acs.jctc.3c00886

[44] Dan Shepherd and Michael J Bremner. Temporally unstructured quantum computation. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465 (2105): 1413–1439, 2009. 10.1098/rspa.2008.0443.
https://doi.org/10.1098/rspa.2008.0443

[45] Armando Angrisani, Alexander Schmidhuber, Manuel S Rudolph, M Cerezo, Zoë Holmes, and Hsin-Yuan Huang. Classically estimating observables of noiseless quantum circuits. arXiv preprint arXiv:2409.01706, 2024. 10.48550/arXiv.2409.01706.
https://doi.org/10.48550/arXiv.2409.01706
arXiv:2409.01706

[46] Hale F Trotter. On the product of semi-groups of operators. Proceedings of the American Mathematical Society, 10 (4): 545–551, 1959. 10.2307/2033649.
https://doi.org/10.2307/2033649

[47] Masuo Suzuki. Generalized trotter's formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems. Communications in Mathematical Physics, 51 (2): 183–190, 1976. 10.1007/bf01609348.
https://doi.org/10.1007/bf01609348

[48] Christopher J Wood, Jacob D Biamonte, and David G Cory. Tensor networks and graphical calculus for open quantum systems. arXiv preprint arXiv:1111.6950, 2011. 10.26421/qic15.9-10-3.
https://doi.org/10.26421/qic15.9-10-3
arXiv:1111.6950

[49] Laurin E Fischer, Matea Leahy, Andrew Eddins, Nathan Keenan, Davide Ferracin, Matteo AC Rossi, Youngseok Kim, Andre He, Francesca Pietracaprina, Boris Sokolov, et al. Dynamical simulations of many-body quantum chaos on a quantum computer. arXiv preprint arXiv:2411.00765, 2024. 10.48550/arXiv.2411.00765.
https://doi.org/10.48550/arXiv.2411.00765
arXiv:2411.00765

Cited by

[1] Leonhard Moske, Pedro Ribeiro, Tomaž Prosen, Sergiy Denysov, Karol Życzkowski, and David J. Luitz, "Random-matrix perspective on probabilistic error cancellation", Physical Review A 114 1, 012442 (2026).

[2] Yi-Hsiang Chen, "Faster Probabilistic Error Cancellation", arXiv:2506.04468, (2025).

[3] Dawei Zhong, William Munizzi, Huo Chen, and Wibe Albert de Jong, "Combining Error Detection and Mitigation: A Hybrid Protocol for Near-Term Quantum Simulation", arXiv:2510.01181, (2025).

[4] Yi Yuan, Yuanchen Zhao, and Dong E. Liu, "Zeno-Enhanced Probabilistic Error Cancellation with Quantum Error Detection Codes", arXiv:2605.12149, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-19 12:44:08) and SAO/NASA ADS (last updated successfully 2026-08-19 12:44:09). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.