PaperlayerView exact revision on arXiv

Source-linked AI summary

Pauli Propagation: A Computational Framework for Simulating Quantum Systems

Manuel S. Rudolph, Tyson Jones, Yanting Teng, Armando Angrisani, Zoë Holmes

arXiv:2505.21606v2quant-phcond-mat.other

TL;DR

Classical simulation of quantum systems requires methods suited to different regimes, and Pauli propagation has emerged as a promising framework whose capabilities and algorithmic structure need a comprehensive account. This paper develops that account from tree-search and truncation strategies through implementation and applications, and provides PauliPropagation.jl for practical simulation and further algorithm development. The framework is competitive for selected tasks, supports rapid approximate expectation-value evaluation and hybrid workflows, and shows potential for reusable surrogate models, while important scaling and error-estimation limitations remain.

  • Problem

    No single classical simulation method is optimal across quantum-system regimes, while Pauli propagation has largely been studied through separate theoretical guarantees or case studies rather than an end-to-end account.

  • Method

    The paper analyzes Pauli propagation from its operator-evolution and truncated-path foundations through search, truncation, error estimation, implementation, applications, and the PauliPropagation.jl package.

  • Results

    Pauli propagation is competitive for certain tasks, can estimate typical random-circuit expectation values with polynomial resources, and can achieve up to an order-of-magnitude improvement using approximately 32 threads for a 10^8-string observable operation.

  • Takeaways & Limitations

    Pauli propagation provides a practical framework for large-scale circuit simulation, quantum–classical hybridization, variational workflows, and reusable surrogate evaluations across parameters.

Abstract

from arXiv · show

Classical methods to simulate quantum systems are not only a key element of the physicist's toolkit for studying many-body models but are also increasingly important for verifying and challenging upcoming quantum computers. Pauli propagation has recently emerged as a promising new family of classical algorithms for simulating digital quantum systems. Here we provide a comprehensive account of Pauli propagation, tracing its algorithmic structure from its bit-level implementation and formulation as a tree-search problem, all the way to its high-level user applications for simulating quantum circuits and dynamics. Utilising these observations, we present PauliPropagation.jl, a Julia software package that can perform rapid Pauli propagation simulation straight out-of-the-box and can be used more generally as a building block for novel simulation algorithms.

I. INTRODUCTION

Pauli propagation is a classical simulation framework that evolves Pauli-basis operators, often by Heisenberg-picture backpropagation, to study dynamics, expectation values, and correlations. This paper gives an end-to-end account of its foundations, algorithms, implementation, applications, and software support.

  • I. INTRODUCTION: Pauli propagation approximates quantum-operator evolution through a truncated Pauli path integral and is competitive for certain simulation tasks.It is especially promising for rough expectation values on arbitrary circuit topologies and for interfacing classical computation with quantum hardware.
  • I. INTRODUCTION: The paper connects Pauli propagation's mathematical foundations to search, truncation, error estimation, and hardware-level implementation.Its scope proceeds from high-level applications through algorithmic nuances to CPU/GPU implementation and future directions.
  • I. INTRODUCTION: PauliPropagation.jl is an open-source, extensible Julia package for out-of-the-box large-scale circuit simulation and for developing new propagation algorithms.The package uses Julia's multiple dispatch to remain adaptable and extensible.
  • I. INTRODUCTION: Pauli propagation typically reverses the statevector workflow by evolving an observable under the adjoint circuit and overlapping it with an initial state.This supports expectation values, operator correlations, and related scalar outputs.
  • I. INTRODUCTION: A propagated object is represented as a sum of Pauli strings, while each operation maps an input string to a branched sum whose size is its branching factor.The framework can also evolve states when their Pauli-basis representation is sparse.

B. Common gates and operations

Common gates and channels differ sharply in how they transform and branch Pauli strings. Clifford operations are non-branching, while Pauli rotations branch conditionally, and noise or controlled operations introduce distinct computational behaviors and limits.

  • Clifford Gates: Clifford gates map each Pauli string to one Pauli string, so Clifford-only circuits can be simulated in polynomial time in the number of gates.CNOT can still alter the number of non-identity Paulis and thereby affect later branching.
  • Pauli Rotations: Pauli rotations are either 1-branching or 2-branching, regardless of how many qubits they act on.Branching occurs when the input Pauli fails to commute with the rotation generator; otherwise the string is unchanged.
  • Pauli Rotations: 2^m is the worst-case number of Pauli strings generated by m Pauli rotations, but commutativity and merging usually reduce the practical cost.The two-qubit example produces three strings rather than the nominal 2^3 = 8.
  • Noise Channels: Pauli noise is non-branching because it damps coefficients without changing Pauli strings, whereas non-unital channels can branch on X, Y, and Z in the Heisenberg picture.Amplitude damping is a non-unital example whose repeated application pushes states toward the computational zero state.
  • Controlled Gates and Measurements: Many-controlled unitaries are typically ill-suited to Pauli propagation because control qubits can create exponentially many Pauli-basis terms.Projectors can nevertheless remain efficient when overlaps with stabilizer states are easy to compute.

C. Pauli propagation surrogates

Pauli propagation surrogates compile a truncated expectation-value model once, trading initial time and memory for faster evaluations across circuit parameters. The paper presents this as a promising but still technically immature route for variational and dynamical simulation.

  • C. Pauli propagation surrogates: A Pauli propagation surrogate trades initial computational time and especially memory for faster expectation-value re-evaluation at different parameter settings.Parameter-independent branching and truncation logic can be compiled into a reusable computational model.
  • C. Pauli propagation surrogates: A 20-qubit, 10-layer demonstration compares surrogate and conventional propagation at approximately 0.005–0.010 average absolute error against statevector simulation.Both simulations use one CPU thread, while the setup is explicitly intended to demonstrate potential rather than establish broad scalability.
  • C. Pauli propagation surrogates: Surrogates retain Pauli terms likely to contribute to the final overlap, avoiding repeated traversal of paths with small or zero contributions.This exploits the fact that many Pauli terms annihilate when overlapped with an initial state or operator.
  • C. Pauli propagation surrogates: Surrogates can support variational optimization and family-wide dynamical studies by varying circuit parameters, Hamiltonians, or initial-state preparation circuits.The paper highlights disorder averaging and meta-learning as potential uses.
  • C. Pauli propagation surrogates: The current PauliPropagation.jl surrogate implementation lacks sophisticated compilation techniques and may not scale to the most interesting cases.The authors describe efficient on-the-fly graph construction and compilation as nontrivial, and characterize the present implementation as far from ideal.

D. Prior work and related methods

Pauli propagation is connected to stabilizer simulation, tensor-network methods, and Pauli-basis dynamics software, while this work positions PauliPropagation.jl as an extensible circuit-simulation framework. The paper surveys these relationships and prior applications while distinguishing their computational settings and representations.

  • Stabilizer simulation: Pauli propagation shares Pauli-basis update principles with stabilizer simulation, but stabilizer tools target Clifford circuits and may not support non-Clifford gates.Extended stabilizer simulation covers Clifford and some non-Clifford circuits; STIM is described as faster for purely Clifford circuits.
  • Related software: PauliStrings.jl evolves observables in the Heisenberg picture by solving the von Neumann equation through nested commutators.Its focus is real-time quantum dynamics, whereas PauliPropagation.jl emphasizes circuit and Floquet-dynamics simulation.
  • PauliPropagation.jl: PauliPropagation.jl is an open-source, extensible Julia package for simulating large-scale quantum circuits and reproducing selected prior simulations.Its multiple-dispatch design supports research use, quantum-algorithm development, and novel propagation methods.
  • Tensor-network comparison: Pauli propagation and tensor networks differ in resource scaling: propagation uses the number of Pauli strings, whereas MPS methods use bond dimension with different memory and runtime costs.The paper notes that tensor networks can strongly compress some Pauli sums, including cases that are difficult for propagation.

III. MID LEVEL

This section presents truncation strategies and tree-search implementations for controlling Pauli-propagation cost. It contrasts coefficient-, weight-, frequency-, sine-, and path-weight truncations with DFS, BFS, and merging-BFS traversal strategies.

  • Truncation strategies: Truncations reduce computational resources by discarding small coefficients or Pauli strings, but the required accuracy depends strongly on the simulation task.The Pauli-propagation tree can otherwise grow exponentially with circuit depth.
  • Basic truncations: Small-coefficient truncation is the default practical strategy, while Pauli weight truncation removes high-weight strings that often have small overlaps with the initial state.PauliPropagation.jl exposes coefficient and weight thresholds, with min abs coeff=1e-10 active by default.
  • Limitations of truncation: Weight truncation can accumulate strongly over time in structured real-time dynamics because high-to-low-weight operator backflow may be interrupted.The cited guarantee for locally scrambling circuits is average-case and does not directly cover these structured circuits.
  • Frequency and sine truncation: Frequency truncation removes paths with many sine or cosine factors, producing average coefficients that decrease as (1/2)^ℓ.The strategy has been used in LOWESA and has provable average-case polynomial runtimes for inversely polynomially small errors in some noisy settings.
  • Frequency and sine truncation: Sine truncation drops paths exceeding a sine-factor threshold and underlies Clifford perturbation theory as an expansion in powers of sines.Path-weight truncation has formal success for noisy-circuit simulability but its practical advantage over other truncations remains unclear.
  • Tree-search strategies: DFS uses polynomial memory but cannot merge paths, whereas merging-BFS can achieve strong polynomial speed-ups by combining identical Pauli strings.For m 2-branching rotations, path counts can reach 2^m, while merging-BFS computes at most the corresponding number of unique strings.

C. Error estimates

Pauli propagation offers several error-estimation strategies, but their guarantees depend strongly on whether errors are evaluated in worst-case or average-case settings. Convergence checks and Monte Carlo estimates provide practical guidance while retaining important scope limitations.

  • Error estimation is difficult because systematic approximations, truncations, and convergence in relevant parameters are not always clear.
  • Worst-case bounds: Worst-case truncation bounds accumulate discarded ℓ1-norm contributions across circuit layers and make no assumptions about the initial state or circuit.
  • Worst-case versus average-case: Average-case analyses can be substantially less pessimistic than worst-case bounds, but their gap may grow exponentially with system size.
  • Monte Carlo estimates: Monte Carlo sampling estimates the mean-square error by sampling O(ϵ^-2) Pauli paths under independently sampled circuit parameters.
  • Monte Carlo estimates: These Monte Carlo estimates apply to parameter ensembles and can be much larger for particular parameter choices, especially outside random sampling.
  • Convergence checks: In a 6 × 6 tilted-field Ising simulation, lowering coefficient thresholds made expectation values coincide for longer times, while precise values between t = 1.0 and t = 1.5 required cutoff 2^-18 or below.That cutoff took 26 minutes on one CPU thread and produced just under 50 million Pauli strings.

IV. UNDER THE HOOD

The implementation of Pauli propagation is shaped by the need to process rapidly growing collections of Pauli strings efficiently. PauliPropagation.jl therefore combines compact integer representations with data structures and compiler-friendly operations tailored to propagation workloads.

  • PauliPropagation.jl abstracts low-level data structures, memory management, control flow, parallelisation, and compilation while targeting high-performance simulation.
  • Pauli-string requirements: A Pauli string uses a four-symbol alphabet, so each single-qubit Pauli can be represented with two bits rather than an eight-bit character.
  • Pauli-string requirements: Compile-time length bounds permit static structures and compiler optimisations, while primitive representations avoid the overhead of repeatedly constructing objects.
  • Performance requirements: The representation supports compact storage, fast comparison and hashing, individually addressable Paulis, and efficient processing in hot loops.
  • Integer representation: Unsigned-integer encoding represents a Pauli string as a base-four numeral, with each bit pair denoting one Pauli operator.

B. Processing a Pauli string

Pauli strings are processed as packed binary integers, allowing bitwise operations to implement construction, modification, products, lookup, and commutation checks efficiently.

  • Binary encoding maps Pauli-string operations to bitwise instructions that operate simultaneously on corresponding bit pairs.
  • Basic operations: Bit shifts, masks, and OR operations construct or modify selected Pauli operators, while extraction uses right shifts followed by masking.
  • Products: The product of two encoded Pauli strings uses bitwise XOR for the encoded string, while the required prefactor is computed separately.
  • Lookup operations: Lookup tables replace repeated evaluations of small Pauli-substring maps, including the Hadamard gate’s Pauli transfer action.
  • Commutation: Commutation is determined by counting the sites where individual Paulis anticommute; the full strings commute when that count is even.

C. Representing a Pauli sum

Representing Pauli sums requires balancing memory efficiency, dynamic growth, rapid merging, modification, and iteration over potentially billions of weighted strings. Arrays and hash tables emerge as appropriate options with different performance trade-offs.

  • Pauli propagation must store rapidly growing ensembles that may reach billions of strings, making per-string memory overhead especially costly.
  • Memory requirements: Storing all 4^n possible Pauli strings requires n4^n bits before coefficients; at n = 16, the strings alone require at least 8GB.
  • Data-structure trade-offs: Arrays provide contiguous storage and fast iteration, while hash tables provide amortised O(1) insertion and lookup when their load factor remains small.
  • Dynamic growth: Dynamic sizing is necessary because the number of propagated strings is difficult to predict and changes as truncation costs are adjusted.
  • Search and merging: Efficient merging-BFS requires fast Pauli search, enabled by unsigned-integer keys supporting O(1) comparison and hashing.
  • Design choice: Arrays and hash tables are both suitable overall, with the better choice depending on the circuit, task, and computational hardware.

Hash Tables

Hash tables represent Pauli sums with fast average-case updates and straightforward single-threaded support, while incurring memory, enumeration, and parallelization trade-offs.

  • Representation and operations: Pauli strings are stored as hashable unsigned-integer keys with associated coefficients, enabling amortised O(1) insertion, removal, and search.Each value remains paired with its original key because hashing is generally non-invertible.
  • Parallel processing: Parallel processing can use concurrent hash tables or separate per-thread tables followed by a serial union.General Julia and Python hash maps commonly remain serial because insertion is not easily parallelizable.
  • Trade-offs: Hash tables require substantial capacity overhead: a desirable load factor near 0.5 can make internal storage up to five times larger than the number of Pauli strings.Enumeration is also suboptimal because implementations iterate redundant empty slots or maintain separate key lists.
  • Trade-offs: Bitwise operations on operands exceeding CPU-register size technically scale linearly with operand width, although practical effects are often negligible.The package therefore treats hash-table lookup as effectively O(1) when amortised over many lookups.
  • Package choice: PauliPropagation.jl uses Julia’s Base.Dict for PauliSum, providing asymptotically favorable support across circuit families with simple single-threaded defaults.The choice balances hash-table flexibility against the alternative data structures suited to different situations.

Arrays

Array-based Pauli sums trade some single-threaded convenience for contiguous storage, in-place mutation, and strong CPU/GPU parallelization; PauliPropagation.jl demonstrates substantial multithreaded speedups.

  • Array representation: Arrays store Pauli strings and coefficients contiguously, enabling rapid enumeration and in-place mutation when gates preserve the number of strings.This is particularly advantageous for predominantly Clifford circuits and Pauli noise channels.
  • Parallel primitives: Arrays support independent kernel execution because each index can be processed without interfering with neighboring indices.PauliPropagation.jl writes these routines for CPU and GPU execution using Julia and AcceleratedKernels.jl.
  • Parallel primitives: Stream compaction truncates arrays by flagging retained terms, computing a parallel cumulative sum, and writing untruncated elements into auxiliary arrays.The flag and index arrays let threads transfer terms independently into correct output positions, making the procedure thread safe.
  • Parallel primitives: Merging sorts Pauli strings so duplicates become adjacent, identifies new domains with flags and cumulative sums, then accumulates coefficients for unique strings.Radix sort can reduce sorting to O(N), while pre-allocation amortises resizing costs over multiple gates.
  • Performance: Up to an order of magnitude improvement is observed with approximately 32 threads for Pauli rotations, including merging and truncations, reaching about one second for 10^8 Pauli strings.Performance eventually shows strongly diminishing returns or degradation as more threads are used.
  • Limitations: GPU support is constrained because Pauli strings longer than 32 qubits require chunks of UInt32 or UInt64 rather than one long integer.The authors describe GPU acceleration as still being at an early stage.

Trees

The paper presents tree and array/hash-based mechanisms for representing and updating Pauli sums, emphasizing branching, merging, parallel execution, and extensible gate definitions.

  • Trees: A tree stores one Pauli and scalar per node, with root-to-leaf paths encoding strings and coefficient products accumulated along each path.Search, insertion, and removal take O(n), while enumerating N leaves takes O(N).
  • Gate implementation: Generic Pauli-transfer-matrix evolution is costly because a k-qubit channel requires a 4^k × 4^k matrix and at least O(16^k) subsequent operation.The framework instead exploits sparse, few-branching canonical channels.
  • Gate implementation: Pauli rotations branch into one or two terms depending on commutation, with the new string and commutation relation computed using O(1) bitwise operations.Array implementations use flags, cumulative sums, capacity checks, and coefficient updates to write new terms efficiently.
  • Extensibility: Custom compile-time-known operations can be supplied through overloadable apply() functions, while fixed runtime gates can use precomputed transfer maps.Parametrized transfer maps are computed once per gate rather than once per Pauli string.
  • Limitations: Current truncation after each gate can re-enumerate the full PauliSum and temporarily store terms that are immediately discarded.Earlier truncation could reduce this overhead but would complicate code and custom truncations.

E. Calculating the overlap

Pauli propagation computes expectation values by overlapping a propagated observable with a state or other object, with the required overlap procedure determined by the simulation target and state representation.

  • Overlap framework: The final overlap combines the propagated Pauli sum with a state or observable to obtain an expectation value.The propagated observable is evolved under the adjoint circuit in the Heisenberg picture.
  • Correlation functions: Correlation functions can be computed by looking up the coefficient of the original Pauli string in the propagated sum, requiring O(1) hash-table lookup.No summation is necessary for this correlation-function calculation.
  • State-specific overlaps: For product stabilizer states, a Pauli term contributes only when every site contains either the state’s matching Pauli or identity.For the all-zero state, only strings containing I and Z contribute, checkable with O(1) bit operations.
  • General overlaps: When a state has a Pauli-basis representation, its expectation values can be computed through a scalar product between its PauliSum and the evolved sum.The implementation accounts for the normalization factor 2^n associated with unnormalised Pauli operators.
  • General overlaps: For states represented by tensor networks or quantum devices, the required Pauli expectations can be supplied by classical-shadow protocols or direct measurements.This allows overlap evaluation even when the state is not efficiently representable in the Pauli basis.

V. OUTLOOK

Pauli propagation is promising in settings where Pauli spectra remain concentrated or expectation values can be estimated efficiently, but high magic, connectivity, and precision requirements can make simulations difficult. The outlook highlights applications in noisy dynamics, local observables, repeated evaluations, transparent Pauli-string analysis, and hybrid quantum-classical workflows.

  • Magic and hardness: Low magic keeps significant Pauli terms few, enabling fast and precise propagation, whereas high magic spreads coefficients across many strings and can make truncation expensive.High-magic regimes can require propagating a large fraction of Pauli strings for precise estimates.
  • Open limitations: The paper leaves open whether physically interesting low-magic, high-entanglement circuits offer a strong advantage over tensor networks.It also questions how guarantees for typical random circuits translate to physically motivated problems.
  • Noise and open quantum systems: Pauli noise strictly reduces magic, while amplitude damping tends to reduce effective magic in unstructured circuits, making open-system simulation a potentially favorable setting.The text notes that this does not by itself establish efficient simulation for every open quantum system.
  • Expectation values in typical random or scrambling circuits: For typical random or scrambling circuits, high magic implies worst-case hardness but is not sufficient for average-case hardness because relevant state overlaps can remain small.The cited results support polynomial-resource approximation of expectation values for typical circuits.
  • Local observables and operator lightcones: Operator lightcones can reduce cost for local or low-weight observables because Pauli propagation skips gates commuting with all current Pauli strings.Highly connected topologies instead increase operator-lightcone growth and can accelerate spreading into exponentially many strings.
  • Pauli-string transparency: Propagation methods expose individual Pauli strings and coefficients directly, whereas tensor networks may require queries or sampling to retrieve comparable information.Tensor networks may still simulate some cases for longer times or at higher precision.
  • Repeated evaluations and hybridization: Pauli propagation supports repeated evaluations through surrogates and can combine with quantum devices using Pauli measurements of an initial or partially evolved state.The surrogate implementation remains imperfect, while the hybrid framework is provably efficient in the same cases as Pauli propagation itself.

B. Avenues for further developments

The paper identifies development challenges for Pauli propagation across low-, middle-, and high-level concerns, while outlining algorithmic and practical directions for improvement.

  • B. Avenues for further developments: Pauli propagation development spans computational performance, algorithm design, and understanding which practitioner applications best suit the method.The authors frame these challenges as ranging from low-level implementation through middle-level strategies to high-level applications.
  • B. Avenues for further developments: Finite memory is a primary low-level constraint, with current GPU approaches often reaching memory limits before CPU-based simulations reach time limits.The package supports multithreaded CPUs and limited GPU acceleration, but GPUs commonly have less memory than HPC CPU nodes.
  • B. Avenues for further developments: Larger simulations may require propagation strategies beyond pure merging-BFS, including deterministic or randomized depth-first components.Future package support is intended to include both GPU-accelerated and non-memory-limited propagation strategies.
  • B. Avenues for further developments: Pauli weight truncation is tailored to random circuits but is significantly less effective for structured circuits, motivating circuit-specific prior knowledge and methods such as Majorana propagation.Majorana propagation is described as substantially better suited to the long Pauli strings arising in Fermionic systems.
  • B. Avenues for further developments: Meet-in-the-middle simulation replaces one depth L simulation with two depth L/2 simulations, halving the computation's exponent at the cost of an additional inner-product calculation.The approach propagates initial and final objects in the Schrödinger and Heisenberg pictures, respectively.
  • B. Avenues for further developments: The paper does not provide a definitive answer about which applications place Pauli propagation above competing methods, instead describing current strengths and weaknesses.The authors present this as an open high-level question for practitioners.

A: Pauli normalisation

PauliPropagation.jl uses an unnormalised Pauli basis, simplifying coefficient storage but making the propagated basis non-orthonormal and requiring care with inner products and conventions.

  • A: Pauli normalisation: PauliPropagation.jl stores coefficients cj for Pauli sums E[P] = ∑j cjPj in the unnormalised Pauli basis.The implementation does not include the normalization factors used in normalized Pauli-basis formulations.
  • A: Pauli normalisation: Using the unnormalised basis means the propagated Pauli strings are not orthonormal when viewed as vectors.This differs from formulations using normalized Pauli strings and can affect inner-product calculations.
  • A: Pauli normalisation: Computing a Hilbert–Schmidt inner product between a state and a Pauli sum requires an additional factor beyond the coefficient inner product.The scalarproduct() function computes the inner product between two Pauli-sum coefficient vectors, whereas state–Pauli-sum evaluation uses ∑j cj Tr[ρPj].
  • A: Pauli normalisation: The implementation uses little-endian binary indexing with one-based Julia indices, while Pauli strings and qubit states use big-endian notation.This creates a tension between the conventions used by programmers and those familiar to the quantum-information community.
  • A: Pauli normalisation: Pauli strings are treated as base-four numerals with digit symbols {I,X,Y,Z} = {0,1,2,3}, using an endianness distinct from binary and decimal numerals.This representation supports instantiating a Pauli string as an unsigned integer.
  • A: Pauli normalisation: Pauli propagation is logic-heavy but becomes memory-bandwidth-bound at scale, requiring an implementation that combines high-level scientific maintainability with speed.The paper motivates a language and codebase that scientists can extend without sacrificing compiler-level performance.
Loading 2505.21606v2…