Importance of the spectral gap in estimating ground-state energies

• URL: http://arxiv.org/abs/2007.11582v2
• Date: Fri, 9 Dec 2022 20:56:11 GMT
• Title: Importance of the spectral gap in estimating ground-state energies
• Authors: Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The field of quantum Hamiltonian complexity lies at the intersection of quantum many-body physics and computational complexity theory, with deep implications to both fields. The main object of study is the LocalHamiltonian problem, which is concerned with estimating the ground-state energy of a local Hamiltonian and is complete for the class QMA, a quantum generalization of the class NP. A major challenge in the field is to understand the complexity of the LocalHamiltonian problem in more physically natural parameter regimes. One crucial parameter in understanding the ground space of any Hamiltonian in many-body physics is the spectral gap, which is the difference between the smallest two eigenvalues. Despite its importance in quantum many-body physics, the role played by the spectral gap in the complexity of the LocalHamiltonian is less well-understood. In this work, we make progress on this question by considering the precise regime, in which one estimates the ground-state energy to within inverse exponential precision. Computing ground-state energies precisely is a task that is important for quantum chemistry and quantum many-body physics. In the setting of inverse-exponential precision, there is a surprising result that the complexity of LocalHamiltonian is magnified from QMA to PSPACE, the class of problems solvable in polynomial space. We clarify the reason behind this boost in complexity. Specifically, we show that the full complexity of the high precision case only comes about when the spectral gap is exponentially small. As a consequence of the proof techniques developed to show our results, we uncover important implications for the representability and circuit complexity of ground states of local Hamiltonians, the theory of uniqueness of quantum witnesses, and techniques for the amplification of quantum witnesses in the presence of postselection.

Related papers

• Simulating quantum chaos without chaos [1.7942265700058988]
  We introduce a novel class of quantum Hamiltonians that fundamentally challenges the conventional understanding of quantum chaos. Our ensemble is computationally indistinguishable from the Gaussian unitary ensemble (GUE) of strongly-interacting Hamiltonians. This stark contrast between efficient computational indistinguishability and traditional chaos indicators calls into question fundamental assumptions about the nature of quantum chaos.
  arXiv  Detail & Related papers  (2024-10-23T18:01:50Z)
• Hybrid Quantum-Classical Clustering for Preparing a Prior Distribution of Eigenspectrum [10.950807972899575]
  We consider preparing the prior distribution and circuits for the eigenspectrum of time-independent Hamiltonians. The proposed algorithm unfolds in three strategic steps: Hamiltonian transformation, parameter representation, and classical clustering. The algorithm is showcased through applications to the 1D Heisenberg system and the LiH molecular system.
  arXiv  Detail & Related papers  (2024-06-29T14:21:55Z)
• Quantum benefit of the quantum equation of motion for the strongly coupled many-body problem [0.0]
  The quantum equation of motion (qEOM) is a hybrid quantum-classical algorithm for computing excitation properties of a fermionic many-body system. We demonstrate explicitly that the qEOM exhibits a quantum benefit due to the independence of the number of required quantum measurements.
  arXiv  Detail & Related papers  (2023-09-18T22:10:26Z)
• 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)
• Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis [3.7179456510537694]
  We study a parameterized version of the local Hamiltonian problem, called the weighted local Hamiltonian problem. The relevant quantum states are superpositions of computational basis states of Hamming weight $k$. We prove that this problem is in QW[1], the first level of the quantum weft hierarchy.
  arXiv  Detail & Related papers  (2022-11-10T04:12:20Z)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  We study learnability of quantum circuit Born machines (QCBMs) and quantum generative adversarial networks (QGANs) We first analyze the generalization ability of QCBMs and identify their superiorities when the quantum devices can directly access the target distribution. Next, we prove how the generalization error bound of QGANs depends on the employed Ansatz, the number of qudits, and input states.
  arXiv  Detail & Related papers  (2022-05-10T08:05:59Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• 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)
• Realizing topologically ordered states on a quantum processor [0.0845004185087851]
  Topologically ordered states has proven to be extremely challenging in both condensed matter and synthetic quantum systems. We prepare the ground state of the toric code Hamiltonian using an efficient quantum circuit on a superconducting quantum processor.
  arXiv  Detail & Related papers  (2021-04-02T18:00:01Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06: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.