betaFeedback

WorksPhysics and Astronomy

Scalable Pauli propagation through F2\mathbb{F}_2-linear partitioning

Abstract

Pauli propagation simulates quantum circuits and many-body dynamics by evolving observables in the Heisenberg picture as sparse sums of Pauli strings. As Pauli-string operations reduce to bit manipulations, its performance is limited by memory bandwidth and capacity rather than computational throughput. Pooling the memory of many cores and nodes is hindered by the deduplication step after every gate, which can require global synchronization. We avoid this bottleneck by partitioning the strings with an F2\mathbb{F}_2-linear hash function, which guarantees that a kk-qubit channel couples each partition to at most 4k4^k partitions fixed by the gate, decomposing gate application into independent tasks with bounded communication. Benchmarks of our open-source implementation demonstrate efficient parallel scaling within and across compute nodes, enabling simulations with over 101110^{11} Pauli strings and extending the accessible timescales of quantum many-body dynamics.

Introduction

Classical simulation methods are central to the study of quantum many-body systems and the development of quantum technologies, providing both theoretical insight and benchmarks for quantum experiments. For example, the kicked Ising experiment on a 127-qubit superconducting processor [1] was quickly followed by classical simulations that matched or surpassed its accuracy [2, 3, 4, 5, 6]. Among these methods is Pauli propagation, which evolves observables in the Heisenberg picture as sums of Pauli strings. Its cost depends only on the number of terms, which Clifford gates leave unchanged, making it particularly effective for near-Clifford and certain noisy circuits, where its efficiency is rigorously established [7, 8, 9, 10, 11], and it has also proven effective for the real-time dynamics of local observables [12, 13].

Pauli propagation can be implemented efficiently using the binary symplectic representation, which encodes each Pauli string as a pair of bitstrings and reduces multiplication and commutation checks to simple bitwise operations [13, 14, 15, 16, 17, 18, 19, 20]. Since individual string operations are cheap, large-scale simulations are limited by memory: its bandwidth sets the propagation rate [21], and its capacity the number of strings that can be retained, and hence the achievable accuracy. This motivates distributing the expansion over many processors and nodes [20].

Although strings can be evolved independently, different inputs can produce identical outputs, whose coefficients must be summed in a deduplication step. In a naive parallel implementation, this requires global communication and synchronization, introducing an overhead that grows with the number of processes. To avoid this, we partition the strings with an F2\mathbb{F}_2-linear hash function. By linearity, multiplication by a fixed Pauli string maps every partition as a whole onto a single other partition.

Since a Pauli rotation combines this multiplication with the identity, each partition couples to at most one other, replacing global communication with independent pairwise exchanges and allowing deduplication to be performed locally, as illustrated in Figure 1. The number of partitions can be chosen independently of the number of workers, allowing task sizes to be optimized for cache locality and improving performance even on a single core.

Naive versus F2-linear partitioning for successive Pauli rotations

Figure 1. Naive versus F2\mathbb{F}_2-linear partitioning for successive Pauli rotations. Grey squares denote partitions between gates, and red lines indicate possible exchanges. (a) Naive partitioning permits near-all-to-all communication. (b) F2\mathbb{F}_2-linear hashing shifts partition labels by a gate-dependent XOR offset, restricting exchanges to predetermined pairs.

We benchmark our open-source implementation, paulistrings-rs [22], on the kicked Ising circuit of Ref. [1] and quenches of the two-dimensional transverse-field Ising model [12, 23]. Within a node, the implementation exhibits near-ideal scaling until memory bandwidth becomes limiting. Across nodes, it achieves substantial parallel speedups while maintaining weak-scaling efficiencies of 68–74% at 32 nodes, supporting aggregate budgets of up to 1.6×10111.6 \times10^{11} Pauli strings. By exploiting the combined memory capacity of multiple nodes, the implementation enables larger Pauli expansions and extends the accessible timescales of classical quantum dynamics simulations.

Methods

Pauli propagation represents operators as sparse sums of Pauli strings,

O=∑i=1NciPi,(1)O = \sum_{i=1}^{N} c_i P_i, \tag*{(1)}

where every Pi∈{I,X,Y,Z}⊗LP_i \in\{I,X,Y,Z\}^{\otimes L} for a system of LL qubits. Pauli strings span the 4L4^L-dimensional operator space, and many operators admit sparse representations with N≪4LN \ll4^L. Pauli propagation evolves these expansions through successive gate applications, updating the strings and their coefficients. This approach remains efficient when the number of strings required to approximate the operator of interest remains manageable, as is often the case for a variety of applications [12, 13, 17].

To manipulate these expansions efficiently, we use the symplectic encoding of Pauli strings [14]. Each single-qubit Pauli operator is represented by two bits (x,z)∈F22(x,z) \in\mathbb{F}_2^2, with the phase convention P(x,z)=ixzXxZzP(x,z) = i^{xz}X^xZ^z ensuring Hermiticity. For LL qubits, these bits form a vector over the binary field, p=(px∣pz)∈F22L\boldsymbol{p} = (p^x \mid p^z) \in\mathbb{F}_2^{2L}, representing the string

P(p)=iNY(p)⨂j=1LXjpjxZjpjz,(2)P(\boldsymbol{p}) = i^{N_Y(\boldsymbol{p})} \bigotimes_{j=1}^{L} X_j^{p_j^x} Z_j^{p_j^z}, \tag*{(2)}

where NY(p)=∣px∧pz∣N_Y(\boldsymbol{p}) = |\boldsymbol{p}^x \wedge\boldsymbol{p}^z| counts the number of YY factors, ∧\wedge denotes bitwise AND, and ∣⋅∣|\cdot| the Hamming weight.

In this encoding, multiplication of two Pauli strings reduces to bitwise XOR ⊕\oplus, up to a phase,

P(p)P(q)=iκ(p,q)P(p⊕q),(3)P(\boldsymbol{p})P(\boldsymbol{q}) = i^{\kappa(\boldsymbol{p},\boldsymbol{q})}P(\boldsymbol{p}\oplus\boldsymbol{q}), \tag*{(3)}

where the phase follows from commuting ZpzZ^{p^z} past XqxX^{q^x}, which gives a minus sign wherever both act,

κ(p,q)=NY(p)+NY(q)−NY(p⊕q)+2∣pz∧qx∣.(4)\kappa(\boldsymbol{p},\boldsymbol{q}) = N_Y(\boldsymbol{p}) + N_Y(\boldsymbol{q}) - N_Y(\boldsymbol{p}\oplus\boldsymbol{q}) + 2|\boldsymbol{p}^z \wedge\boldsymbol{q}^x|. \tag*{(4)}

Commutation is determined by the symplectic product

s(p,q)=pTJq,J=(0II0),(5)s(\boldsymbol{p},\boldsymbol{q}) = \boldsymbol{p}^{T}J\boldsymbol{q}, \qquad J = \begin{pmatrix} 0 & I \\ I & 0 \end{pmatrix}, \tag*{(5)}

such that PQ=(−1)s(p,q)QPPQ = (-1)^{s(\boldsymbol{p},\boldsymbol{q})}QP, where the symplectic form JJ over F2\mathbb{F}_2 gives the encoding its name.

A gate generally maps each input Pauli string to a linear combination of output strings, with the number of terms defining the branching ratio. A Pauli rotation RQ(θ)=exp⁡(−i2θQ)R_Q(\theta) = \exp(-\frac{i}{2}\theta Q) transforms a string PP depending on whether it commutes or anticommutes with QQ:

RQ†(θ)PRQ(θ)={P,s(p,q)=0,cos⁡θ P+isin⁡θ QP,s(p,q)=1.(6)R_Q^\dagger(\theta) P R_Q(\theta) = \begin{cases} P, & s(\boldsymbol{p},\boldsymbol{q}) = 0,\\ \cos\theta\,P + i\sin\theta\,QP, & s(\boldsymbol{p},\boldsymbol{q}) = 1. \end{cases} \tag*{(6)}

Pauli rotations, with a branching ratio of at most 2, are the elementary gates used in the Trotterized simulations considered below.

After each gate application, the output strings must be collected into an expansion of the form of Eq. (1), with each string appearing once. Duplicate Pauli strings can be generated by the gate, and these must then be identified and their coefficients summed in a deduplication step. When gate applications are parallelized, strings are distributed across processes, but naive partitioning can generate duplicate strings on different processes, in which case deduplication requires global communication. To avoid this, we introduce an F2\mathbb{F}_2-linear hashing scheme that decomposes gate applications into independent tasks involving a bounded number of partitions, enabling predictable communication and local deduplication.

In this scheme, as shown in Figure 2(a), a binary matrix M∈F2B×2LM \in\mathbb{F}_2^{B \times2L} assigns each Pauli string to one of 2B2^B partitions,

F2-linear partitioning and multiplication

Figure 2. F2\mathbb{F}_2-linear partitioning and multiplication. (a) The Pauli string P=Y1Z3P = Y_1Z_3 has bit vector p=(px∣pz)∈F22L\boldsymbol{p} = (\boldsymbol{p}^x \mid\boldsymbol{p}^z) \in\mathbb{F}_2^{2L}. The binary hash matrix MM assigns it the label b=Mp\boldsymbol{b} = M\boldsymbol{p}, computed mod 2, and hence the partition Bb\mathcal{B}_{\boldsymbol{b}}. Each partition stores the strings pb,i\boldsymbol{p}_{b,i} and coefficients cb,ic_{b,i} of the operator ObO_b. (b)–(c) Multiplication by Q=X1X2Q = X_1X_2, with bitvector q\boldsymbol{q}, maps p\boldsymbol{p} to p⊕q\boldsymbol{p} \oplus\boldsymbol{q} and the label b\boldsymbol{b} to b⊕δ\boldsymbol{b} \oplus\boldsymbol{\delta} with δ=Mq\boldsymbol{\delta} = M\boldsymbol{q} (b). Every partition is therefore mapped to a single partner, and the partitions are exchanged in pairs (c). Shown here is the case L=3L = 3, B=2B = 2. Labels are written as b=b1b2\boldsymbol{b} = b_1b_2, and filled (empty) squares denote 1 (0).

Bb={P(p)∣Mp=b},b∈F2B,(7)\mathcal{B}_{\boldsymbol{b}} = \{P(\boldsymbol{p}) \mid M\boldsymbol{p} = \boldsymbol{b}\}, \qquad\boldsymbol{b} \in\mathbb{F}_2^B, \tag*{(7)}

and by linearity M(p⊕q)=Mp⊕MqM(\boldsymbol{p} \oplus\boldsymbol{q}) = M\boldsymbol{p} \oplus M\boldsymbol{q}. Consequently, multiplication by a fixed Pauli string QQ maps every string in Bb\mathcal{B}_{\boldsymbol{b}} to Bb⊕Mq\mathcal{B}_{\boldsymbol{b}\oplus M\boldsymbol{q}}, as illustrated in Fig. 2(b). Unlike the hash-based distribution in ORQA [20], this restricts communication to a single predetermined partner per partition, avoiding string-dependent routing, as shown in Fig. 2(c).

A Pauli rotation RQ(θ)R_Q(\theta) maps each string P∈BbP \in\mathcal{B}_{\boldsymbol{b}} to a combination of PP and QPQP as shown in Eq. (6). The former remains in Bb\mathcal{B}_{\boldsymbol{b}}, while the latter belongs to Bb⊕Mq\mathcal{B}_{\boldsymbol{b}\oplus M\boldsymbol{q}}. Therefore, each partition interacts with at most one other partition, forming independent pairs that can be updated and deduplicated separately.

More generally, any gate or channel acting on kk qubits maps P(p)P(\boldsymbol{p}) to a linear combination of strings P(p⊕d)P(\boldsymbol{p}\oplus\boldsymbol{d}), where dd is supported only on those qubits. By linearity of the hash, the output partition label is M(p⊕d)=b⊕MdM(p \oplus d) = b \oplus Md. Let WU⊆F22LW_U \subseteq\mathbb{F}_2^{2L} denote the span of all such offsets, and DU=MWUD_U = MW_U their image under the hash. Since the offsets involve at most 2k2k binary coordinates,

dU=dim⁡DU≤min⁡(B,2k).(8)d_U = \dim D_U \le\min(B,2k). \tag*{(8)}

Each partition BbB_b can therefore exchange strings only with partitions labeled by b⊕DUb \oplus D_U. These labels form a coset of DUD_U, which is closed under all offsets generated by the gate. Consequently, the 2B2^B partitions split into 2B−dU2^{B-d_U} disjoint groups, each containing 2dU≤4k2^{d_U} \le4^k partitions. Each group forms an independent task that can be updated and deduplicated without communication with other groups.

The choice of MM involves a tradeoff between balancing the number of strings across partitions and minimizing communication between them. A uniformly random full-rank matrix provides approximately universal hashing, with distinct strings colliding with probability close to 2−B2^{-B} [24], yielding approximately balanced partitions when N≫2BN \gg2^B. However, MM can also be optimized for the specific simulation and hardware, for example to reduce the communication between compute nodes. We discuss this trade-off in more detail in App. A.

The decomposition into independent groups of work provides the basis for both shared-memory parallelism as well as distributed-memory communication. Within a node, these tasks are distributed over the threads by work stealing scheduling, which balances their uneven sizes. Since tasks update disjoint partitions, no locking is required, and threads synchronize only after completing each gate. For distributed execution, additional hash bits assign partitions to NUMA domains or MPI processes, b=(bnode∣blocal)b = (b_{\mathrm{node}} \mid b_{\mathrm{local}}). The gate-dependent offsets determine the communication partners in advance, enabling bounded point-to-point exchanges. Truncation and measurement require at most a scalar or histogram reduction over the partitions, as discussed in App. B. This partitioning also benefits single-worker performance by reducing the deduplication working set to fit within processor caches, as discussed in App. C. Together, these features enable effective use of available computing resources, as demonstrated in § 3.

Results

Kicked Ising dynamics

We first use our implementation to apply a kicked Ising circuit on the 127-qubit heavy-hex lattice introduced in Ref. [1], a standard benchmark for Pauli propagation methods [3, 17, 25]. Every Trotter step applies the unitary circuit

U=[∏⟨jk⟩exp⁡(iπ4ZjZk)][∏jexp⁡(−iθh2Xj)],(9)U = \left[\prod_{\langle jk\rangle} \exp\left(i\frac{\pi}{4}Z_jZ_k\right)\right]\left[\prod_j \exp\left(-i\frac{\theta_h}{2}X_j\right)\right], \tag*{(9)}

where ⟨jk⟩\langle jk\rangle denotes nearest-neighbor pairs, and θh\theta_h is the angle of the transverse-field kick, here fixed to θh=π/4\theta_h = \pi/4. Using the initial product state ∣0⟩⊗127\lvert0\rangle^{\otimes127}, we calculate the single-site magnetization ⟨Z62⟩\langle Z_{62}\rangle after 20 Trotter steps. Coefficients are truncated using an absolute threshold ∣ci∣≤δ\lvert c_i\rvert\le\delta, with alternative truncation methods detailed in App. B.

We first examine the strong scaling on a single two-socket node, where ideal performance corresponds to wall time inversely proportional to the number of threads. Figure 3(a) shows the wall time per Trotter step as a function of thread count, for δ=2.5×10−5\delta= 2.5 \times10^{-5} and δ=5.0×10−6\delta= 5.0 \times10^{-6}. The single-partition configuration uses a shared thread pool, while the two-partition configuration assigns the expansion to separate NUMA domains using the lattice-cut hash of App. A 3. The two-partition configuration is used for the multi-node benchmarks below. Efficiencies are measured relative to the first point of the curve, at T=1T = 1 and T=2T = 2, respectively.

Figure 3. Strong scaling of the wall time of ⟨Z62⟩\langle Z_{62}\rangle for the kicked Ising circuit (127 qubits, θh=π/4\theta_h = \pi/4, 20 Trotter steps). Dashed lines indicate ideal scaling, with percentages giving the corresponding parallel efficiencies relative to the first point of each curve. (a) Scaling on a single two-socket AMD EPYC 9474F node, for a single pool of threads (one partition) and with two partitions assigned to the two NUMA domains by a lattice-cut node hash. (b) Scaling on across multiple nodes, with one MPI rank per NUMA domain partitioned according to the avoid 50% hash (see App. A 3). Each curve begins at the smallest number of nodes whose combined memory holds the operator.

Scaling is close to ideal up to 16 threads, after which efficiency gradually decreases, reaching 61% for δ=5×10−6\delta= 5 \times10^{-6} and 38% for δ=2.5×10−5\delta= 2.5 \times10^{-5} at 96 threads. The deviation from ideal is consistent with saturation of the available memory bandwidth, as discussed in App. C. The larger cutoff produces a smaller Pauli expansion, so fixed per-gate and per-task overheads account for a larger fraction of its wall time, causing an earlier deviation from ideal scaling. The two-partition configuration is slower at low thread counts, where the single-partition configuration benefits from keeping the entire expansion within one NUMA domain, but becomes faster at 64 threads and above by improving memory locality.

We next examine strong scaling across multiple nodes, where aggregate memory makes smaller thresholds accessible. Figure 3(b) shows the wall time as a function of node count for several δ\delta using two MPI ranks per node (one per NUMA domain) and the avoid f=50%f = 50\% node hash of App. § 3.1 § 8. Each curve starts at the minimum number of nodes required to accommodate the operator, increasing from one node at δ=2.5×10−6\delta= 2.5 \times10^{-6} to four nodes for δ=7.5×10−7\delta= 7.5 \times10^{-7}. For the three thresholds, wall time decreases monotonically, reaching efficiencies of 28%, 58%, and 67%, respectively. At a fixed number of nodes, a smaller threshold takes longer, since it retains more strings. As in the single-node benchmarks, larger operators exhibit better parallel efficiency, as fixed overheads become relatively less significant. The hash optimizations of App. § 3.1 § 8 are also more effective at smaller node counts, reducing the baseline wall time and thereby lowering the measured strong-scaling efficiency. These results show that F2_2-linear partitioning enables substantial parallel speedups within and across compute nodes.

Two-dimensional transverse field Ising model

Next we consider quench operator dynamics in the two-dimensional transverse field Ising model on a square lattice with open boundaries,

H=−J∑⟨jk⟩ZjZk−h∑jXj,(10)H = -J \sum_{\langle jk\rangle} Z_j Z_k - h \sum_j X_j, \tag*{(10)}

where JJ is the ferromagnetic coupling and hh is the strength of the transverse field. Near the critical field hc/J≈3.04438h_c/J \approx3.04438 [26], Pauli expansions of local operators grow rapidly [12], making this system a demanding benchmark for evaluating weak scaling and the ability to exploit the combined memory capacity of multiple nodes. In Figure 4, we examine the weak scaling on a 16×1616 \times16 lattice: starting from the product state ∣0⟩⊗256|0\rangle^{\otimes256} we quench to h/J=3.04h/J = 3.04 and compute the spatially averaged magnetization, ⟨Z(t)⟩=256−1∑j⟨Zj(t)⟩\langle Z(t)\rangle= 256^{-1}\sum_j\langle Z_j(t)\rangle, over 20 second-order Trotter steps with Jδt=0.1J\delta t = 0.1. Instead of a coefficient threshold, we use the per-worker truncation scheme of App. § 4, fixing the retained-string budget per compute node NPN_P and dividing it equally between two MPI ranks, one per NUMA domain. Strings are distributed using the avoid f=50%f = 50\% node hash described in App. § 3.1. For weak scaling, we keep NPN_P, the string budget per thread, fixed as the number of nodes increases, with ideal scaling corresponding to constant wall time per Trotter step. Figure 4 shows the wall time per step from 1 to 32 nodes, with fixed per-node budgets of 5×1085 \times10^{8}, 2×1092 \times10^{9}, and 5×1095 \times10^{9} strings. At 32 nodes, weak-scaling efficiency remains between 68% and 74%, improving with the per-node string budget. At the largest budget, 160 billion strings, around 10 TiB are retained after deduplication and truncation, with total memory usage peaking at approximately 28.8 TiB, out of the 47 TiB available across 32 nodes. This demonstrates the ability to exploit the memory capacity of multiple nodes while maintaining efficient parallel scaling.

Figure 4. Weak scaling of the wall time per Trotter step of the 16×1616 \times16 transverse-field Ising quench, at fixed per-node string budgets of NP=5×108N_P = 5 \times10^8, 2×1092 \times10^9, and 5×1095 \times10^9. Strings are distributed using the avoid f=50%f = 50\% hash of App. § 3.1 § 8, across AMD EPYC 9474F sockets, two of which live on each 96-core, 1.47 TiB node. At 32 nodes, the largest configuration supports up to 1.6×10111.6 \times10^{11} Pauli strings, corresponding to 10.5 TiB of storage after deduplication and truncation, or 22% of the available memory.

To assess how the increased memory capacity of our implementation improves convergence, we reproduce the 14 ×\times 14 quench of Ref. [23], starting from ∣1⟩⊗196\lvert1\rangle^{\otimes196} and evolving the central-site magnetization ⟨Z105(t)⟩\langle Z_{105}(t)\rangle at h/J=3h/J = 3. We evolve over 40 second-order Trotter steps with Jδt=0.05J\delta t = 0.05, with the only truncation being coefficient thresholds δ\delta ranging from 10−410^{-4} to 2.5×10−72.5 \times10^{-7}. As shown in Figure 5(a), decreasing the threshold extends the time range over which the magnetization converges. At the smallest threshold, the expansion reaches 1.64×10111.64 \times10^{11} Pauli strings (about 11 TiB), distributed over 64 nodes. The corresponding retained operator norm, ∑s∣cs∣2\sum_s \lvert c_s\rvert^2, is shown in Figure 5(b). At tJ=1tJ = 1, the smallest threshold retains 99.1% of the exact squared operator norm, indicating that only a small fraction of the operator weight has been discarded. Finally, Figure 5(c) compares our Pauli propagation (PP) with results from Ref. [23] using matrix product states (MPS), tree tensor network (TTN), and two-dimensional tensor networks with belief propagation (2DTN). Within the convergence limits of MPS and TTN, indicated by vertical lines according to the symmetry-based criterion of that reference, all four methods agree. At later times, the predictions diverge due to differing approximations, and the reference calculations no longer provide a converged benchmark for quantitative accuracy. Together, these results show that distributed memory, usable with our implementation, enables substantially larger Pauli expansions while maintaining efficient parallel scaling, extending the range of accessible dynamics.

Figure 5. Central-site magnetization ⟨Z105(t)⟩\langle Z_{105}(t)\rangle for the 14×1414 \times14 transverse-field Ising quench from ∣1⟩⊗196|1\rangle^{\otimes196} to h/J=3h/J = 3, using 40 second-order Trotter steps with Jδt=0.05J\delta t = 0.05. (a) Magnetization and (b) retained squared operator norm ∑s∣cs∣2\sum_s |c_s|^2 for coefficient thresholds δ=10−4\delta= 10^{-4} to 5×10−75 \times10^{-7}. (c) Pauli propagation (PP) at δ=5×10−7\delta= 5 \times10^{-7} compared with the MPS, TTN, and 2DTN-BP results of Ref. [23]. The Pauli propagation results are consistent up to the solid gray and dashed orange lines which indicate the symmetry-based convergence limits of MPS and TTN, respectively, from Ref. [23].

Discussion and Outlook

Pauli propagation is a competitive classical simulation method for quantum dynamics, but its scalability is typically constrained by the memory bandwidth and capacity required to manipulate large Pauli expansions. In this work, we introduced an F2F_2-linear partitioning scheme to enable scalability by distributing Pauli expansions across processors and compute nodes, such that gate applications are split into independent tasks with bounded communication. This partitioning improves memory locality and enables the aggregate memory bandwidth and capacity of multiple nodes to be exploited, allowing larger simulations with efficient parallelization.

Both benefits of the partitioning concern memory. Within a node, improved memory locality reduces data movement and enables more effective use of the available memory bandwidth. Across nodes, the scheme enables the combined memory capacity to be exploited efficiently, requiring only point-to-point exchanges of Pauli strings rather than global redistribution. Benchmarks on the kicked Ising circuit and the two-dimensional transverse field Ising model demonstrate substantial parallel speedups within and across compute nodes. Our distributed-memory simulations reach Pauli expansions exceeding 101110^{11} strings, extending the time range over which the simulated dynamics converge.

The remaining opportunities for performance improvements lie in reducing memory traffic and communication overhead. For distributed execution, gates that couple workers still require pairwise exchanges and a brief synchronization, whose cost grows with the fraction of exchanging gates. Tailoring the node hash to the circuit and number of nodes can reduce the fraction, although maintaining a balanced distribution of strings becomes increasingly challenging as the number of workers grows (see A3). Single-node propagation remains limited by memory bandwidth, so further performance gains must come from hardware-specific optimizations that reduce the amount of data moved per string and gate, as discussed in App. § 10.

The partitioning strategy is independent of the underlying storage format and truncation scheme, allowing it to be incorporated into existing Pauli propagation implementations without altering their propagation algorithms. A natural next step is to extend this approach to GPU-based implementations, where the benefit of the added memory bandwidth traditionally is hindered by the limited memory capacity. Our methods thus provide the natural strategy for Pauli propagation methods to exploit modern parallel hardware, from the cores of a single node to many nodes. With this, Pauli propagation makes for a competitive classical simulation method, enabling larger and more accurate simulations of quantum many-body dynamics.

**Note added.—**During the preparation of this manuscript, related F2F_2-linear partitionings were also introduced for the distribution over MPI ranks in monprop [27].

Acknowledgments

L.D. thanks Nicolas Loizeau for the collaboration on PauliStrings.jl [13] that led to the idea for this project. A.O. and A.K. acknowledge support from the Pierre Hohenberg Graduate Scholar Fellowship and computational resources provided by the Flatiron Institute. J.D. and L.D. are grateful for ongoing support by the Flatiron Institute. The Flatiron Institute is a division of the Simons Foundation.

Linear hash details

Linear partitioning

A hash function h:F22L→F2Bh:\mathbb{F}_2^{2L}\to\mathbb{F}_2^B assigns every Pauli string P(p)P(\mathbf{p}) to the partition Bh(p)\mathcal{B}_{h(\mathbf{p})}. The hash is F2\mathbb{F}_2-linear if

h(p⊕q)=h(p)⊕h(q)for all p,q∈F22L.(11)h(\mathbf{p}\oplus\mathbf{q})=h(\mathbf{p})\oplus h(\mathbf{q})\quad\text{for all }\mathbf{p},\mathbf{q}\in\mathbb{F}_2^{2L}. \tag*{(11)}

Every such hash can be represented as h(p)=Mph(\mathbf{p})=M\mathbf{p} for a binary matrix M∈F2B×2LM\in\mathbb{F}_2^{B\times2L}. Each row mj\mathbf{m}_j of MM selects a subset of bits from the binary representation p\mathbf{p}, whose parity determines the corresponding partition label bit, bj=mj⋅p=∣mj∧p∣ mod 2b_j=\mathbf{m}_j\cdot\mathbf{p}=|\mathbf{m}_j\wedge\mathbf{p}|\bmod2. By linearity, the partition containing the identity string is the kernel K=ker⁡MK=\ker M, a linear subspace of dimension 2L−rank⁡M2L-\operatorname{rank}M. Every other partition is a coset of KK,

Bb=pb⊕K,with Mpb=b.(12)\mathcal{B}_{\mathbf{b}}=\mathbf{p}_{\mathbf{b}}\oplus K,\quad\text{with }M\mathbf{p}_{\mathbf{b}}=\mathbf{b}. \tag*{(12)}

For full-rank MM, all 2B2^B partitions therefore contain the same number 4L/2B4^L/2^B of possible strings. Moreover, multiplication by any Pauli string Q=P(q)Q=P(\mathbf{q}) maps Bb\mathcal{B}_{\mathbf{b}} onto Bb⊕Mq\mathcal{B}_{\mathbf{b}\oplus M\mathbf{q}} as a whole.

Conversely, this property characterizes linear partitioning up to relabeling. For any k∈K\mathbf{k}\in K, multiplication by P(k)P(\mathbf{k}) maps the identity to P(k)P(\mathbf{k}). Since multiplication maps whole partitions onto partitions, it must map KK onto itself. Thus k⊕K=K\mathbf{k}\oplus K=K for every k∈K\mathbf{k}\in K, proving that KK is closed under ⊕\oplus and is therefore a linear subspace. Similarly, multiplication by any P(p)P(\mathbf{p}) maps KK onto the partition containing P(p)P(\mathbf{p}), which is precisely the coset p⊕K\mathbf{p}\oplus K. Since every linear subspace is the kernel of some linear map, these cosets define a F2\mathbb{F}_2-linear hash up to relabeling.

For common classes of gates, the offset space DUD_U of Eq. (8), which sets the number of partitions involved in each task, can be determined explicitly. A Pauli rotation maps every string to itself and to QPQP, so WU=span⁡{q}W_U=\operatorname{span}\{\mathbf{q}\} and dU≤1d_U\leq1 regardless of the weight of QQ. When Mq=0M\mathbf{q}=0, no interpartition communication is required. For a dense gate or channel acting on kk qubits, the offsets can span the full 2k2k-dimensional binary space supported on those qubits, giving dU≤min⁡(2k,B)d_U\leq\min(2k,B).

A Clifford gate maps each Pauli string to a single string up, p↦Sp=p⊕Δp\mathbf{p}\mapsto S\mathbf{p}=\mathbf{p}\oplus\Delta\mathbf{p} up to a sign, where S=I+ΔS=I+\Delta is a symplectic matrix. Therefore, propagation requires only updating the strings and routing them to their destination partitions, without generating additional strings or requiring deduplication. The offset space is therefore WU=im⁡ΔW_U=\operatorname{im}\Delta, giving

dU=rank⁡(MΔ)≤rank⁡(S+I).(13)d_U=\operatorname{rank}(M\Delta)\leq\operatorname{rank}(S+I). \tag*{(13)}

For the standard single- and two-qubit Clifford generators, rank⁡(S+I)≤1\operatorname{rank}(S+I)\leq1 and rank⁡(S+I)≤2\operatorname{rank}(S+I)\leq2, respectively, as listed in Table I. For any p=pb⊕k\mathbf{p}=\mathbf{p}_{\mathbf{b}}\oplus\mathbf{k} with k∈K\mathbf{k}\in K, the output partition label is,

GateBit updaterank⁡(S+I)\operatorname{rank}(S+I)
HjH_jpjx↔pjzp_j^x\leftrightarrow p_j^z1
SjS_jpjz←pjz⊕pjxp_j^z\leftarrow p_j^z\oplus p_j^x1
CNOT⁡c→t\operatorname{CNOT}_{c\to t}ptx←ptx⊕pcx,pcz←pcz⊕ptzp_t^x\leftarrow p_t^x\oplus p_c^x,\quad p_c^z\leftarrow p_c^z\oplus p_t^z2
CZ⁡jk\operatorname{CZ}_{jk}pjz←pjz⊕pkx,pkz←pkz⊕pjxp_j^z\leftarrow p_j^z\oplus p_k^x,\quad p_k^z\leftarrow p_k^z\oplus p_j^x2

Table I. Bit updates of the standard Clifford generators on a string p=(px∣pz)\mathbf{p}=(p^x\mid p^z), which leave all other bits unchanged, together with the bound rank⁡(S+I)\operatorname{rank}(S+I) of Eq. (13) on the number of offset directions.

MSp=b⊕MΔpb⊕MΔk.(14)MS\mathbf{p}=\mathbf{b}\oplus M\Delta\mathbf{p}_{\mathbf{b}}\oplus M\Delta\mathbf{k}. \tag*{(14)}

Therefore, strings from the partition b\mathbf{b} can reach only partitions labeled by b⊕MΔpb⊕MΔ(K)\mathbf{b}\oplus M\Delta\mathbf{p}_{\mathbf{b}}\oplus M\Delta(K), at most 2d2^d of them with d=dim⁡MΔ(K)≤dUd=\dim M\Delta(K)\leq d_U. This routing depends only on the hash and the gate and can be precomputed. For full-row-rank MM, a right inverse M+M^+ determines the base offset MΔM+bM\Delta M^+\mathbf{b} for each partition, while the columns of MΔNM\Delta N, where NN is a basis matrix for KK, span the remaining possible offsets.

Linear hashes are also a classic universal family [24]. For a uniformly random MM, two distinct strings collide with probability

Pr⁡[M(p⊕q)=0]=2−B,(15)\Pr[M(\mathbf{p}\oplus\mathbf{q})=0]=2^{-B}, \tag*{(15)}

since each row is independently orthogonal to the nonzero vector p⊕q\mathbf{p}\oplus\mathbf{q} with probability 1/21/2. However, this collision guarantee holds only on average over MM and does not ensure balanced partitions for a fixed hash or fixed circuit. For a fixed MM and circuit, partition balance depends on how the strings are distributed over the cosets of ker⁡M\ker M, as discussed in App. § 3.1.§ 8.

Implementation

Evaluating the hash from scratch requires computing BB parities, costing O(BL)O(BL) operations per string. Once a partition label is known, linearity allows it to be updated incrementally, as b↦b⊕Md\mathbf{b}\mapsto\mathbf{b}\oplus M\mathbf{d}, where d\mathbf{d} is the offset generated by a gate. For a gate acting on kk qubits, the 4k4^k possible offsets MdM\mathbf{d} can be precomputed, reducing routing to a table lookup and XOR.

For distributed execution, the hash label is split into node and local components, b=(bnode∣blocal)\mathbf{b}=(\mathbf{b}_{\mathrm{node}}\mid\mathbf{b}_{\mathrm{local}}) corresponding to row blocks MnodeM_{\mathrm{node}} and MlocalM_{\mathrm{local}} of MM. The former assigns strings to workers, while the latter determines their partition within each worker. The node part is fixed for the whole simulation, since changing it generally moves strings between all workers. We draw the local rows at random, such that MM as a whole is a random full-rank matrix and every local partition can be used.

As the number of strings varies by orders of magnitude during a simulation, we dynamically adjust the number of local partitions to keep the mean partition size close to a target, as discussed in more detail in App. § 10. The hash uses the first BB rows of a fixed, full-rank matrix with at most 2L2L rows, with the node-assignment rows placed first. Increasing or decreasing BB activates or deactivates additional rows for local partitioning, leaving the node assignments unchanged. Since each BB-bit label is a prefix of the corresponding (B+1)(B+1)-bit label, adding a row splits each partition BbB_b into B(b,0)B_{(b,0)} and B(b,1)B_{(b,1)}, requiring only one additional parity per string. Removing the row merges these partitions back, without recomputing other label bits or transferring strings between workers. This adaptation therefore requires no global synchronization. Furthermore, each worker can adjust BB independently, coordinating only with workers coupled by a gate when strings must be exchanged. At these exchanges, the participating workers adopt the largest of their BB values to ensure consistent partition labels.

Choosing the node hash

The choice of the node hash, MnodeM_{\mathrm{node}}, involves a trade-off between evenly distributing strings across workers and minimizing costly interworker communication. We quantify the load imbalance by λ=Nmax⁡/Nˉ\lambda= N_{\max}/\bar{N}, where Nmax⁡N_{\max} is the maximum number of strings held by any worker and Nˉ\bar{N} is the mean number of strings per worker. For a Trotter step composed of Pauli rotations, we quantify communication by fexf_{\mathrm{ex}}, the fraction of gates satisfying Mnodeq≠0M_{\mathrm{node}}q \ne0, which can exchange strings between workers. Unlike the load imbalance, fexf_{\mathrm{ex}} depends only on the hash and the circuit, and is thus easy to compute beforehand. We illustrate this trade-off using the 127-qubit kicked Ising circuit, starting from the single-site observable Z62Z_{62}.

The two objectives compete because the same gates that generate new Pauli strings also determine how they are distributed across workers. Every string in the propagated operator is obtained from the initial observable Z62Z_{62} by multiplying with gate offsets q\boldsymbol{q}, each shifting its node label by MnodeqM_{\mathrm{node}}\boldsymbol{q}. A gate with Mnodeq=0M_{\mathrm{node}}\boldsymbol{q} = 0 requires no interworker communication, but also cannot distribute strings to other workers. If all gates are local, the node label is conserved, and all strings remain on the worker holding the initial observable, giving fex=0f_{\mathrm{ex}} = 0 but λ=P\lambda= P. Conversely, a uniformly random hash balances the strings, λ≈1\lambda\approx1, but fex=1−1/Pf_{\mathrm{ex}} = 1 - 1/P, which tends to all gates as the number of workers P=2BnodeP = 2^{B_{\mathrm{node}}} grows.

Between these extremes, the hash can be tailored to the circuit and available computational resources, for which we evaluate several families of options, as illustrated in Figure 6(a) for a small lattice. For example, a random hash of only the xx bits makes all ZZZZ rotations local, as their offsets only contain zz bits. Alternatively, a lattice cut divides the lattice into PP contiguous blocks, where row ii of the hash reads the zz bits of all qubits in blocks whose binary label has bit ii set. Then, the XX rotations leave the zz bits unchanged, while ZZZZ rotations within a block flip two zz bits whose contributions cancel. Therefore, only ZZZZ rotations connecting different blocks cc and c′c' require communication, shifting the label by c⊕c′c \oplus c'. More generally, we can also define avoid f%f\%, which selects a random fraction ff of the gates and construct a dense random hash using only coordinates outside their offsets, ensuring that these gates remain local. Varying ff thus interpolates between an unrestricted random hash at f=0f = 0 and hashes that keep an increasing fraction of gates local, at the cost of fewer coordinates available for load balancing.

Node-hash strategies for the kicked Ising circuit

Figure 6. Node-hash strategies for the kicked Ising circuit (127 qubits, θh=π/4\theta_h = \pi/4, δ=4×10−6\delta= 4 \times10^{-6}, 20 Trotter steps). (a) Example rows of MnodeM_{\mathrm{node}} on a 9-qubit heavy-hex lattice (P=8P = 8, except ZZ-parity with P=2P = 2). Strategies: random (dense); xx only (dense on xx bits); lattice cut (the zz bits of contiguous lattice blocks, numbered in binary); avoid ff (dense on coordinates outside the offsets of a random fraction ff of gates); sparse zz (kk randomly selected zz bits per row); ZZ-parity (a single conserved parity row). (b) Fraction fexf_{\mathrm{ex}} of the 271 gates of a Trotter step that can require interworker communication, versus the number of workers PP. (c) Load imbalance λ=Nmax⁡/Nˉ\lambda= N_{\max}/\bar{N} versus PP, obtained by distributing the same 3.6×1083.6 \times10^8 strings from a single unpartitioned run after 20 steps according to each hash. (d) Wall time TT versus the number of workers PP (up to 8.2×1088.2 \times10^8 strings), implemented as one MPI rank per NUMA domain of AMD EPYC 9474F nodes (two domains per node), using a single unpartitioned rank as the baseline. Points in (b) and (c) are medians over three seeds for the random choices, with bands and bars spanning all three; points in (d) are the fastest of the three seeds.

Tailoring the hash too much can lead to poor load balance, as illustrated by two common pitfalls. The first arises from conserved quantities, illustrated by the ZZ-parity hash in Figure 6(a). Every gate offset of the kicked Ising circuit has an even number of zz bits, so that the total ZZ-parity of a string, the parity of its number of ZZ and YY factors, is conserved. A hash row reading all zz bits therefore avoids communication but assigns the same label bit to every propagated string, leaving one worker empty and giving λ=2\lambda= 2 at P=2P = 2. The same holds for any row, or combination of rows, that is orthogonal to every offset; such rows are attractive, as they never communicate, but must be avoided.

A second source of imbalance arises because propagated Pauli strings often have low weight, acting trivially on most qubits. A hash row that reads only a few coordinates therefore evaluates to 0 for most strings, concentrating them in a small number of partitions. This is illustrated by the sparse zz-only hash in Figure 6(a), where each row reads the zz bits of only kk qubits. As kk decreases, fewer gates require communication, but the load imbalance increases, as seen in Figure 6(c) where at P=64P = 64 the k=2k = 2 hash gives λ=19.6\lambda= 19.6, with 58% of the workers empty. The lattice cut, whose rows also read a restricted subset of coordinates, gives λ=1.8\lambda= 1.8. In contrast, the xx-only hash and f=50%f = 50\% remain within 1% of perfect balance, with fex=0.39f_{\mathrm{ex}} = 0.39–0.450.45 compared with 0.99 for a random hash [Fig. 6(b)]. The same effect motivates drawing MlocalM_{\mathrm{local}} densely at random to avoid nearly empty local partitions.

The reduced communication yields shorter runtimes, as shown in Figure 6(d). On 8 MPI ranks, a random hash is 1.6×\times faster than a single rank, while the xx-only hash, lattice cut and f=50%f = 50\% are 1.9–2.9×\times faster, exchanging 1.0–2.9 TB instead of 5.9 TB. On 64 ranks, the random hash reaches 4.2×\times, against 4.8–8.5×\times for these tailored hashes.

Tailoring the node hash is therefore particularly beneficial when the number of workers is small compared to the number of distinct gates in the circuit. In this regime, the hash can keep a large fraction of the gates local while still distinguishing enough strings to maintain load balance, improving performance without affecting accuracy. This is particularly relevant for a single-node job with only a few NUMA domains, such as the two domains in Sec. IIIA, where we use a lattice cut. The hash families considered here illustrate how the gate and lattice structure can be exploited to reduce communication in other circuits, and if optimized to the problem and hardware used, can give large improvements. As the number of workers grows, however, each additional row of MnodeM_{\mathrm{node}} must distinguish strings not already separated by the previous rows while avoiding the offsets of gates kept local, making it increasingly difficult to maintain both low communication and good load balance.

Truncation and measurement

In Sec. II, we showed how using a linear hash avoids global communication by decomposing gate applications into independent tasks involving small groups of partitions. However, both measurements and truncation can reintroduce global communication. Here, we show that common truncation schemes and measurements can be performed locally on each worker, with communication limited to scalar or fixed-size histogram reductions.

Various truncation schemes can be deployed to control the growth of the Pauli expansion, discarding strings expected to contribute little and thus trading accuracy for memory. For example, one can truncate with respect to coefficient weight after every operation, either removing all strings with coefficients under some threshold δ\delta, or truncating down to only the Nmax⁡N_{\max} largest coefficients [3, 12, 13, 17]. Alternatively, one can keep only strings with spatial length below a threshold, add depolarizing noise channels to exponentially suppress long strings [8], or replace the expansion at certain times with an unbiased resampling of existing strings down to Nmax⁡N_{\max} [28, 29]. In all cases, truncation only removes strings, leaving the partition of the retained ones unchanged. Schemes that evaluate criteria independently for each string, such as coefficient, weight, or length thresholds, are therefore trivially parallel with each partition applying them locally.

Keeping the Nmax⁡N_{\max} largest coefficients is useful when the total computational resources available is fixed, but it is not trivially parallel: it requires identifying a global cutoff, and therefore global communication over all the data. We introduce two approximations that progressively reduce this cost and that apply equally to keeping the Nmax⁡N_{\max} shortest strings. In the first method, each worker bins its coefficient magnitudes logarithmically, and the histograms are summed in a single reduction whose size is independent of the number of strings. All strings in bins above the cutoff are retained, while the remaining budget is filled from the cutoff bin. Only the strings retained from this boundary bin then depend on the hash. Alternatively, each of the PP workers can apply the same rule to a local budget NP=Nmax⁡/PN_P = N_{\max}/P, eliminating communication and bounding the memory used by each worker. This retains the largest coefficients on each worker rather than the largest overall, so the result depends on the distribution of strings across workers and therefore on PP. This second approach was employed in Fig. 4, and Fig. 7 compares the two approaches at the same total budget, showing they give equivalent magnetization in less time per trotter step in the transverse field Ising quench. The difference between them remains well below the effect of the truncation itself, estimated from a 4×4 \times larger budget [Fig. 7(b)], indicating that per-worker truncation closely approximates global truncation for this benchmark.

Now we discuss how to apply parallelization to measurements. The expectation value of a propagated observable in the state ρ\rho is

⟨O(t)⟩=Tr⁡(ρO(t))=∑iciTr⁡(ρP(pi)).(16)\langle O(t) \rangle= \operatorname{Tr}\left(\rho O(t)\right) = \sum_i c_i \operatorname{Tr}\left(\rho P(p_i)\right). \tag*{(16)}

Individual string contributions can be evaluated efficiently from their symplectic representation for many initial states of interest. For computational basis states, only Pauli strings containing II and ZZ contribute, with expectation values determined by a bitwise parity. For general product states, expectation values factorize into single-qubit contributions, costing O(L)O(L) per string. For stabilizer states, contributions are 00 or ±1\pm1 and can be evaluated through stabilizer-group membership tests using binary linear algebra.

Figure 7. Retaining the globally largest NN coefficients against retaining the N/PN/P largest on each of PP workers, for the 16×1616 \times16 transverse-field Ising quench of § 3 B: (a) the magnetization for both truncations at each PP, (b) their difference next to the effect of the truncation itself (a 4×4 \times larger budget), and (c) the wall time per Trotter step.

Each partition independently accumulates its contribution to the expectation value, and a single scalar reduction then sums these contributions. Operator overlaps can be evaluated similarly, since only strings present in both operators contribute to the Hilbert–Schmidt inner product. When both operators use the same node hash, identical strings reside on the same worker, such that their intersection is computed locally.

Implementation details

The partitioning of § 2 determines which strings interact and which workers communicate, but leaves open how each task is executed. Since operations on individual Pauli strings are inexpensive, the performance of paulistrings-rs is primarily determined by memory traffic. We reduce this traffic through compact storage, cache-sized working sets, selective processing of strings, gate fusion, and bookkeeping integrated into existing passes. The resulting propagation loop of a single worker is summarized in Algorithm 1.

Algorithm 1. Propagation loop for a single worker. A run consists of consecutive gates that exchange no strings, or a single gate that can exchange strings between workers. The number of active local hash bits, B≤BlocalB \le B_{\mathrm{local}}, is adjusted dynamically to maintain a target partition size, with 2B2^B local partitions per worker.

  1. for each run RR of consecutive gates do Prepare

  2. if RR exchanges strings then

  3. agree on BB with the workers that RR couples

  4. send strings marked for exchange in chunks

  5. else

  6. split or merge partitions towards the target size Apply, in parallel by work stealing

  7. for each group of partitions that RR couples do

  8. load the group once its incoming strings have arrived

  9. apply each gate, skipping unchanged partitions

  10. accumulate the histogram and mark strings for the next exchange Truncate

  11. if the policy keeps the globally largest coefficients then

  12. reduce the histograms, decide the cut for the next Apply Finish

  13. agree on BB across all workers and apply the pending cutoff

Each Pauli string is packed into 2⌈L/64⌉2\lceil L/64\rceil 64-bit words for efficient bitwise operations. Within each partition, the xx bits, the zz bits, and the coefficients are stored in separate arrays, with entries sorted by Pauli string. Threshold truncation therefore requires only a single pass and preserves the ordering of the retained strings. Under the phase convention of § 2, every encoded Pauli string is Hermitian, so Hermitian observables have real coefficients. These remain real under Hermiticity-preserving gates, allowing coefficients to be stored as real rather than complex numbers, halving their memory footprint.

Partitioning also reduces memory traffic for a single worker by shrinking the working set for deduplication from NN to roughly 2dN/PB2^dN/P^B strings. With enough partitions, this working set fits in the processor caches, so hash-map accesses or sorting operations avoid much of the traffic to main memory. The number of local partitions is therefore adjusted dynamically to keep the working sets small without creating excessive partitioning overhead. An additional local hash row is activated when the mean partition size exceeds a target, splitting every partition as described in App. A 2, and deactivated only when the mean falls below one eighth of the target, preventing frequent splitting and merging. Figure 8 shows the wall time as a function of the target partition size on two nodes with different L2 cache sizes. Small partitions incur additional overhead, while large partitions reduce cache locality, resulting in a broad performance optimum that changes little with thread count. By default, we target 2102^{10} strings per partition and maintain at least 272^7 local partitions to ensure parallelism for small operators, independently of the number of threads.

Figure 8. Wall time of the kicked Ising circuit (127 qubits, 20 Trotter steps, 8.3×1068.3 \times10^{6} strings) against the target number of strings per partition. Results are shown for 1 to 16 threads within one NUMA domain of AMD EPYC 9474F (left) and 7742 (right) processors. Wall time TT, normalized by the minimum Tmin⁡T_{\min} over target partition sizes for each processor and thread count. Dashed lines indicate the L2 cache capacity per core, assuming 48 bytes per string. Performance is near-optimal for a broad range of partition sizes, with little dependence on thread count.

We also avoid unnecessary memory accessing by exploiting that Pauli rotations affect only strings anticommuting with their generator QQ [Eq. (6)]. Each partition maintains bitwise OR summaries of its xx and zz bits, allowing partitions that commute entirely with QQ to be skipped without reading their contents. Within affected partitions, one pass identifies the anticommuting strings, while a second updates their coefficients and generates partners QPQP, which belong to the partition b⊕Mqb \oplus Mq.

The generated partners must then be combined with existing strings. XOR with the fixed offset qq reverses the order of two strings exactly when qq sets the first bit in which they differ. The partners of a sorted partition can therefore be arranged in sorted order by block swaps, without a comparison sort. Since the partner QPQP also anticommutes with QQ, it can coincide only with an existing anticommuting string in the destination partition, already identified in the first pass. These contributions are summed directly, new strings below the coefficient threshold are discarded, and the remainder is merged into the sorted destination, copying unchanged strings in contiguous blocks.

For a Clifford rotation, with θ\theta an odd multiple of π/2\pi/2, every anticommuting string is instead replaced by its partner, and no coefficients have to be summed.

Since every pass over the strings costs memory bandwidth, consecutive gates that exchange no strings between workers are applied in a single pass. Each gate UU couples only partitions within a coset of its offset space DUD_U, so a sequence of gates couples only partitions within a coset of the sum of their offset spaces. Each such group is loaded into cache, propagated through the entire sequence with deduplication after every gate, and written back. Adding gates can double the number of coupled partitions, so fusion stops when a group would exceed eight partitions, keeping the working set small enough to benefit from the L2 cache. Longer sequences can instead be fused by delaying deduplication, propagating strings along branching Pauli paths before merging identical strings. This trades fewer memory passes for larger intermediate expansions, moving from breadth-first towards depth-first propagation. For runs of Clifford gates, such as the ZZZZ rotations of the kicked Ising circuit, each string is propagated through the entire run, assigned to its final partition, and sorted only once.

Since fusion eliminates intermediate passes over the strings, truncation schemes requiring global information between gates would generally retain different strings if applied only at the end of a run. Our implementation therefore fuses only under the trivially parallel criteria of App. B, for which the result is unchanged.

For truncation schemes requiring global coordination, we instead reduce memory traffic by integrating bookkeeping into existing passes. When approximating the globally largest coefficients, each task accumulates a histogram of squared coefficient magnitudes in power-of-two bins while its output partitions remain in cache. After the histograms are reduced, the resulting cutoff is applied when the next gate loads each partition, avoiding a separate truncation pass. Communication is prepared similarly. If the next gate exchanges strings, the current pass marks those that must be sent, so the subsequent exchange reads only the marked strings. These are sent in chunks using non-blocking point-to-point messages, allowing each worker to process a group as soon as its incoming data arrives, overlapping communication with computation.

References

  1. [1]Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. van den Berg, S. Rosenblatt, H. Nayfeh, Y. Wu, M. Zaletel, K. Temme, and A. Kandala, Evidence for the utility of quantum computing before fault tolerance, Nature 618, 500 (2023).DOI
  2. [2]J. Tindall, M. Fishman, E. M. Stoudenmire, and D. Sels, Efficient tensor network simulation of IBM’s Eagle kicked Ising experiment, PRX Quantum 5, 010308 (2024), arXiv:2306.14887.DOI
  3. [3]T. Begušić, J. Gray, and G. K.-L. Chan, Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance, Sci. Adv. 10, eadk4321 (2024), arXiv:2308.05077.DOI
  4. [4]H.-J. Liao, K. Wang, Z.-S. Zhou, P. Zhang, and T. Xiang, Simulation of IBM’s kicked Ising experiment with projected entangled pair operator, arXiv preprint arXiv:2308.03082 (2023).arxiv.org/abs/2308.03082
  5. [5]S. Anand, K. Temme, A. Kandala, and M. Zale- tel, Classical benchmarking of zero noise extrapolation beyond the exactly-verifiable regime, arXiv preprint arXiv:2306.17839 (2023).
  6. [6]S. Patra, S. S. Jahromi, S. Singh, and R. Orús, Efficient tensor network simulation of ibm’s largest quantum processors, Physical Review Research 6, 013326 (2024).
  7. [7]D. Aharonov, X. Gao, Z. Landau, Y. Liu, and U. Vazirani, A polynomial-time classical algorithm for noisy random circuit sampling, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (2023) arXiv:2211.03999.DOI
  8. [8]T. Schuster, C. Yin, X. Gao, and N. Y. Yao, A polynomial-time classical algorithm for noisy quantum circuits, Phys. Rev. X 15, 041018 (2025), arXiv:2407.12768.arxiv.org/abs/2407.12768
  9. [9]E. Fontana, M. S. Rudolph, R. Duncan, I. Rungger, and C. Cîrstoiu, Classical simulations of noisy variational quantum circuits, npj Quantum Inf. 11, 84 (2025), arXiv:2306.05400.arxiv.org/abs/2306.05400
  10. [10]A. Angrisani, A. Schmidhuber, M. S. Rudolph, M. Cerezo, Z. Holmes, and H.-Y. Huang, Classically estimating observables of noiseless quantum circuits, Phys. Rev. Lett. 135, 176062 (2025), arXiv:2409.01706.DOI
  11. [11]A. Angrisani, A. A. Mele, M. S. Rudolph, M. Cerezo, and Z. Holmes, Simulating quantum circuits with arbitrary local noise using Pauli propagation, PRX Quantum 7, 020313 (2026), arXiv:2501.13101.DOI
  12. [12]T. Begušić and G. K.-L. Chan, Real-time operator evolution in two and three dimensions via sparse Pauli dynamics, PRX Quantum 6, 020302 (2025), arXiv:2409.03097.DOI
  13. [13]N. Loizeau, J. C. Peacock, and D. Sels, Quantum many-body simulations with PauliStrings.jl, SciPost Phys. Codebases , 54 (2025), arXiv:2410.09654.DOI
  14. [14]J. Dehaene and B. De Moor, Clifford group, stabilizer states, and linear and quadratic operations over gf(2), Phys. Rev. A 68, 042318 (2003).
  15. [15]P. Rall, D. Liang, J. Cook, and W. Kretschmer, Simulation of qubit quantum circuits via Pauli propagation, Phys. Rev. A 99, 062337 (2019), arXiv:1901.09070.DOI
  16. [16]C. Gidney, Stim: a fast stabilizer circuit simulator, Quantum 5, 497 (2021), arXiv:2103.02202.
  17. [17]M. S. Rudolph, T. Jones, Y. Teng, A. Angrisani, and Z. Holmes, Pauli propagation: A computational framework for simulating quantum systems, PRX Quantum 7, 032001 (2026), arXiv:2505.21606.DOI
  18. [18]F. Krötz, PaulLIB: A high-performance library for processing Pauli strings (2026), arXiv:2605.25974 [quant-ph].
  19. [19]L. Broers and L. Mathey, Exclusive-or encoded algebraic structure for efficient quantum dynamics, New J. Phys. 28, 044508 (2026), arXiv:2404.09312.DOI
  20. [20]L. Broers, R.-Y. Sun, and S. Yunoki, Scalable simulation of quantum many-body dynamics with or-represented quantum algebra, Phys. Rev. Appl. 26, 024046 (2026), arXiv:2506.13241.DOI
  21. [21]W. A. Wulf and S. A. McKee, Hitting the memory wall: implications of the obvious, SIGARCH Comput. Archit. News 23, 20 (1995).
  22. [22]https://github.com/lkdvos/paulistrings-rs.
  23. [23]J. Vovrosh, S. Julià-Farré, W. Krinitsin, M. Kaicher, F. Hayes, E. Gottlob, A. Keshtritnavum, K. Bidzhiev, S. B. Jäger, M. Schmitt, J. Tindall, C. Dalyac, T. Mendes-Santos, and A. Dauphin, Simulating dynamics of the two-dimensional transverse-field Ising model: A comparative study of large-scale classical numerics, Phys. Rev. Res. 8, 023311 (2026).DOI
  24. [24]J. L. Carter and M. N. Wegman, Universal classes of hash functions, J. Comput. Syst. Sci. 18, 143 (1979).DOI
  25. [25]A. R. Mazumder, H. Karapetyan, M. Z. Mullath, R. H. Tanin, H. Gharibyan, and H. Tepanyan, Benchmarking zero-setup quantum circuit simulators (2026), arXiv:2607.09882 [quant-ph].arxiv.org/abs/2607.09882
  26. [26]H. W. J. Blöte and Y. Deng, Cluster monte carlo simulation of the transverse ising model, Phys. Rev. E 66, 066110 (2002).pubmed.ncbi.nlm.nih.gov/12513350
  27. [27]A. Miller, monoprop: Scaling pauli and majorana propagation via anticommutation indices, arXiv preprint arXiv:2610.21000 (2026).arxiv.org/abs/2610.21000
  28. [28]S. V. Barron, B. Mitchell, V. Tripathi, F. Grieco, I. Rosen, F. Pietracaprina, D. Materia, A. Seif, D. Wanisch, R. L. Panadés-Barrueta, E. van den Berg, J.-U. Chung, A. Eddins, S. Ferracin, G. García-Pérez, J. Goold, L. C. G. Govia, H. Haas, I. Hincks, J. C. Hoke, Z. Holmes, S. un Lee, Y. Kim, S. Majumder, S. Maniscalco, S. Montangero, D. Puzzouli, T. Prosen, J. Raftery, R. R. Cardoso, M. Rossmannek, M. Rudolph, B. Saxberg, L. Shirizly, K. Siva, J. Skanes-Norman, I. Siloi, K. C. Smith, B. Sokolov, M. Takita, Y. Teng, M. T. Tan, J. Tindall, Z. Zimboraš, M. A. C. Rossi, M. C. Tran, S. N. Filippov, and A. Kandala, Observable estimation in the absence of classical verification (2026), arXiv:2607.25998 [quant-ph].arxiv.org/abs/2607.25998
  29. [29]M. S. Rudolph, R. Puig, S. Thabet, and Z. Holmes, Pushing beyond the memory barrier in propagation algorithms with randomization (2026), arXiv:2610.28845 [quant-ph].arxiv.org/abs/2610.28845

Paper details

vlnc:W_7mt2e3y7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents