On the hardness of learning ground state entanglement of geometrically local Hamiltonians

• URL: http://arxiv.org/abs/2411.04353v1
• Date: Thu, 07 Nov 2024 01:16:15 GMT
• Title: On the hardness of learning ground state entanglement of geometrically local Hamiltonians
• Authors: Adam Bouland, Chenyi Zhang, Zixin Zhou,
• Abstract summary: 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.
• Score: 2.6034750171634107
• License:
• Abstract: Characterizing the entanglement structure of ground states of local Hamiltonians is a fundamental problem in quantum information. In this work we study the computational complexity of this problem, given the Hamiltonian as input. Our main result is that to show it is cryptographically hard to determine if the ground state of a geometrically local, polynomially gapped Hamiltonian on qudits ($d=O(1)$) has near-area law vs near-volume law entanglement. This improves prior work of Bouland et al. (arXiv:2311.12017) showing this for non-geometrically local Hamiltonians. In particular we show this problem is roughly factoring-hard in 1D, and LWE-hard in 2D. Our proof works by constructing a novel form of public-key pseudo-entanglement which is highly space-efficient, and combining this with a modification of Gottesman and Irani's quantum Turing machine to Hamiltonian construction. Our work suggests that the problem of learning so-called "gapless" quantum phases of matter might be intractable.

Related papers

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Commuting Local Hamiltonians Beyond 2D [0.09208007322096534]
  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.
  arXiv  Detail & Related papers  (2024-10-14T13:40:54Z)
• 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)
• Public-key pseudoentanglement and the hardness of learning ground state entanglement structure [2.1808110832567125]
  Given a local Hamiltonian, how difficult is it to determine the entanglement structure of its ground state? We show that this problem is computationally intractable even if one is only trying to decide if the ground state is volume-law vs near area-law entangled. Our work opens new directions in Hamiltonian complexity, for example whether it is difficult to learn certain phases of matter.
  arXiv  Detail & Related papers  (2023-11-20T18:54:48Z)
• Local Hamiltonian Problem with succinct ground state is MA-Complete [0.788657961743755]
  Finding the ground energy of a quantum system is a fundamental problem in condensed matter physics and quantum chemistry. Existing classical algorithms for tackling this problem often assume that the ground state has a succinct classical description. We study the complexity of the local Hamiltonian problem with succinct ground state and prove it is MA-Complete.
  arXiv  Detail & Related papers  (2023-09-18T21:08:51Z)
• 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)
• 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)
• 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)
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms [105.54048699217668]
  A central component of variational quantum algorithms (VQA) is the state-preparation circuit, also known as ansatz or variational form. Here, we show that this approach is not always advantageous by introducing ans"atze that incorporate symmetry-breaking unitaries. This work constitutes a first step towards the development of a more general class of symmetry-breaking ans"atze with applications to physics and chemistry problems.
  arXiv  Detail & Related papers  (2020-08-03T18:00:05Z)

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.