WorksPhysics and Astronomy
Scalable Pauli propagation through -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 -linear hash function, which guarantees that a -qubit channel couples each partition to at most 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 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 -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.

Figure 1. Naive versus -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) -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 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,
where every for a system of qubits. Pauli strings span the -dimensional operator space, and many operators admit sparse representations with . 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 , with the phase convention ensuring Hermiticity. For qubits, these bits form a vector over the binary field, , representing the string
where counts the number of factors, denotes bitwise AND, and the Hamming weight.
In this encoding, multiplication of two Pauli strings reduces to bitwise XOR , up to a phase,
where the phase follows from commuting past , which gives a minus sign wherever both act,
Commutation is determined by the symplectic product
such that , where the symplectic form over 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 transforms a string depending on whether it commutes or anticommutes with :
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 -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 assigns each Pauli string to one of partitions,

Figure 2. -linear partitioning and multiplication. (a) The Pauli string has bit vector . The binary hash matrix assigns it the label , computed mod 2, and hence the partition . Each partition stores the strings and coefficients of the operator . (b)–(c) Multiplication by , with bitvector , maps to and the label to with (b). Every partition is therefore mapped to a single partner, and the partitions are exchanged in pairs (c). Shown here is the case , . Labels are written as , and filled (empty) squares denote 1 (0).
and by linearity . Consequently, multiplication by a fixed Pauli string maps every string in to , 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 maps each string to a combination of and as shown in Eq. (6). The former remains in , while the latter belongs to . 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 qubits maps to a linear combination of strings , where is supported only on those qubits. By linearity of the hash, the output partition label is . Let denote the span of all such offsets, and their image under the hash. Since the offsets involve at most binary coordinates,
Each partition can therefore exchange strings only with partitions labeled by . These labels form a coset of , which is closed under all offsets generated by the gate. Consequently, the partitions split into disjoint groups, each containing partitions. Each group forms an independent task that can be updated and deduplicated without communication with other groups.
The choice of 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 [24], yielding approximately balanced partitions when . However, 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, . 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
where denotes nearest-neighbor pairs, and is the angle of the transverse-field kick, here fixed to . Using the initial product state , we calculate the single-site magnetization after 20 Trotter steps. Coefficients are truncated using an absolute threshold , 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 and . 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 and , respectively.
Figure 3. Strong scaling of the wall time of for the kicked Ising circuit (127 qubits, , 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 and 38% for 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 using two MPI ranks per node (one per NUMA domain) and the avoid 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 to four nodes for . 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 F-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,
where is the ferromagnetic coupling and is the strength of the transverse field. Near the critical field [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 lattice: starting from the product state we quench to and compute the spatially averaged magnetization, , over 20 second-order Trotter steps with . Instead of a coefficient threshold, we use the per-worker truncation scheme of App. § 4, fixing the retained-string budget per compute node and dividing it equally between two MPI ranks, one per NUMA domain. Strings are distributed using the avoid node hash described in App. § 3.1. For weak scaling, we keep , 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 , , and 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 transverse-field Ising quench, at fixed per-node string budgets of , , and . Strings are distributed using the avoid 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 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 14 quench of Ref. [23], starting from and evolving the central-site magnetization at . We evolve over 40 second-order Trotter steps with , with the only truncation being coefficient thresholds ranging from to . 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 Pauli strings (about 11 TiB), distributed over 64 nodes. The corresponding retained operator norm, , is shown in Figure 5(b). At , 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 for the transverse-field Ising quench from to , using 40 second-order Trotter steps with . (a) Magnetization and (b) retained squared operator norm for coefficient thresholds to . (c) Pauli propagation (PP) at 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 -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 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 -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 assigns every Pauli string to the partition . The hash is -linear if
Every such hash can be represented as for a binary matrix . Each row of selects a subset of bits from the binary representation , whose parity determines the corresponding partition label bit, . By linearity, the partition containing the identity string is the kernel , a linear subspace of dimension . Every other partition is a coset of ,
For full-rank , all partitions therefore contain the same number of possible strings. Moreover, multiplication by any Pauli string maps onto as a whole.
Conversely, this property characterizes linear partitioning up to relabeling. For any , multiplication by maps the identity to . Since multiplication maps whole partitions onto partitions, it must map onto itself. Thus for every , proving that is closed under and is therefore a linear subspace. Similarly, multiplication by any maps onto the partition containing , which is precisely the coset . Since every linear subspace is the kernel of some linear map, these cosets define a -linear hash up to relabeling.
For common classes of gates, the offset space 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 , so and regardless of the weight of . When , no interpartition communication is required. For a dense gate or channel acting on qubits, the offsets can span the full -dimensional binary space supported on those qubits, giving .
A Clifford gate maps each Pauli string to a single string up, up to a sign, where 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 , giving
For the standard single- and two-qubit Clifford generators, and , respectively, as listed in Table I. For any with , the output partition label is,
| Gate | Bit update | |
| 1 | ||
| 1 | ||
| 2 | ||
| 2 |
Table I. Bit updates of the standard Clifford generators on a string , which leave all other bits unchanged, together with the bound of Eq. (13) on the number of offset directions.
Therefore, strings from the partition can reach only partitions labeled by , at most of them with . This routing depends only on the hash and the gate and can be precomputed. For full-row-rank , a right inverse determines the base offset for each partition, while the columns of , where is a basis matrix for , span the remaining possible offsets.
Linear hashes are also a classic universal family [24]. For a uniformly random , two distinct strings collide with probability
since each row is independently orthogonal to the nonzero vector with probability . However, this collision guarantee holds only on average over and does not ensure balanced partitions for a fixed hash or fixed circuit. For a fixed and circuit, partition balance depends on how the strings are distributed over the cosets of , as discussed in App. § 3.1.§ 8.
Implementation
Evaluating the hash from scratch requires computing parities, costing operations per string. Once a partition label is known, linearity allows it to be updated incrementally, as , where is the offset generated by a gate. For a gate acting on qubits, the possible offsets can be precomputed, reducing routing to a table lookup and XOR.
For distributed execution, the hash label is split into node and local components, corresponding to row blocks and of . 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 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 rows of a fixed, full-rank matrix with at most rows, with the node-assignment rows placed first. Increasing or decreasing activates or deactivates additional rows for local partitioning, leaving the node assignments unchanged. Since each -bit label is a prefix of the corresponding -bit label, adding a row splits each partition into and , 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 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 values to ensure consistent partition labels.
Choosing the node hash
The choice of the node hash, , involves a trade-off between evenly distributing strings across workers and minimizing costly interworker communication. We quantify the load imbalance by , where is the maximum number of strings held by any worker and is the mean number of strings per worker. For a Trotter step composed of Pauli rotations, we quantify communication by , the fraction of gates satisfying , which can exchange strings between workers. Unlike the load imbalance, 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 .
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 by multiplying with gate offsets , each shifting its node label by . A gate with 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 but . Conversely, a uniformly random hash balances the strings, , but , which tends to all gates as the number of workers 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 bits makes all rotations local, as their offsets only contain bits. Alternatively, a lattice cut divides the lattice into contiguous blocks, where row of the hash reads the bits of all qubits in blocks whose binary label has bit set. Then, the rotations leave the bits unchanged, while rotations within a block flip two bits whose contributions cancel. Therefore, only rotations connecting different blocks and require communication, shifting the label by . More generally, we can also define avoid , which selects a random fraction of the gates and construct a dense random hash using only coordinates outside their offsets, ensuring that these gates remain local. Varying thus interpolates between an unrestricted random hash at and hashes that keep an increasing fraction of gates local, at the cost of fewer coordinates available for load balancing.

Figure 6. Node-hash strategies for the kicked Ising circuit (127 qubits, , , 20 Trotter steps). (a) Example rows of on a 9-qubit heavy-hex lattice (, except -parity with ). Strategies: random (dense); only (dense on bits); lattice cut (the bits of contiguous lattice blocks, numbered in binary); avoid (dense on coordinates outside the offsets of a random fraction of gates); sparse ( randomly selected bits per row); -parity (a single conserved parity row). (b) Fraction of the 271 gates of a Trotter step that can require interworker communication, versus the number of workers . (c) Load imbalance versus , obtained by distributing the same strings from a single unpartitioned run after 20 steps according to each hash. (d) Wall time versus the number of workers (up to 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 -parity hash in Figure 6(a). Every gate offset of the kicked Ising circuit has an even number of bits, so that the total -parity of a string, the parity of its number of and factors, is conserved. A hash row reading all bits therefore avoids communication but assigns the same label bit to every propagated string, leaving one worker empty and giving at . 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 -only hash in Figure 6(a), where each row reads the bits of only qubits. As decreases, fewer gates require communication, but the load imbalance increases, as seen in Figure 6(c) where at the hash gives , with 58% of the workers empty. The lattice cut, whose rows also read a restricted subset of coordinates, gives . In contrast, the -only hash and remain within 1% of perfect balance, with – compared with 0.99 for a random hash [Fig. 6(b)]. The same effect motivates drawing 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 faster than a single rank, while the -only hash, lattice cut and are 1.9–2.9 faster, exchanging 1.0–2.9 TB instead of 5.9 TB. On 64 ranks, the random hash reaches 4.2, against 4.8–8.5 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 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 , or truncating down to only the 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 [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 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 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 workers can apply the same rule to a local budget , 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 . 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 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 is
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 and contribute, with expectation values determined by a bitwise parity. For general product states, expectation values factorize into single-qubit contributions, costing per string. For stabilizer states, contributions are or and can be evaluated through stabilizer-group membership tests using binary linear algebra.
Figure 7. Retaining the globally largest coefficients against retaining the largest on each of workers, for the transverse-field Ising quench of § 3 B: (a) the magnetization for both truncations at each , (b) their difference next to the effect of the truncation itself (a 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, , is adjusted dynamically to maintain a target partition size, with local partitions per worker.
for each run of consecutive gates do Prepare
if exchanges strings then
agree on with the workers that couples
send strings marked for exchange in chunks
else
split or merge partitions towards the target size Apply, in parallel by work stealing
for each group of partitions that couples do
load the group once its incoming strings have arrived
apply each gate, skipping unchanged partitions
accumulate the histogram and mark strings for the next exchange Truncate
if the policy keeps the globally largest coefficients then
reduce the histograms, decide the cut for the next Apply Finish
agree on across all workers and apply the pending cutoff
Each Pauli string is packed into 64-bit words for efficient bitwise operations. Within each partition, the bits, the 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 to roughly 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 strings per partition and maintain at least 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, 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 , normalized by the minimum 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 [Eq. (6)]. Each partition maintains bitwise OR summaries of its and bits, allowing partitions that commute entirely with 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 , which belong to the partition .
The generated partners must then be combined with existing strings. XOR with the fixed offset reverses the order of two strings exactly when 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 also anticommutes with , 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 an odd multiple of , 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 couples only partitions within a coset of its offset space , 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 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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]C. Gidney, Stim: a fast stabilizer circuit simulator, Quantum 5, 497 (2021), arXiv:2103.02202.
- [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]F. Krötz, PaulLIB: A high-performance library for processing Pauli strings (2026), arXiv:2605.25974 [quant-ph].
- [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]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]W. A. Wulf and S. A. McKee, Hitting the memory wall: implications of the obvious, SIGARCH Comput. Archit. News 23, 20 (1995).
- [22]https://github.com/lkdvos/paulistrings-rs.
- [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]J. L. Carter and M. N. Wegman, Universal classes of hash functions, J. Comput. Syst. Sci. 18, 143 (1979).DOI
- [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]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]A. Miller, monoprop: Scaling pauli and majorana propagation via anticommutation indices, arXiv preprint arXiv:2610.21000 (2026).arxiv.org/abs/2610.21000
- [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]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




