Simulation Complexity of Many-Body Localized Systems

• URL: http://arxiv.org/abs/2205.12967v1
• Date: Wed, 25 May 2022 18:00:00 GMT
• Title: Simulation Complexity of Many-Body Localized Systems
• Authors: Adam Ehrenberg, Abhinav Deshpande, Christopher L. Baldwin, Dmitry A. Abanin, Alexey V. Gorshkov
• Abstract summary: We demonstrate a transition in the classical complexity of simulating such systems as a function of evolution time. We also show that the quantum circuit complexity for MBL systems is sublinear in evolution time.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Quantum complexity and localization in random quantum circuits [0.0]
  We study complexity in random quantum circuits with and without measurements. For $N$ qubits without measurements, the saturation value scales as $2N-1$, and the saturation time scales as $2N$. We observe that complexity acts as a novel probe of Anderson localization and many-body localization.
  arXiv  Detail & Related papers  (2024-09-05T16:10:54Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Complexity is not Enough for Randomness [0.0]
  We study the dynamical generation of randomness in Brownian systems as a function of the degree of locality of the Hamiltonian. We find that the generation of randomness persists for exponentially long times in the system size, even for systems governed by highly non-local time-dependent Hamiltonians.
  arXiv  Detail & Related papers  (2024-05-27T18:00:00Z)
• On the sampling complexity of open quantum systems [0.0]
  We show how the complexity of the underlying quantum process corresponds to the complexity of the associated family of master equations for the dynamics. Our results pave the way for studying open quantum systems from a complexity-theoretic perspective.
  arXiv  Detail & Related papers  (2022-09-22T09:09:28Z)
• Saturation and recurrence of quantum complexity in random local quantum dynamics [5.803309695504831]
  Quantum complexity is a measure of the minimal number of elementary operations required to prepare a given state or unitary channel. Brown and Susskind conjectured that the complexity of a chaotic quantum system grows linearly in time up to times exponential in the system size, saturating at a maximal value, and remaining maximally complex until undergoing recurrences at doubly-exponential times.
  arXiv  Detail & Related papers  (2022-05-19T17:42:31Z)
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
  Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware. We present an algorithm that compresses the Trotter steps into a single block of quantum gates. This results in a fixed depth time evolution for certain classes of Hamiltonians.
  arXiv  Detail & Related papers  (2021-08-06T19:38:01Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Complexity Growth in Integrable and Chaotic Models [0.0]
  We use the SYK family of models with $N$ Majorana fermions to study the complexity of time evolution. We study how this linear growth is eventually truncated by the appearance and accumulation of conjugate points.
  arXiv  Detail & Related papers  (2021-01-06T19:00:00Z)
• Fast and differentiable simulation of driven quantum systems [58.720142291102135]
  We introduce a semi-analytic method based on the Dyson expansion that allows us to time-evolve driven quantum systems much faster than standard numerical methods. We show results of the optimization of a two-qubit gate using transmon qubits in the circuit QED architecture.
  arXiv  Detail & Related papers  (2020-12-16T21:43:38Z)
• Simulating nonnative cubic interactions on noisy quantum machines [65.38483184536494]
  We show that quantum processors can be programmed to efficiently simulate dynamics that are not native to the hardware. On noisy devices without error correction, we show that simulation results are significantly improved when the quantum program is compiled using modular gates.
  arXiv  Detail & Related papers  (2020-04-15T05:16:24Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.