Commuting Local Hamiltonians Beyond 2D

• URL: http://arxiv.org/abs/2410.10495v3
• Date: Thu, 17 Oct 2024 15:34:53 GMT
• Title: Commuting Local Hamiltonians Beyond 2D
• Authors: John Bostanci, Yeongwoo Hwang,
• Abstract summary: We present a new technique to analyze the complexity of commuting local Hamiltonians. We show that a larger family of commuting local Hamiltonians is in NP. This is the first time a family of 3D commuting local Hamiltonians has been contained in NP.
• Score: 0.09208007322096534
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Commuting local Hamiltonians provide a testing ground for studying many of the most interesting open questions in quantum information theory, including the quantum PCP conjecture and the existence of area laws. Although they are a simplified model of quantum computation, the status of the commuting local Hamiltonian problem remains largely unknown. A number of works have shown that increasingly expressive families of commuting local Hamiltonians admit completely classical verifiers. Despite intense work, the largest class of commuting local Hamiltonians we can place in NP are those on a square lattice, where each lattice site is a qutrit. Even worse, many of the techniques used to analyze these problems rely heavily on the geometry of the square lattice and the properties of the numbers 2 and 3 as local dimensions. In this work, we present a new technique to analyze the complexity of various families of commuting local Hamiltonians: guided reductions. Intuitively, these are a generalization of typical reduction where the prover provides a guide so that the verifier can construct a simpler Hamiltonian. The core of our reduction is a new rounding technique based on a combination of Jordan's Lemma and the Structure Lemma. Our rounding technique is much more flexible than previous work, and allows us to show that a larger family of commuting local Hamiltonians is in NP, albiet with the restriction that all terms are rank-1. Specifically, we prove the following two results: 1. Commuting local Hamiltonians in 2D that are rank-1 are contained in NP, independent of the qudit dimension. Note that this family of commuting local Hamiltonians has no restriction on the local dimension or the locality. 2. We prove that rank-1, 3D commuting Hamiltonians with qudits on edges are in NP. To our knowledge this is the first time a family of 3D commuting local Hamiltonians has been contained in NP.

Related papers

• On the hardness of learning ground state entanglement of geometrically local Hamiltonians [2.6034750171634107]
  Characterizing the entanglement structure of ground states of local Hamiltonians is a fundamental problem in quantum information. In particular we show this problem is roughly factoring-hard in 1D, and LWE-hard in 2D. Our work suggests that the problem of learning so-called "gapless" phases of matter might be intractable.
  arXiv  Detail & Related papers  (2024-11-07T01:16:15Z)
• Multipartite Embezzlement of Entanglement [44.99833362998488]
  Embezzlement of entanglement refers to the task of extracting entanglement from an entanglement resource via local operations and without communication. We show that finite-dimensional approximations of multipartite embezzling states form multipartite embezzling families. We discuss our results in the context of quantum field theory and quantum many-body physics.
  arXiv  Detail & Related papers  (2024-09-11T22:14:22Z)
• Complexity of geometrically local stoquastic Hamiltonians [1.474723404975345]
  The QMA-completeness of the local Hamiltonian problem is a landmark result of the field of Hamiltonian complexity. We show that both the two- and one-dimensional geometrically local analogues remain MA-hard with high enough qudit dimension.
  arXiv  Detail & Related papers  (2024-07-22T09:27:25Z)
• Classification of dynamical Lie algebras for translation-invariant 2-local spin systems in one dimension [44.41126861546141]
  We provide a classification of Lie algebras generated by translation-invariant 2-local spin chain Hamiltonians. We consider chains with open and periodic boundary conditions and find 17 unique dynamical Lie algebras. In addition to the closed and open spin chains, we consider systems with a fully connected topology, which may be relevant for quantum machine learning approaches.
  arXiv  Detail & Related papers  (2023-09-11T17:59:41Z)
• Commuting Local Hamiltonian Problem on 2D beyond qubits [0.8333246626497363]
  We study the complexity of local Hamiltonians in which the terms pairwise commute. CLHs provide a way to study the role of non-commutativity in the complexity of quantum systems.
  arXiv  Detail & Related papers  (2023-09-10T01:43:48Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• Improved Hardness Results for the Guided Local Hamiltonian Problem [1.53934570513443]
  Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. We show that the BQP-completeness persists even with 2-local Hamiltonians. We also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians.
  arXiv  Detail & Related papers  (2022-07-21T01:13:32Z)
• Efficient Verification of Ground States of Frustration-Free Hamiltonians [28.03059224016627]
  We propose a recipe for verifying the ground states of general frustration-free Hamiltonians based on local measurements. We derive rigorous bounds on the sample complexity by virtue of the quantum detectability lemma and quantum union bound. Our work is of interest not only to many tasks in quantum information processing, but also to the study of many-body physics.
  arXiv  Detail & Related papers  (2022-06-30T13:50:56Z)
• Locality optimization for parent Hamiltonians of Tensor Networks [0.7734726150561088]
  We present an algorithm to systematically simplify parent Hamiltonians. We find that the RVB model is the exact ground state of a parent Hamiltonian whose terms are all products of at most four Heisenberg interactions.
  arXiv  Detail & Related papers  (2022-03-14T19:01:07Z)
• Learning Neural Hamiltonian Dynamics: A Methodological Overview [109.40968389896639]
  Hamiltonian dynamics endows neural networks with accurate long-term prediction, interpretability, and data-efficient learning. We systematically survey recently proposed Hamiltonian neural network models, with a special emphasis on methodologies.
  arXiv  Detail & Related papers  (2022-02-28T22:54:39Z)
• Matrix Product Density Operators: when do they have a local parent Hamiltonian? [59.4615582291211]
  We study whether one can write a Matrix Product Density Operator (MPDO) as the Gibbs state of a quasi-local parent Hamiltonian. We conjecture this is the case for generic MPDO and give supporting evidences.
  arXiv  Detail & Related papers  (2020-10-28T00:30:07Z)

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.