Parallelization Patterns

Quantum workloads offer several different kinds of parallelism: independent parameter points or trajectories, distributed pieces of a state, and parallel operations within a matrix or tensor kernel. Choose a decomposition that matches the mathematical dependencies. Parallelizing a loop whose iterations depend on each other can change the numerical method rather than accelerate it.

Required background. High-performance computing basics defines scaling and cost; error budgets fixes scientific acceptance criteria.

Independent tasks and unequal workloads

Parameter sweeps, disorder realizations, independent Monte Carlo chains, and independent quantum trajectories can often run as separate tasks. Give every task an immutable identity containing its parameter set, initial condition, and random-stream identifier. Collect results by that identity rather than by completion order.

A parameter sweep is independent only if each point is defined independently. A continuation method that initializes a self-consistent solution from the previous point has a dependency and may follow a particular solution branch. Replacing it with unrelated parallel initializations can change the branch selected. Compare branch behavior explicitly when changing the scheduling.

Static allocation is simple when task costs are uniform. Dynamic scheduling helps when convergence times or jump counts vary, but should not alter the random stream assigned to a task. A worker number is therefore usually a poor scientific identifier for a trajectory.

Domain decomposition and halo exchange

For a local finite-difference operator, divide the grid among workers. Interior points use local data; points near a partition boundary require neighboring values in a halo. For a one-dimensional three-point stencil, exchange one boundary value with each neighboring partition before applying the boundary rows.

If a $d$-dimensional local block has linear size $n$, its work scales like $n^d$ while a fixed-width halo scales like $n^{d-1}$. The communication-to-work ratio therefore grows roughly as $1/n$ as blocks become small. Strong scaling eventually loses efficiency even if each local kernel remains fast.

A minimal communication model is

$$T_{\mathrm{comm}}\approx m\alpha+\beta V,$$

where $m$ is the number of messages, $\alpha$ latency, $V$ the transferred volume, and $\beta$ time per byte. Combining small messages reduces latency costs; overlapping communication with interior work is valid only when the required data dependencies are respected.

Global transforms and Krylov orthogonalization have additional communication patterns. An FFT is not a nearest-neighbor stencil, and a distributed inner product needs a global reduction. These operations can become bottlenecks even when the local Hamiltonian action scales well.

Reductions and statistical aggregation

Floating-point addition depends on summation order. Parallel reduction trees may therefore differ in low-order bits from a serial sum. Use stable accumulation and scientifically meaningful tolerances; require a fixed reduction order only when bitwise reproducibility is necessary and its cost is understood.

For independent batches with counts $N_i$ and means $\bar x_i$, combine means by

$$\bar x=\frac{\sum_i N_i\bar x_i}{\sum_iN_i}.$$

Averaging the batch means equally is incorrect when their sample counts differ. For example, batches of 10 observations with mean zero and 90 observations with mean one combine to $0.9$, not $0.5$.

To combine variance information, retain each batch’s count, mean, and centered sum of squares $M_{2,i}=\sum_{k=1}^{N_i}(x_{ik}-\bar x_i)^2$. The combined sum is

$$M_2=\sum_i\left[M_{2,i}+N_i(\bar x_i-\bar x)^2\right].$$

The second term accounts for differences between batch means. Divide by $N-1$ for the sample variance of $N=\sum_iN_i>1$ observations. Autocorrelation and chain equilibration still require separate treatment; this identity does not make correlated draws independent.

Random streams and reproducible ensembles

Do not initialize every worker with the same random seed. That repeats trajectories and can make the nominal sample count much larger than the effective count. Use a generator’s supported independent-stream or counter-based construction, assigning streams to logical tasks rather than transient worker locations.

For a trajectory with adaptive stepping, changing the step sequence changes how many random numbers are consumed. Reproducibility under rescheduling is different from reproducibility under a changed numerical method. Record the generator, stream mapping, and algorithm settings when exact replay matters.

Shared random numbers can intentionally reduce the variance of a difference between two parameter estimates, but then their covariance must be included. This is a designed coupling of estimators, not an excuse for accidentally duplicated streams.

Testing the parallel calculation

Compare one-worker and multiworker runs for the same deterministic task, then for the same indexed stochastic ensemble. Check that every task appears exactly once, normalization and residual criteria agree, and aggregated counts match the requested experiment. A plausible mean does not reveal missing or duplicated tasks.

Test uneven workloads and partitions that do not divide the grid evenly. For a stencil, compare a vector with nonzero entries precisely at partition boundaries; smooth random test vectors may make boundary communication errors less conspicuous.

Exercises

Two workers return the same 1,000 independent samples because they share a seed. Is the effective number of independent samples 2,000? What happens to the estimated standard error if duplication is ignored?

Solution

There are only 1,000 independent draws. Treating the duplicated list as 2,000 independent samples makes the naive standard error too small by approximately $\sqrt2$, although the sample mean is unchanged. Independence is a property of the generated data, not the number of worker outputs.

References

• Hager, G., and G. Wellein, Introduction to High Performance Computing for Scientists and Engineers, CRC Press, 2010 — decomposition, communication, and scaling.
• Message Passing Interface Forum, MPI Documents, accessed 13 October 2026 — authoritative message-passing and collective-operation semantics.
• Salmon, J. K., M. A. Moraes, R. O. Dror, and D. E. Shaw, “Parallel Random Numbers: As Easy as 1, 2, 3,” Proceedings of SC ’11, article 16 (2011), original article — counter-based random streams for parallel simulations.