We study the computational complexity of simulating the time-dependent expectation value of a local operator in a one-dimensional quantum system by using temporal matrix product states(MPSs) and argue that it is intimately related to that of encoding temporal transition matrices and their partial traces. We show that we can upper-bound the rank of these reduced transition matrices by one of the Heisenberg evolution of local operators, thus making aconnection between two apparently different quantities, the temporal entanglement and the local operator entanglement(OE). As a result, whenever the local OE grows slower than linearly in time, we show that computing time-dependent expectation values of local operators using temporal MPSs is likely advantageous with respect to computing the same quantities using standard MPS techniques. Published by the American Physical Society 2024
We study the computational complexity of simulating the time-dependent expectation value of a local operator in a one-dimensional quantum system by using temporal matrix product states(MPSs) and argue that it is intimately related to that of encoding temporal transition matrices and their partial traces. We show that we can upper-bound the rank of these reduced transition matrices by one of the Heisenberg evolution of local operators, thus making aconnection between two apparently different quantities, the temporal entanglement and the local operator entanglement(OE). As a result, whenever the local OE grows slower than linearly in time, we show that computing time-dependent expectation values of local operators using temporal MPSs is likely advantageous with respect to computing the same quantities using standard MPS techniques. Published by the American Physical Society 2024
The dynamics of one-dimensional quantum many-body systems is often numerically simulated with matrix-product states (MPSs). The computational complexity of MPS methods is known to be related to the growth of entropies of reduced density matrices for bipartitions of the chain. While for closed systems the entropy relevant for the complexity is uniquely defined by the entanglement entropy, for open systems it depends on the choice of the representation. Here, we systematically compare the growth of different entropies relevant to the complexity of matrix-product representations in open-system simulations. We simulate an XXZ spin-1/2 chain in the presence of spontaneous emission and absorption and dephasing. We compare simulations using a representation of the full density matrix as a matrix-product density operator (MPDO) with a quantum trajectory unraveling, where each trajectory is itself represented by an MPS (QT + MPS). We show that the bipartite entropy in the MPDO description (operator entanglement, OE) generally scales more favorably with time than the entropy in QT + MPS (trajectory entanglement, TE): (i) For spontaneous emission and absorption the OE vanishes while the TE grows and reaches a constant value for large dissipative rates and sufficiently long times; (ii) for dephasing the OE exhibits only logarithmic growth while the TE grows polynomially. Although QT + MPS requires a smaller local state space, the more favorable entropy growth can thus make MPDO simulations fundamentally more efficient than QT + MPS. Furthermore, MPDO simulations allow for easier exploitation of higher-order Trotter decompositions and translational invariance, allowing for larger time steps and system sizes.
Temporal entanglement (TE) of an influence matrix (IM) has been proposed as a measure of complexity of simulating dynamics of local observables in a many-body system. Foligno et al. [Phys. Rev. X 13, 041008 (2023)] recently argued that the TE in chaotic 1d quantum circuits obeys linear (volume-law) scaling with evolution time. To reconcile this apparent high complexity of IM with the rapid thermalization of local observables, here we study the relation between TE, non-Markovianity, and local temporal correlations for chaotic quantum baths. By exactly solving a random-unitary bath model, and bounding distillable entanglement between future and past degrees of freedom, we identify a regime where TE is extensive and reflects genuine non-Markovianity. This memory, however, is entirely contained in highly complex temporal correlations, and its effect on few-point temporal correlators is negligible. An IM coarse-graining procedure, reducing the allowed frequency of measurements of the probe system, results in a transition from volume- to {subvolume- (area or logarithmic)} law TE scaling. We demonstrate the generality of this TE transition in 1d circuits by analyzing the kicked Ising model analytically at dual-unitary points, as well as numerically away from them. This finding indicates that dynamics of local observables are fully captured by a subvolume-law IM. We provide evidence that the compact IM MPS obtained via standard compression algorithms accurately describes local~evolution.
Local-operator entanglement (LOE) quantifies the nonlocal structure of Heisenberg operators and serves as a diagnostic of many-body chaos. We provide rigorous bounds showing when an operator can be well-approximated by a matrix-product operator (MPO), given asymptotic scaling of its LOE α-Rényi entropies. Specifically, we prove that a volume law scaling for α≥1 implies that the operator cannot be approximated efficiently as an MPO while faithfully reproducing all expectation values. On the other hand, if we restrict to correlations over a relevant sub-class of (ensembles of) states, then logarithmic scaling of the α<1 entropies implies MPO simulability. This result covers a range of relevant quantities, including infinite temperature autocorrelation functions, out-of-time-ordered correlators, and average-case expectation values over ensembles of computational basis states. Beyond this regime, we provide numerical evidence together with a random matrix model to argue that this simulability result also typically holds for arbitrary states. Our results put on firm footing the heuristic expectation that a low operator entanglement implies efficient tensor network representability, extending celebrated foundational results from the theory of matrix-product states and providing a formal link between quantum chaos and classical simulability.
The complexity of simulating the out-of-equilibrium evolution of local operators in the Heisenberg picture is governed by the operator entanglement, which grows linearly in time for generic nonintegrable systems, leading to an exponential increase in computational resources. A promising approach to simplify this challenge involves discarding parts of the operator and focusing on a subspace formed by ``light'' Pauli strings---strings with few Pauli matrices---as proposed by Rakovszki et al. [Phys. Rev. B 105, 075131 (2022)]. In this work, we investigate whether this strategy can be applied to quenches starting from homogeneous product states. For ergodic dynamics, these initial states grant access to a wide range of equilibration temperatures. By concentrating on the desired matrix elements and retaining only the portion of the operator that contains Pauli strings parallel to the initial state, we uncover a complex scenario. In some cases, the light Pauli strings suffice to describe the dynamics, enabling efficient simulation with current algorithms. However, in other cases, heavier strings become necessary, pushing computational demands beyond our current capabilities. We analyze this behavior by introducing a measure of complexity, the operator weight entropy, which we compute for different operators across most points on the Bloch sphere.
Out-of-equilibrium dynamics of non-integrable Hamiltonian many-body quantum systems are characterized by highly entangled wave functions. Near-maximal entanglement arises in systems exhibiting thermalization or pre-thermalization, where the system converges to a steady state with a fixed energy density. Classical simulation of the time dependence of such wave functions requires exponential resources. However, typical computations aim to estimate expectation values of local operators and correlation functions to some expected precision. For thermalizing systems at sufficiently high energy densities, such computations can be done without storing the full wave function by instead simulating the evolution of the local operator, which requires significantly fewer resources. Nonetheless, constructing such resource-efficient classical algorithms remains a challenge for intermediate energy densities, where simulating both the wave function and operator evolution is costly. In this paper, we propose a heuristic approach to accelerate the convergence of Matrix Product State (MPS) simulations of expectation values, applicable across a broad range of energy densities. We estimate the desired observables by rescaling the MPS results at low bond dimensions with a factor that depends on the fidelity of the MPS wave function. Using this technique, we simulated the dynamics of the two-dimensional Transverse-Field Ising Model (TFIM) on a 7×8 grid with periodic boundary conditions, using a maximum bond dimension of χ=4096 on a single A100 GPU, as well as the dynamics of the two-dimensional XY model on grids of size up to 9×9. We compare our TFIM results to similar simulations on a digital quantum processor [R. Haghshenas et al., Nature 653, 56 (2026)], demonstrating excellent agreement and confirming the predictive power of our method.
Abstract In one dimension, the area law and its implications for the approximability by matrix product states are the key to efficient numerical simulations involving quantum states. Similarly, in simulations involving quantum operators, the approximability by matrix product operators (in Hilbert–Schmidt norm) is tied to an operator area law , namely the fact that the operator space entanglement entropy (OSEE)—the natural analog of entanglement entropy for operators, investigated by Zanardi (2001 Phys. Rev . A 63 040304) and by Prosen and Pižorn (2007 Phys. Rev. A 76 032316)—is bounded. In the present paper, it is shown that the OSEE can be calculated in two-dimensional conformal field theory, in a number of situations that are relevant to questions of simulability of long-time dynamics in one spatial dimension. It is argued that: (i) thermal density matrices ρ ∝ e − β H and generalized Gibbs ensemble density matrices ρ ∝ e − H G G E with local H GGE generically obey the operator area law; (ii) after a global quench, the OSEE first grows linearly with time, then decreases back to its thermal or GGE saturation value, implying that, while the operator area law is satisfied both in the initial state and in the asymptotic stationary state at large time, it is strongly violated in the transient regime; (iii) the OSEE of the evolution operator U ( t ) = e − i H t increases linearly with t , unless the Hamiltonian is in a localized phase; (iv) local operators in Heisenberg picture, ϕ ( t ) = e i H t ϕ e − i H t , have an OSEE that grows sublinearly in time (perhaps logarithmically), however it is unclear whether this effect can be captured in a traditional CFT framework, as the free fermion case hints at an unexpected breakdown of conformal invariance.