Hamiltonian complexity in the thermodynamic limit

DOI10.1145/3519935.3520067arXiv2107.06201OpenAlexW3178614848MaRDI QIDQ6083530FDOQ6083530

Sandy Irani, Dorit Aharonov

Publication date: 8 December 2023

Published in: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: Despite progress in quantum Hamiltonian complexity, little is known about the computational complexity of quantum physics at the thermodynamic limit. Even defining the problem is not straight forward. We study the complexity of estimating the ground energy of a fixed, translationally invariant Hamiltonian in the thermodynamic limit, to within a given precision; the number of bits $n$ for the precision is the sole input to the problem. The complexity of this problem captures how difficult it is for the physicist to measure or compute another digit in the approximation of a physical quantity in the thermodynamic limit. We show that this problem is contained in $mbox{FEXP}^{mboxQMA-EXP}$ and is hard for $mbox{FEXP}^{mboxNEXP}$. This means that the problem is doubly exponentially hard in the size of the input. As an ingredient in our construction, we study the problem of computing the ground energy of translationally invariant finite 1D chains. A single Hamiltonian term, which is a fixed parameter of the problem, is applied to every pair of particles in a finite chain. The length of the chain is the sole input to the problem and the task is to compute an approximation of the ground energy. No thresholds are provided as in the standard formulation of the local Hamiltonian problem. We show that this problem is contained in $mbox{FP}^{mboxQMA-EXP}$ and is hard for $mbox{FP}^{mboxNEXP}$. Our techniques employ a circular clock in which the ground energy is calibrated by the length of the cycle. This requires more precise expressions for the ground states of the resulting matrices than was required for previous QMA-completeness constructions and even exact analytical bounds for the infinite case which we derive using techniques from spectral graph theory. To our knowledge, this is the first use of the circuit-to-Hamiltonian construction which shows hardness for a function class.

Full work available at URL: https://arxiv.org/abs/2107.06201

Recommendations

• Thermodynamics of Quantum Information Systems — Hamiltonian Description
• Tsallis thermostatistics for finite systems: a Hamiltonian approach
• Thermalization under randomized local Hamiltonians
• Hamiltonian thermodynamics
• Computability of entropy and information in classical Hamiltonian systems
• Semiclassical and thermal phase space entropies measuring complexity
• Thermodynamic vs statistical entropy production in thermostatted Hamiltonian dynamics
• scientific article; zbMATH DE number 1973190
• Quantum Hamiltonian Complexity
• Complexity of stoquastic frustration-free Hamiltonians

zbMATH Keywords

thermodynamic limitHamiltonian complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited In (1)

• Thermodynamics of Quantum Information Systems — Hamiltonian Description

This page was built for publication: Hamiltonian complexity in the thermodynamic limit

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083530)