arXiv:2610.28845
Pushing beyond the memory barrier in propagation algorithms with randomization
Manuel S. Rudolph, Ricard Puig, Slimane Thabet, Zoë Holmes
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.
AI Summary
Pauli propagation can simulate circuit observables without storing a state vector, but branching under non-Clifford gates can exhaust memory. This paper studies how to continue propagation within a prescribed memory budget by trading additional computation for statistical precision. The protocol combines deterministic gate application, merging of duplicate Pauli strings, coefficient truncation, and stochastic compression when the stored expansion reaches its cap. Calibrated or semi-deterministic comb resampling retains dominant coefficients while sampling the remainder. Independent runs can be averaged in parallel. Benchmarks favor compressing only enough to accommodate the next gate—conservatively to $M/2$ strings for Pauli rotations—rather than aggressively reducing the expansion. Tests on a 30-qubit transverse-field Ising circuit, checked against exact state-vector simulation, show an apparent standard-deviation scaling near $M^{-1}$ at shallower depths, reverting toward $M^{-1/2}$ as coefficient distributions flatten. With $M=10^5$, biased randomized calculations approach or outperform deterministic calculations storing $4.2\times10^6$–$9.6\times10^6$ strings. Variance bounds depend on accumulated squared coefficient one-norms; a phenomenological model describes the truncation bias–variance trade-off. The CPU implementation reports approximately $10^9$ strings processed per second using 64 threads. An application estimates marginal collision entropies for a 64-qubit disordered Heisenberg experiment using independent replicas. Those estimates retain truncation and zero-clipping biases, excluded from statistical error bars, and are not fully converged at an intermediate coupling. More generally, averaging cannot remove truncation bias, and deep-circuit variance can still grow exponentially; the improved memory scaling is not established universally.
for the purposes of literature search, combining drafts, editing text, deriving and formatting equations, and implementing high-performance code.
Error found: The abstract's claim of several orders of magnitude less memory exceeds the explicit accuracy comparisons, which demonstrate 42-fold and 96-fold reductions in stored Pauli-string counts rather than measured total RAM. The abstract overgeneralizes the advantage of increasing per-run memory over independent averaging, since the reported faster memory scaling is regime-dependent and is explicitly expected to revert to ordinary Monte Carlo scaling for sufficiently flattened coefficient distributions.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 47 pages, 10 figures