Source-linked AI summary
Simulation Complexity of Many-Body Localized Systems
Adam Ehrenberg, Abhinav Deshpande, Christopher L. Baldwin, Dmitry A. Abanin, Alexey V. Gorshkov
TL;DR
The paper asks how difficult it is to classically simulate MBL evolution as physical time increases. Using quasilocal integrals of motion, it proves quasipolynomial strong simulation for polynomial times, hardness of sampling for certain families after exponential times, and sublinear quantum circuit complexity for sufficiently localized systems.
Problem
The work addresses the lack of rigorous complexity-theoretic understanding of simulating generic MBL systems with quasilocal integrals of motion.
Source: §I · pp. 1–2Method
Results
The paper obtains quasipolynomial strong simulation for 1D MBL systems at polynomial evolution times, proves worst-case sampling hardness after exponentially long times for a specific MBL family, and finds sublinear quantum circuit complexity under a localization condition.
Source: §I · p. 2, §VII · p. 8Takeaways & Limitations
Classical and quantum simulation complexity both vary with evolution time and localization, providing complexity-based distinctions among MBL dynamics.
Source: §I · p. 2, §VII · p. 8The hardness family is fine-tuned, while the quasipolynomial algorithm and sublinear circuit result retain scope and localization restrictions.
Source: §IV · p. 5, §VII · p. 8
Abstract
from arXiv · showhide
We use complexity theory to rigorously investigate the difficulty of classically simulating evolution under many-body localized (MBL) Hamiltonians. Using the defining feature that MBL systems have a complete set of quasilocal integrals of motion (LIOMs), we demonstrate a transition in the classical complexity of simulating such systems as a function of evolution time. On one side, we construct a quasipolynomial-time tensor-network-inspired algorithm for strong simulation of 1D MBL systems (i.e., calculating the expectation value of arbitrary products of local observables) evolved for any time polynomial in the system size. On the other side, we prove that even weak simulation, i.e. sampling, becomes formally hard after an exponentially long evolution time, assuming widely believed conjectures in complexity theory. Finally, using the consequences of our classical simulation results, we also show that the quantum circuit complexity for MBL systems is sublinear in evolution time. This result is a counterpart to a recent proof that the complexity of random quantum circuits grows linearly in time.
I. INTRODUCTION
The paper frames MBL simulation as a complexity problem whose difficulty changes with evolution time. It introduces rigorous classical easiness and hardness results alongside a sublinear quantum-circuit-complexity result.
Motivation
- MBL dynamics can spread entanglement through exponentially decaying interactions among quasilocal conserved operators, unlike single-particle localization.These interactions can destroy separability over exponentially long timescales.Source: §I · p. 1
Simulation tasks
- The paper distinguishes weak simulation, sampling outcomes, from strong simulation, calculating all marginal and conditional probabilities.Strong simulation implies sampling, but sampling does not generally reveal the underlying probabilities.Source: §I · p. 1
Classical simulation
- A tensor-network-inspired algorithm strongly simulates any 1D MBL system in quasipolynomial time for evolution times polynomial in system size.The runtime has the form T = exp[O(log^c N)] for some c > 1.Source: §I · p. 2
- After evolution time t = Ω(exp[N^δ]) for arbitrarily small δ > 0, sampling becomes worst-case hard for a specific family of MBL Hamiltonians.The hardness argument is inspired by IQP sampling and does not apply to every MBL Hamiltonian.Source: §I · p. 2
Quantum complexity
- For sufficiently localized MBL Hamiltonians, quantum circuit complexity grows sublinearly with evolution time, contrasting with the linear growth established for random quantum circuits.This suggests quantum simulation complexity can help classify ergodicity of quantum dynamics.Source: §I · p. 2
Novelty
- Prior MBL simulation methods showed good numerical performance but lacked general accuracy proofs for quasilocal integrals of motion.The paper presents its work as the first systematic complexity-theoretic analysis of generic MBL simulation.Source: §I · p. 2
II. SETUP
The setup defines MBL through a quasilocal unitary that maps physical spins to localized conserved bits and specifies the associated sampling problem. It also states oracle assumptions for accessing the canonical description efficiently.
Definitions
- MBL is defined by a quasilocal unitary that diagonalizes the Hamiltonian in terms of commuting localized bits.The localized bits are conserved quantities, while physical bits represent experimentally accessible observables.Source: §II · p. 2
- A quasilocal unitary decomposes into layers of finite-support unitaries whose constituents become closer to the identity as their support grows.This permits distant sites to be entangled while the generated entanglement decays rapidly with distance.Source: §II · pp. 2–3
Problem formulation
- The physical experiment prepares a product state, evolves it under H, and measures in a product basis to produce the distribution D.The setup allows product-state and product-basis choices without privileging a particular basis.Source: §II · p. 3
- Weak simulation samples from a distribution close to D in total variation distance, whereas strong simulation computes its marginals and conditional probabilities.Approximate sampling is used because physical quantum experiments cannot generally produce perfect samples.Source: §II · p. 3
Assumptions
- The formal problem assumes efficient access to constituents of the quasilocal unitary and to the canonical couplings.These quantities are treated as oracle-accessible because listing exponentially many of them is computationally expensive.Source: §II · p. 3
III. TRUNCATING THE CANONICAL HAMILTONIAN
The truncation method replaces the exact canonical Hamiltonian with a finite-range approximation while controlling the resulting distribution error. Logarithmic truncation scales suffice for polynomially long evolution times.
Hamiltonian approximation
- The approximate Hamiltonian truncates both long-range coupling constants and large-support constituents of the diagonalizing quasilocal unitary.Couplings beyond radius r_J are set to zero, while sufficiently large constituents of U are replaced by the identity.Source: §III · p. 3
Error control
- Ensuring ||ΔH|| ≤ ε/t guarantees that the evolved states, and therefore their measurement distributions, remain ε-close up to time t.The argument bounds total variation distance through the state 2-norm and the Hamiltonian approximation error.Source: §III · p. 3
Error analysis
- The norm bounds combine site-counting factors with exponential decay from the Hamiltonian couplings and quasilocal unitary.The decay estimates rely on the localization-length condition ξ < 1/log 2.Source: §III · p. 4
Error control
- For some polynomially long time t = O(N b), it suffices to choose quantities ensuring ∥∆H∥≤ε/t, with CU, CJ, and k constant independent of N.The factors of N arise from summing over sites, while exponential decay factors arise from decay properties of H and U.Source: §III · p. 4
Result
- Truncating the couplings and quasilocal unitary at logarithmic scale produces a distribution close in total variation distance to the exact one.This is the central approximation guarantee used by the simulation algorithm.Source: §III · p. 4
IV. QUASIPOLYNOMIAL-TIME SAMPLING
The paper constructs a tensor-network algorithm for strong simulation by evaluating local-observable expectations through a qubit-wise tensor contraction. Quasilocality bounds tensor sizes to polylogarithmic legs, yielding quasipolynomial runtime for polynomial evolution times.
Strong simulation
- The algorithm computes all probabilities and marginal probabilities, equivalently expectation values of arbitrary products of local observables, thereby providing strong simulation.Strong simulation also implies sampling from the outcome distribution.Source: §IV · p. 4
Tensor-network construction
- The evolution circuit is organized in the truncated LIOM basis, with commuting Hamiltonian terms grouped into unitaries by their leftmost supported site.The circuit applies the truncated quasilocal unitary, evolves under grouped commuting terms, applies the observable, and reverses the process.Source: §IV · p. 4
- Qubit-wise contraction avoids the extensive tensors produced by time-wise contraction, while the number of contraction operations remains polynomial in N.The scheme contracts tensors intersecting one qubit at a time rather than following their temporal order.Source: §IV · pp. 4–5
Runtime bound
- O([log N]^3) legs is the worst-case tensor-size bound, because quasilocal unitary and Hamiltonian constituents have bounded ranges after truncation.The bound follows from the worst-case extensions of constituents in the truncated quasilocal unitary and interaction terms.Source: §IV · p. 5
- For evolution time t = O(polyN), the contraction algorithm solves the simulation problem in quasipolynomial time rather than polynomial time.The quasipolynomial conclusion follows from polynomially many contractions and tensors with O(polylog N) legs; the result also extends to quasipolynomial evolution time and holds in the worst case.Source: §IV · p. 5
V. HARDNESS AFTER EXPONENTIAL TIME
The paper proves that sampling from certain MBL systems becomes classically hard after exponentially long evolution, using a 1D construction that embeds hard 2D dynamics. This contrasts with quasipolynomial strong simulation at polynomial times and reflects entanglement spreading that destroys approximate separability.
Hardness result
- t ≥ Ω(e^(N^δ/ξ)) makes Problem 1 classically hard for any δ > 0, under plausible complexity-theoretic conjectures.The result concerns weak simulation, or sampling, from a family of MBL Hamiltonians.Source: §V · p. 6
Hardness construction
- A 1D MBL Hamiltonian encodes nearest-neighbor 2D commuting dynamics by selectively coupling sites separated by N^δ.For δ = 1/2, the construction generates an effective square grid of size √N; the general construction uses an N^δ × N^(1−δ) grid.Source: §V · p. 6
- Random local fields make evolution under the constructed Hamiltonian implement an IQP-based measurement-based quantum-computing architecture.The resulting sampling problem is hard assuming an infinite Polynomial Hierarchy and average-case hardness of approximating Ising-model partition functions.Source: §V · p. 6
Scope and interpretation
- The hard family is somewhat fine-tuned, so the theorem establishes worst-case hardness rather than average-case hardness for generic MBL Hamiltonians.The paper contrasts this with its polynomial-time quasipolynomial strong-simulation result, which holds in the worst case.Source: §V · p. 6
- Hardness emerges when entanglement spreads across a polynomially scaling distance, making the evolved state no longer approximately separable.This contrasts with single-particle-localized bosonic systems, whose sampling remains efficiently simulable for all evolution times.Source: §V · p. 6
VI. QUANTUM COMPLEXITY OF SIMULATING MBL SYSTEMS
The paper bounds the quantum circuit complexity of MBL time evolution by truncating quasilocal structure and decomposing the resulting operations into local gates. For sufficiently localized systems, the resulting complexity grows sublinearly with evolution time, unlike the conjectured linear growth for chaotic Hamiltonians.
Sublinear circuit complexity
- For ξ < 1/(4 log 2), the approximate circuit complexity C_ε of an MBL evolution grows sublinearly in time for constant ε.This is the main theorem for sufficiently localized MBL Hamiltonians.Source: §VI · pp. 7–8
Approximation strategy
- The approximation uses a truncated Hamiltonian and a truncated quasilocal unitary that approximately diagonalizes the MBL Hamiltonian.The truncation is chosen so the evolution error is bounded by ε/t, while the quasilocal unitary converts between the physical and LIOM-related bases.Source: §VI · p. 7
- The circuit cost has two components: implementing the quasilocal diagonalizing unitary and evolving under the truncated Hamiltonian in the physical basis.This corresponds to the last three circuit sections after the column of single-site observables.Source: §VI · p. 7
Gate decomposition
- The quasilocal unitary acts on at most r_U = Θ(ξ^b log N) qubits per gate, enabling a controlled gate-cost bound after truncation.The truncation radii r_J and r_U are selected logarithmically in N and t to keep total error within the target budget.Source: §VI · pp. 7–8
- A local unitary acting on k qubits can be decomposed into O(k^2 2^(2k)) single-qubit and CNOT gates, with approximate Clifford+T synthesis adding only polylogarithmic error overhead.The construction applies this decomposition layer by layer to the quasilocal unitary and truncated evolution.Source: §VI · p. 7
Interpretation
- Sublinear MBL circuit complexity contrasts with the conjectured linear-in-time complexity of chaotic Hamiltonians and is consistent with logarithmic entanglement spreading.The result provides a complexity-theoretic explanation for why sufficiently localized MBL systems do not generate comparably chaotic dynamics.Source: §VI · p. 8
VII. CONCLUSION AND OUTLOOK
The paper establishes classical easiness results for MBL simulation at several time scales, hardness after exponentially long evolution, and sublinear quantum gate complexity, while identifying important scope restrictions and open questions.
VII. CONCLUSION AND OUTLOOK
- The work develops a quasipolynomial-time strong-simulation algorithm for sufficiently localized MBL systems evolved for quasipolynomially long times.The authors note that this is not yet a polynomial-time algorithm and leave possible improvements open.Source: §VII · p. 8
- The main classical-simulation proof applies only to highly localized LIOMs with ξ < 1/log 2 and uses worst-case bounds without explicitly modeling disorder.The paper also calls for studying access to the Hamiltonian only in the p-bit basis.Source: §VII · p. 8
- A family of random MBL systems becomes hard to simulate after evolution times exponential in system size, but its fine-tuned structure may not represent disorder-induced MBL.Whether average-case hardness extends to more natural disorder-induced Hamiltonians remains open.Source: §VII · p. 8
- For localization length ξ < 1/(4 log 2), the quantum simulation gate complexity is sublinear in evolution time.The authors leave open whether this localization-length condition reflects proof technique or physical behavior.Source: §VII · p. 8
- In higher dimensions, a natural MBL generalization could make sampling hard at constant evolution time, although other extensions may not.The higher-dimensional status of MBL itself is debated, and the hardness conclusion depends on the chosen extension.Source: §VII · p. 8
SUPPLEMENTAL MATERIAL FOR: SIMULATION COMPLEXITY OF MANY-BODY LOCALIZED SYSTEMS
The supplemental material supplies additional algorithmic details for logarithmic-time MBL simulation and proofs deferred from the main text.
SUPPLEMENTAL MATERIAL FOR: SIMULATION COMPLEXITY OF MANY-BODY LOCALIZED SYSTEMS
- The supplement expands the logarithmic-time simulation algorithm and proves main-text equations deferred for clarity.The algorithmic details concern evolution times at most logarithmic in system size.Source: SUPPLEMENTAL MATERIAL FOR: SIMULATION… · p. 10
S.I. LOGARITHMIC TIME SIMULATION
For finite-range Hamiltonians, the supplement derives efficient strong and sampling simulation for logarithmic evolution times using an approximate matrix-product-operator propagator.
S.I. LOGARITHMIC TIME SIMULATION
- An approximate propagator can be constructed with resources polynomial in N and 1/ε and exponential in |t|.This representation applies when H is finite-range in the physical basis.Source: S.I. LOGARITHMIC TIME SIMULATION · p. 10
- The matrix-product-operator representation enables strong simulation of product-state evolution by efficiently evaluating products with local-observable operators.Products of local observables have a trivial matrix-product-operator form.Source: S.I. LOGARITHMIC TIME SIMULATION · p. 10
- Problem 1 is easy for finite-range H when t = O(log N), and the resulting approximate evolution also supports sampling.Strong simulation implies sampling, while the supplement separately describes sampling from the approximate distribution.Source: S.I. LOGARITHMIC TIME SIMULATION · p. 10
- The finite-range assumption is reasonable for candidate systems such as the disordered short-range Ising model, but it also includes thermalizing systems.Thus the result establishes an easy-simulation regime without distinguishing MBL from thermalization through MBL-specific features.Source: S.I. LOGARITHMIC TIME SIMULATION · p. 10
S.II. MATHEMATICAL DETAILS
The mathematical details bound errors from truncating quasilocal unitaries and Hamiltonian terms, using localization-length conditions, combinatorial estimates, and norm inequalities.
S.II. MATHEMATICAL DETAILS
- The truncation analysis assumes ξ < 1/log 2 and uses a logarithmic truncation range r_U = 2aξ log N.The resulting bounds control differences between quasilocal and truncated operators for sufficiently large N.Source: S.II. MATHEMATICAL DETAILS · pp. 10, 12
- The final estimates combine operator-norm bounds, telescoping sums, and submultiplicativity to control products of truncated local unitaries.The multi-index α labels each unitary by its leftmost site and support size, allowing sums over subsets to be reorganized.Source: S.II. MATHEMATICAL DETAILS · pp. 11, 17
- The proof rewrites infinite products as exponentials of infinite sums and bounds their contributions by counting supported unitaries and choosing logarithmic truncation ranges.The analysis combines geometric-series estimates, Stirling’s approximation, and maximization of a single-peaked exponent.Source: S.II. MATHEMATICAL DETAILS · pp. 11–13
- Bounds on the relevant sums rely on geometric convergence and incomplete-Gamma estimates, with exponential decay in p when ξ < 1/log 2.The proof treats separate cases according to the relation between n_0 and the maximizing point n*.Source: S.II. MATHEMATICAL DETAILS · pp. 12, 14, 15
- The Hamiltonian-truncation error is bounded using the triangle inequality, the range cutoff for truncated coefficients, and the number of sites coupled by each p-body term.The parameter ℓ records the maximum distance between sites in a coupled term.Source: S.II. MATHEMATICAL DETAILS · pp. 15–17