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
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.
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.
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.
The simulation of quantum systems is a task for which quantum computers are believed to give an exponential speed up as compared with classical ones. While ground states of one-dimensional systems can be efficiently approximated using matrix product states (MPS), their time evolution can encode quantum computations, so that simulating the latter should be hard classically. However, one might believe that for systems with high enough symmetry, and thus insufficient parameters to encode a quantum computation, efficient classical simulation is possible. We discuss supporting evidence to the contrary: we provide a rigorous proof of the observation that a time-independent local Hamiltonian can yield a linear increase of the entropy when acting on a product state in a translational invariant framework. This criterion has to be met by any classical simulation method, which in particular implies that every global approximation of the evolution requires exponential resources for any MPS-based method.
The rapid growth of entanglement under unitary time evolution is the primary bottleneck for modern tensor-network techniques--such as Matrix Product States (MPS)--when computing time-dependent expectation values. This {entanglement barrier} restricts classical simulations and, conversely, underpins the quantum advantage anticipated from future devices. Here we show that, for one-dimensional Hamiltonian dynamics, the spatio-temporal tensor network encoding the evolved wave function amplitudes can be contracted efficiently along the left-right (spatial) direction. Exploiting this structure, we develop a hybrid Tensor-Network/Monte-Carlo (TN-MC) algorithm that samples the wave function and evaluates expectation values of generic local operators with computational cost that scales only polynomially in time. The accurate contraction of the wave function amplitudes is a consequence of the favorable scaling with time of the generalised temporal entropies. We find that their real part either saturates or, at most, grows logarithmically with time, revealing new instances of continuous dynamical quantum phase transitions (DQPTs) which we characterize. Our results therefore show that, when computing expectation values of local operators, the entanglement barrier in one-dimensional Hamiltonian evolution can be bypassed with a TN-MC blend.