Complexity of geometrically local stoquastic Hamiltonians

• URL: http://arxiv.org/abs/2407.15499v1
• Date: Mon, 22 Jul 2024 09:27:25 GMT
• Title: Complexity of geometrically local stoquastic Hamiltonians
• Authors: Asad Raza, Jens Eisert, Alex B. Grilo,
• Abstract summary: 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.
• Score: 1.474723404975345
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The QMA-completeness of the local Hamiltonian problem is a landmark result of the field of Hamiltonian complexity that studies the computational complexity of problems in quantum many-body physics. Since its proposal, substantial effort has been invested in better understanding the problem for physically motivated important families of Hamiltonians. In particular, the QMA-completeness of approximating the ground state energy of local Hamiltonians has been extended to the case where the Hamiltonians are geometrically local in one and two spatial dimensions. Among those physically motivated Hamiltonians, stoquastic Hamiltonians play a particularly crucial role, as they constitute the manifestly sign-free Hamiltonians in Monte Carlo approaches. Interestingly, for such Hamiltonians, the problem at hand becomes more ''classical'', being hard for the class MA (the randomized version of NP) and its complexity has tight connections with derandomization. In this work, we prove that both the two- and one-dimensional geometrically local analogues remain MA-hard with high enough qudit dimension. Moreover, we show that related problems are StoqMA-complete.

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)
• Coherence generation with Hamiltonians [44.99833362998488]
  We explore methods to generate quantum coherence through unitary evolutions. This quantity is defined as the maximum derivative of coherence that can be achieved by a Hamiltonian. We identify the quantum states that lead to the largest coherence derivative induced by the Hamiltonian.
  arXiv  Detail & Related papers  (2024-02-27T15:06:40Z)
• Quantum simulation for time-dependent Hamiltonians -- with applications to non-autonomous ordinary and partial differential equations [31.223649540164928]
  We propose an alternative formalism that turns any non-autonomous unitary dynamical system into an autonomous unitary system. This makes the simulation with time-dependent Hamiltonians not much more difficult than that of time-independent Hamiltonians. We show how our new quantum protocol for time-dependent Hamiltonians can be performed in a resource-efficient way and without measurements.
  arXiv  Detail & Related papers  (2023-12-05T14:59:23Z)
• 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)
• 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)
• Simultaneous Stoquasticity [0.0]
  Stoquastic Hamiltonians play a role in the computational complexity of the local Hamiltonian problem. We address the question of whether two or more Hamiltonians may be made simultaneously stoquastic via a unitary transformation.
  arXiv  Detail & Related papers  (2022-02-17T19:08:30Z)
• 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)
• Importance of the spectral gap in estimating ground-state energies [0.0]
  The field of quantum Hamiltonian complexity lies at the intersection of quantum many-body physics and computational complexity theory. The main object of study is the LocalHamiltonian problem, which is concerned with estimating the ground-state energy of a local Hamiltonian.
  arXiv  Detail & Related papers  (2020-07-22T18:00:00Z)
• Unraveling the topology of dissipative quantum systems [58.720142291102135]
  We discuss topology in dissipative quantum systems from the perspective of quantum trajectories. We show for a broad family of translation-invariant collapse models that the set of dark state-inducing Hamiltonians imposes a nontrivial topological structure on the space of Hamiltonians.
  arXiv  Detail & Related papers  (2020-07-12T11:26:02Z)

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.