Pushing beyond the memory barrier in propagation algorithms with randomization
Abstract
Performant classical tools for simulating quantum circuits are important for benchmarking and supporting upcoming quantum devices. Pauli propagation offers promising capabilities, but deep circuits usually cause a rapid growth in the number of Pauli strings and can quickly exhaust the available memory. In this work, we introduce a randomized protocol that combines a specialized resampling schedule, merging, and a controlled amount of bias to keep the propagating Pauli sum within any prescribed memory budget. Additional computational resources can then be spent on embarrassingly parallel repetitions that systematically improve the estimate. Building on the open-source library PauliPropagation.jl, we show that 1) increasing memory of each simulation reduces the error systematically more than outside averaging, 2) resampling just enough to apply the next gate delays variance accumulation and gives better error-per-time trade-offs than more aggressive resampling, and 3) a small, controlled bias is crucial in cutting down variance and pushing far beyond unbiased randomization. The resulting framework can reproduce deterministic calculations while requiring several orders of magnitude less memory.
Related
- A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms
- Fast convergence of propagation algorithms for open quantum systems
- Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability
- Pushing the Primordial Frontier: Exact Linear Solutions in Multifield Inflation
- Pushing the Dose Limit of Atomic-Resolution Imaging: A 4D-STEM case study of NaCl
BibTeX
@misc{rudolph2026pushing,
title = {{Pushing beyond the memory barrier in propagation algorithms with randomization}},
author = {Manuel S. Rudolph and Ricard Puig and Slimane Thabet and Zoë Holmes},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28845},
eprint = {2610.28845},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28845},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Pushing beyond the memory barrier in propagation algorithms with randomization
AU - Manuel S. Rudolph
AU - Ricard Puig
AU - Slimane Thabet
AU - Zoë Holmes
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.28845
UR - https://arxiv.org/abs/2610.28845
AB - Performant classical tools for simulating quantum circuits are important for benchmarking and supporting upcoming quantum devices. Pauli propagation offers promising capabilities, but deep circuits usually cause a rapid growth in the number of Pauli strings and can quickly exhaust the available memory. In this work, we introduce a randomized protocol that combines a specialized resampling schedule, merging, and a controlled amount of bias to keep the propagating Pauli sum within any prescribed memory budget. Additional computational resources can then be spent on embarrassingly parallel repetitions that systematically improve the estimate. Building on the open-source library PauliPropagation.jl, we show that 1) increasing memory of each simulation reduces the error systematically more than outside averaging, 2) resampling just enough to apply the next gate delays variance accumulation and gives better error-per-time trade-offs than more aggressive resampling, and 3) a small, controlled bias is crucial in cutting down variance and pushing far beyond unbiased randomization. The resulting framework can reproduce deterministic calculations while requiring several orders of magnitude less memory.
ER -