Improved Hardness Results for the Guided Local Hamiltonian Problem

• URL: http://arxiv.org/abs/2207.10250v3
• Date: Sun, 4 Feb 2024 04:29:11 GMT
• Title: Improved Hardness Results for the Guided Local Hamiltonian Problem
• Authors: Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, Fran\c{c}ois Le Gall, Tomoyuki Morimae, Jordi Weggemans
• Abstract summary: 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.
• Score: 1.53934570513443
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with $6$-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to $1/2$ with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.

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)
• 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)
• Observing super-quantum correlations across the exceptional point in a single, two-level trapped ion [48.7576911714538]
  In two-level quantum systems - qubits - unitary dynamics theoretically limit these quantum correlations to $2qrt2$ or 1.5 respectively. Here, using a dissipative, trapped $40$Ca$+$ ion governed by a two-level, non-Hermitian Hamiltonian, we observe correlation values up to 1.703(4) for the Leggett-Garg parameter $K_3$. These excesses occur across the exceptional point of the parity-time symmetric Hamiltonian responsible for the qubit's non-unitary, coherent dynamics.
  arXiv  Detail & Related papers  (2023-04-24T19:44:41Z)
• Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture [0.0]
  We study 'Merlinized' versions of the recently defined Guided Local Hamiltonian problem. These problems do not have a guiding state provided as a part of the input, but merely come with the promise that one exists. We show that guidable local Hamiltonian problems for both classes of guiding states are $mathsfQCMA$-complete in the inverse-polynomial precision setting.
  arXiv  Detail & Related papers  (2023-02-22T19:00:00Z)
• 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)
• Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States [0.0]
  We show that the so-called guided local Hamiltonian problem remains BQP-complete when the Hamiltonian is 2-local. We improve upon this result by showing that it remains BQP-complete when i) the Hamiltonian is 2-local, ii) the overlap between the guiding state and target eigenstate is as large as $1.
  arXiv  Detail & Related papers  (2022-07-20T18:00:02Z)
• Estimating gate complexities for the site-by-site preparation of fermionic vacua [0.0]
  We study the ground state overlap as a function of the number of sites for a range of quadratic fermionic Hamiltonians. For one-dimensional systems, we find that two $N/2$-site ground states also share a large overlap with the $N$-site ground state everywhere except a region near the phase boundary.
  arXiv  Detail & Related papers  (2022-07-04T19:45:14Z)
• 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)
• Non-equilibrium stationary states of quantum non-Hermitian lattice models [68.8204255655161]
  We show how generic non-Hermitian tight-binding lattice models can be realized in an unconditional, quantum-mechanically consistent manner. We focus on the quantum steady states of such models for both fermionic and bosonic systems.
  arXiv  Detail & Related papers  (2021-03-02T18:56:44Z)
• 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.