Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States

• URL: http://arxiv.org/abs/2207.10097v3
• Date: Wed, 7 Feb 2024 11:51:33 GMT
• Title: Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States
• Authors: Chris Cade, Marten Folkertsma, Jordi Weggemans
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently it was shown that the so-called guided local Hamiltonian problem -- estimating the smallest eigenvalue of a $k$-local Hamiltonian when provided with a description of a quantum state ('guiding state') that is guaranteed to have substantial overlap with the true groundstate -- is BQP-complete for $k \geq 6$ when the required precision is inverse polynomial in the system size $n$, and remains hard even when the overlap of the guiding state with the groundstate is close to a constant $\left(\frac12 - \Omega\left(\frac{1}{\mathop{poly}(n)}\right)\right)$. We improve upon this result in three ways: 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 - \Omega\left(\frac{1}{\mathop{poly}(n)}\right)$, and iii) when one is interested in estimating energies of excited states, rather than just the groundstate. Interestingly, iii) is only made possible by first showing that ii) holds.

Related papers

• Hamiltonians for Quantum Systems with Contact Interactions [49.1574468325115]
  We show that in the limit one obtains the one-body Hamiltonian for the light particle subject to $N$ (non-local) point interactions placed at fixed positions. We will verify that such non-local point interactions do not exhibit the ultraviolet pathologies that are present in the case of standard local point interactions.
  arXiv  Detail & Related papers  (2024-07-09T14:04:11Z)
• Geometry of degenerate quantum states, configurations of $m$-planes and invariants on complex Grassmannians [55.2480439325792]
  We show how to reduce the geometry of degenerate states to the non-abelian connection $A$. We find independent invariants associated with each triple of subspaces. Some of them generalize the Berry-Pancharatnam phase, and some do not have analogues for 1-dimensional subspaces.
  arXiv  Detail & Related papers  (2024-04-04T06:39:28Z)
• Parent Hamiltonian Reconstruction via Inverse Quantum Annealing [0.0]
  Finding a local Hamiltonian $hatmathcalH$ having a given many-body wavefunction $|psirangle$ as its ground state, i.e. a parent Hamiltonian, is a challenge of fundamental importance in quantum technologies. We introduce a numerical method that efficiently performs this task through an artificial inverse dynamics. We illustrate the method on two paradigmatic models: the Kitaev fermionic chain and a quantum Ising chain in longitudinal and transverse fields.
  arXiv  Detail & Related papers  (2023-03-20T15:32: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)
• 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)
• Some Remarks on the Regularized Hamiltonian for Three Bosons with Contact Interactions [77.34726150561087]
  We discuss some properties of a model Hamiltonian for a system of three bosons interacting via zero-range forces in three dimensions. In particular, starting from a suitable quadratic form $Q$, the self-adjoint and bounded from below Hamiltonian $mathcal H$ can be constructed. We show that the threshold value $gamma_c$ is optimal, in the sense that the quadratic form $Q$ is unbounded from below if $gammagamma_c$.
  arXiv  Detail & Related papers  (2022-07-01T10:01: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)
• Nearly-frustration-free ground state preparation [0.0]
  Solving for quantum ground states is important for understanding the properties of quantum many-body systems. Recent work has presented a nearly optimal scheme that prepares ground states on a quantum computer for completely generic Hamiltonians.
  arXiv  Detail & Related papers  (2021-08-06T18:00:04Z)
• Anisotropy-mediated reentrant localization [62.997667081978825]
  We consider a 2d dipolar system, $d=2$, with the generalized dipole-dipole interaction $sim r-a$, and the power $a$ controlled experimentally in trapped-ion or Rydberg-atom systems. We show that the spatially homogeneous tilt $beta$ of the dipoles giving rise to the anisotropic dipole exchange leads to the non-trivial reentrant localization beyond the locator expansion.
  arXiv  Detail & Related papers  (2020-01-31T19:00:01Z)
• Computing local properties in the trivial phase [2.741266294612776]
  A translation-invariant gapped local Hamiltonian is in the trivial phase if it can be connected to a completely decoupled Hamiltonian. We show that the expectation value of a local observable can be computed in time.
  arXiv  Detail & Related papers  (2020-01-29T11:33:10Z)

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.