arXiv:2610.21000
monoprop: Scaling Pauli and Majorana propagation via Anticommutation Indices
Aaron Miller
Abstract
We introduce monoprop, an open-source, massively parallel operator-propagation framework for fermion and qubit bases. For $N$ qubits or modes, existing codes represent each of the $K$ tracked operator terms (Pauli strings or products of Majorana operators) as a $2N$-bit string, testing each for anticommutation with the gate at $O(KN)$ cost per gate. Here, we introduce the anticommutation index which rapidly looks up the terms anticommuting with a gate. A local gate changes only the terms that touch its sites, and when terms are truncated to act on few sites, only a fraction $\sim1/N$ touch any given qubit or mode, and we use this to prove the time per gate scales as $O(K/N)$. This counterintuitive result tells us that for a fixed number of terms, increasing the number of sites can make things faster. We demonstrate this numerically, and show monoprop scales almost ideally to 8192 cores, tracking $9.5\times10^{10}$ terms. Beyond propagation, we present memory-efficient surrogate graphs, which record one propagation and replay it at new angles, for fast energy re-estimation and parameter gradients, and an efficient method for finding energy-minimising gates and optimal angles for simulating adaptive quantum-chemistry circuits.
AI Summary
Operator propagation approximates circuit expectation values by evolving sparse Pauli or Majorana expansions. This paper addresses the cost of finding and updating terms that anticommute with each gate, introducing `monoprop`, an open-source C++/Python framework with MPI parallelisation. Its central data structure is an anticommutation index: lists of tracked terms occupying each operator position. Taking the symmetric difference of the lists selected by a gate identifies anticommuting terms without scanning the entire expansion. For $K$ terms of bounded degree and local Pauli or even-Majorana gates, the proved per-gate cost is $O(K/N)$ when position occupancies remain balanced, and $O(K)$ in the worst case, versus the paper’s $O(KN)$ dense-bitstring baseline. Sparse term storage requires $O(d)$ rather than $O(N)$ memory per term. Single-core kicked-Ising and Hubbard benchmarks exhibit approximately inverse-system-size cost per tracked term, with reported speedups of $24$–$149\times$ at selected sizes. Distributed Hubbard benchmarks track $9.47\times10^{10}$ terms on 8192 cores, retaining 94% weak-scaling efficiency for the largest workload. Recorded surrogate graphs evaluate energies and all-parameter gradients in roughly 0.1 and 0.2 times propagation time. A separate Fock-reference gate-selection algorithm reduces exhaustive scoring from $O(N^{d+g})$ to expected $O(N^{(d+g)/2})$, supported by enumeration proofs and timing fits. The inverse-size bound requires bounded support and balanced occupancies, which are not guaranteed dynamically. The study benchmarks performance rather than physical accuracy or optimisation outcomes. Diagonal-term cutoff exemptions qualify degree-based bounds; gate-selection functionality is not yet included in the public release.
The author used Claude to improve clarity and to simplify long-winded proofs and for presentation.
Central claim may not hold: The abstract's O(K/N) per-gate claim requires an additional occupancy condition, such as the theorem's evenly supported operator assumption; bounded-degree terms and local gates alone permit Ω(K) work. The introduction incorrectly describes lookup time as proportional to the anticommuting output size, whereas commuting terms occurring in multiple selected lists can require substantial work even when that output is empty.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 9 pages, 6 figures