Parallel Computing Cuts Quantum Simulation Costs Dramatically

Fredrik Hasselgren and Bálint Koczor, from the University of Oxford, have developed a method for massively parallelising tensor-network simulations, overcoming the exponential computational costs typically associated with entanglement build-up. Adapting randomised quantum algorithms, specifically a technique called TE-PAI, for classical computation enables exact time evolution on average and sharply reduces the computational workload. Their MPS TE-PAI approach offers a key improvement over traditional methods, achieving per-sample gate-count reductions of up to a factor of $10^$3 and increased strength against bond-dimension truncation, potentially unlocking the simulation of more complex strongly correlated systems.

Randomised tensor-network simulations sharply reduce quantum system gate-counts

A per-sample gate-count reduction of up to a factor of 103 has been achieved when simulating quantum systems, representing a substantial leap forward in computational efficiency. This improvement overcomes previous limitations imposed by the exponential growth of entanglement, which previously restricted the simulation of complex quantum dynamics. The new MPS TE-PAI method, a randomised quantum algorithm, enables massive parallelisation by representing ensembles of shallow circuits as tensor networks, yielding orders of magnitude reduction in time-to-solution.

Computation is distributed across multiple threads, circumventing the serial nature of traditional tensor-network simulations. This approach allows for exact time evolution on average, utilising an unbiased estimator and reducing estimator variance. Numerical experiments using one-dimensional spin-ring Hamiltonians also revealed that MPS TE-PAI exhibits greater durability against bond-dimension truncation, a necessary practice when simulating strongly correlated systems. Furthermore, the method can be combined with existing time evolution algorithms, extending their effective simulation time.

Matrix product state time evolution with parallelised adaptive imaginary time propagation

Accurately simulating the time evolution of quantum systems is a vital enabler of scientific progress. Classical state-vector simulation algorithms, however, require either exponential space or time as the system size increases. Sophisticated matrix product state (MPS) tensor-network techniques can represent certain classes of quantum states efficiently, but their scalability is still limited by entanglement growth. Currently, quantum computers limit both the number of qubits and the achievable circuit depths due to decoherence.

Rapid progress in hardware and quantum algorithm design is expected to soon enable large-scale, high-accuracy, long-time evolution of quantum systems beyond the capabilities of state-of-the-art classical approximations. This motivates the challenge of pushing the boundaries of classical simulation methods for time evolution. Tensor-network contractions and related “quantum-inspired” classical algorithms have recently received attention as a means to improve and extend the currently known set of tools for quantum simulation techniques.

In regimes where entanglement becomes large, such as generic chaotic real-time dynamics with volume-law entanglement, low-bond-dimension tensor-network representations can lose their efficiency. This motivates alternative representations that track the evolution of observables rather than states. Pauli propagation, also called sparse Pauli dynamics, simulates dynamics by evolving local operators in the Heisenberg picture as a truncated expansion over Pauli strings, and has recently been developed into a practical and theoretically well established framework for simulating circuits and many-body spin dynamics in challenging regimes.

These techniques build on recent advances in quantum computing algorithms and develop a quantum-inspired classical approach for extending the simulation capabilities of classical computers. Their classical tensor-network MPS protocol builds on the quantum algorithm called Time-Evolution by Probabilistic Angle Interpolation (TE-PAI), which reduces time-evolution circuit depth by replacing a single deep circuit with a statistical ensemble of shallow random circuits. While tensor-network based simulation is well explored, these techniques are inherently serial, propagating the wavefunction step-by-step via short-time propagators.

This quantum-inspired classical algorithm trades total computational volume for reduced depth and increased parallelisation, distributing the computation of randomly generated circuit instances across independent computational threads, thereby reducing the total time-to-solution at the cost of increased aggregate computational volume. The MPS TE-PAI approach enables unbiased estimation of local observables by averaging an ensemble of shallow randomized Trotter variant circuits that are simulated using efficient tensor network contraction. This leads to a reduced estimator variance, as detailed in Section II C. They perform a range of numerical experiments and demonstrate that for disordered one-dimensional spin-ring Hamiltonians, they observe substantial practical reductions in per-sample circuit depth relative to deep Trotterization at fixed accuracy, and quantify the associated depth, width trade-off under realistic parallelisation assumptions.

A hybrid simulation strategy is introduced and validated, switching from deterministic Trotter evolution to MPS TE-PAI once the bond dimension approaches a truncation threshold, thereby extending the reachable simulation time under a fixed contraction cost budget. The article is structured as follows: cost-metrics are outlined in Section II A, the main results of the TE-PAI protocol and its connection to standard Trotterization are reviewed in Section II B, and the expectedly lower variance of their tensor-network approach is derived in Section II C. Section II D outlines and justifies the deep Trotterization protocol used for comparison, while Section II E relates MPS TE-PAI to other tensor-network techniques. Throughout, a one-dimensional n-qubit system evolved under a geometrically local Hamiltonian is considered and simulated using MPS, truncating the bond dimension where necessary to maintain computational tractability.

Because MPS TE-PAI is a fundamentally parallel protocol that simulates time evolution via an ensemble of random circuit variants, the following cost metrics are distinguished: Per-circuit cost Ccirc, total cost Ctot, and time-to-solution Ctot/Nworkers. Under ideal parallelisation with one worker per circuit, the TTS reduces to the contraction time of the deepest single circuit instance. The aim of MPS TE-PAI is to attain a lower TTS since each circuit instance satisfies Ccirc.

Let χ(t) denote the maximum bond dimension of an exact MPS at time t, and let χmax denote the maximum value attained over the full evolution. For a nearest-neighbour two-qubit gate applied to an MPS in mixed-canonical form, the dominant cost of the bond update and SVD re-factorization scales as O(χ3). Consequently, for a circuit instance with ν two-site gates, the per-sample cost is modelled as Ccirc ∝ ν X m=1 χ 3m ≤ν χ3 max, where χm is the bond dimension at the mth gate application. This bound makes explicit the two drivers of classical cost: gate count ν and entanglement-induced bond dimension growth χ(t). Bond-dimension truncation is imposed by discarding all but the χ ≤χcut, the largest singular values at each two-site update, at the cost of a controlled approximation error.

In their main numerical experiments, χcut = 16 is used at which good convergence is observed. Throughout this work, MPS implementations of TE-PAI are compared to the first-order Trotter-Suzuki decomposition for time-independent Hamiltonian H = PL k=1 ck hk: e−iHT = L Y k=1 e−ickhk T N. N + E, where E is an error term bounded in operator norm as ∥E∥≤ε. Therefore, achieving precision ε using the above first-order formula requires a gate count ν that is upper bounded as ν ≤1 2LT 2∥c∥2 T ε−1, where ∥c∥2 T is a commutator norm. Rather than implementing all gates in the above product formula, TE-PAI randomly chooses a subset of gates to be implemented at a fixed rotation angle ∆as per the following protocol.

Given an input Hamiltonian, a Trotter circuit U in Eq. with N Trotter-steps over total time T is initialised. The superoperator representation of this product formula is U = N Y j=1 L Y k=Rk(θkj) . Ns random circuit variants are generated by randomly replacing continuous rotation gates Rk(θkj) in U with a discrete rotation angle drawn from {0, ±∆, π} according to the probabilities defined in Section A 3. All circuit variants are executed and in post-processing, each measurement outcome is multiplied with the relevant prefactor and sign as detailed in Section A 3. As discussed in Section A 3, the above protocol provides an unbiased estimator for the time evolution operator, which is summarised in the following statement. Statement 1 (From Ref. . Replacing continuous-angle rotations in a Trotter circuit with discrete rotation angles drawn randomly as in the TE-PAI protocol detailed around Eq. yields the TE-PAI estimator U as a single random circuit instance.

This estimator is unbiased, meaning E[ U] = U, where the expectation is calculated over a random circuit ensemble. The classical computational cost of generating Ns circuits is O(NLNs), with further details in Section A. In particular, beginning with an asymptotically deep product formula, the protocol yields a finite expected number of gates in the limit as ν∞:= lim N→∞E[ν] = csc(∆)(3 −cos ∆)∥ c∥1 T, which scales linearly with T. The term ∥ c∥1 represents the norm of the Hamiltonian coefficient vector and ∆ is the rotation angle used; see Section A 4 for further details. The purpose of TE-PAI is to estimate the expected ground state energy. Tensor-network simulations of quantum many-body dynamics are limited by entanglement build-up, leading to exponentially growing computational costs. These classical algorithms are also inherently sequential, as the tensor network representation of the quantum state is typically updated incrementally at each time step.

Accelerating quantum system simulations with parallel tensor network algorithms

Researchers are pushing the boundaries of classical simulation, seeking to model quantum systems beyond the reach of today’s quantum computers. Their new method, MPS TE-PAI, offers a significant speed boost by distributing calculations across multiple processors, a technique known as parallelisation. Initiating this approach too early, before bond-dimension truncation becomes necessary, can increase computational demands. Despite this, the method remains valuable for simulating complex quantum systems, demonstrating substantial reductions in computational steps, up to a factor of one thousand, when compared to standard simulation methods. This speed boost is achieved through parallelisation and offers greater durability when simplifying calculations due to limitations in computing resources.

Researchers developed a new classical simulation method, MPS TE-PAI, to model the behaviour of quantum systems more efficiently. This technique achieves exact time evolution on average by utilising an ensemble of randomised circuits represented as tensor networks, enabling massive parallelisation of calculations. Simulations of one-dimensional spin-ring Hamiltonians showed reductions in computational steps by up to a factor of one thousand compared to conventional methods. The approach also proved more resilient to simplifications necessary when computational resources are limited, suggesting it can tackle more complex quantum simulations.