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.\

}, url = {https://arxiv.org/abs/2205.12967}, author = {Adam Ehrenberg and Abhinav Deshpande and Christopher L. Baldwin and Dmitry A. Abanin and Alexey V. Gorshkov} } @article {2759, title = {The Lieb-Robinson light cone for power-law interactions}, year = {2021}, month = {3/29/2021}, abstract = {The Lieb-Robinson theorem states that information propagates with a finite velocity in quantum systems on a lattice with nearest-neighbor interactions. What are the speed limits on information propagation in quantum systems with power-law interactions, which decay as 1/rα at distance r? Here, we present a definitive answer to this question for all exponents α\>2d and all spatial dimensions d. Schematically, information takes time at least rmin{1,α\−2d} to propagate a distance~r. As recent state transfer protocols saturate this bound, our work closes a decades-long hunt for optimal Lieb-Robinson bounds on quantum information dynamics with power-law interactions.

}, url = {https://arxiv.org/abs/2103.15828}, author = {Minh C. Tran and Andrew Y. Guo and Christopher L. Baldwin and Adam Ehrenberg and Alexey V. Gorshkov and Andrew Lucas} } @article {2868, title = {Minimum Entanglement Protocols for Function Estimation}, year = {2021}, month = {10/14/2021}, abstract = {We derive a family of optimal protocols, in the sense of saturating the quantum Cram{\'e}r-Rao bound, for measuring a linear combination of d field amplitudes with quantum sensor networks, a key subprotocol of general quantum sensor networks applications. We demonstrate how to select different protocols from this family under various constraints via linear programming. Focusing on entanglement-based constraints, we prove the surprising result that highly entangled states are not necessary to achieve optimality in many cases. Specifically, we prove necessary and sufficient conditions for the existence of optimal protocols using at most k-partite entangled cat-like states.

}, url = {https://arxiv.org/abs/2110.07613}, author = {Adam Ehrenberg and Jacob Bringewatt and Alexey V. Gorshkov} } @article {2577, title = {Hierarchy of linear light cones with long-range interactions}, journal = {Physical Review X}, volume = {10}, year = {2020}, month = {5/29/2020}, abstract = {In quantum many-body systems with local interactions, quantum information and entanglement cannot spread outside of a \"linear light cone,\" which expands at an emergent velocity analogous to the speed of light. Yet most non-relativistic physical systems realized in nature have long-range interactions: two degrees of freedom separated by a distance r interact with potential energy V(r)\∝1/rα. In systems with long-range interactions, we rigorously establish a hierarchy of linear light cones: at the same α, some quantum information processing tasks are constrained by a linear light cone while others are not. In one spatial dimension, commutators of local operators \⟨ψ|[Ox(t),Oy]|ψ\⟩ are negligible in every state |ψ\⟩ when |x\−y|≳vt, where v is finite when α\>3 (Lieb-Robinson light cone); in a typical state |ψ\⟩ drawn from the infinite temperature ensemble, v is finite when α\>52 (Frobenius light cone); in non-interacting systems, v is finite in every state when α\>2 (free light cone). These bounds apply to time-dependent systems and are optimal up to subalgebraic improvements. Our theorems regarding the Lieb-Robinson and free light cones, and their tightness, also generalize to arbitrary dimensions. We discuss the implications of our bounds on the growth of connected correlators and of topological order, the clustering of correlations in gapped systems, and the digital simulation of systems with long-range interactions. In addition, we show that quantum state transfer and many-body quantum chaos are bounded by the Frobenius light cone, and therefore are poorly constrained by all Lieb-Robinson bounds.

}, doi = {https://doi.org/10.1103/PhysRevX.10.031009}, url = {https://arxiv.org/abs/2001.11509}, author = {Minh C. Tran and Chi-Fang Chen and Adam Ehrenberg and Andrew Y. Guo and Abhinav Deshpande and Yifan Hong and Zhe-Xuan Gong and Alexey V. Gorshkov and Andrew Lucas} } @article {2406, title = {Complexity phase diagram for interacting and long-range bosonic Hamiltonians}, year = {2019}, month = {06/10/2019}, abstract = {Recent years have witnessed a growing interest in topics at the intersection of many-body physics and complexity theory. Many-body physics aims to understand and classify emergent behavior of systems with a large number of particles, while complexity theory aims to classify computational problems based on how the time required to solve the problem scales as the problem size becomes large. In this work, we use insights from complexity theory to classify phases in interacting many-body systems. Specifically, we demonstrate a \"complexity phase diagram\" for the Bose-Hubbard model with long-range hopping. This shows how the complexity of simulating time evolution varies according to various parameters appearing in the problem, such as the evolution time, the particle density, and the degree of locality. We find that classification of complexity phases is closely related to upper bounds on the spread of quantum correlations, and protocols to transfer quantum information in a controlled manner. Our work motivates future studies of complexity in many-body systems and its interplay with the associated physical phenomena.\

}, url = {https://arxiv.org/abs/1906.04178}, author = {Nishad Maskara and Abhinav Deshpande and Minh C. Tran and Adam Ehrenberg and Bill Fefferman and Alexey V. Gorshkov} } @article {2458, title = {Locality and Heating in Periodically Driven, Power-law Interacting Systems}, journal = {Phys. Rev. A }, volume = {100}, year = {2019}, month = {2019/11/12}, abstract = {We study the heating time in periodically driven D-dimensional systems with interactions that decay with the distance r as a power-law 1/rα. Using linear response theory, we show that the heating time is exponentially long as a function of the drive frequency for α\>D. For systems that may not obey linear response theory, we use a more general Magnus-like expansion to show the existence of quasi-conserved observables, which imply exponentially long heating time, for α\>2D. We also generalize a number of recent state-of-the-art Lieb-Robinson bounds for power-law systems from two-body interactions to k-body interactions and thereby obtain a longer heating time than previously established in the literature. Additionally, we conjecture that the gap between the results from the linear response theory and the Magnus-like expansion does not have physical implications, but is, rather, due to the lack of tight Lieb-Robinson bounds for power-law interactions. We show that the gap vanishes in the presence of a hypothetical, tight bound.\

}, doi = {https://doi.org/10.1103/PhysRevA.100.052103}, url = {https://arxiv.org/abs/1908.02773}, author = {Minh C. Tran and Adam Ehrenberg and Andrew Y. Guo and Paraj Titum and Dmitry A. Abanin and Alexey V. Gorshkov} }