



@article {3071,
	title = {Simulation Complexity of Many-Body Localized Systems},
	year = {2022},
	month = {5/25/2022},
	abstract = {<p>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.\&nbsp;</p>},
	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 {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 = {<p>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 α\&gt;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 α\&gt;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.\&nbsp;</p>},
	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}
}
