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)
• 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)
• Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms [48.869199703062606]
  A fundamental problem in quantum many-body physics is that of finding ground states of local Hamiltonians. We introduce two approaches that achieve a constant sample complexity, independent of system size $n$, for learning ground state properties.
  arXiv  Detail & Related papers  (2024-05-28T18:00:32Z)
• 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)
• Proofs of network quantum nonlocality aided by machine learning [68.8204255655161]
  We show that the family of quantum triangle distributions of [DOI40103/PhysRevLett.123.140] did not admit triangle-local models in a larger range than the original proof. We produce a large collection of network Bell inequalities for the triangle scenario with binary outcomes, which are of independent interest.
  arXiv  Detail & Related papers  (2022-03-30T18:00:00Z)
• 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)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• 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.