Computational Complexity of the Ground State Energy Density Problem
- URL: http://arxiv.org/abs/2107.05060v1
- Date: Sun, 11 Jul 2021 14:52:43 GMT
- Title: Computational Complexity of the Ground State Energy Density Problem
- Authors: James D. Watson, Toby S. Cubitt
- Abstract summary: We study the complexity of finding the ground state energy density of a local Hamiltonian on a lattice in the thermodynamic limit of infinite lattice size.
We show that for classical, translationally invariant, nearest neighbour Hamiltonians on a 2D square lattice, $mathsfPmathsfNEEXPsubseteqmathsfEXPmathsfGSEDsubseteq mathsfEXPmathsfNEXP$, and for quantum Hamiltonians $mathsfPmathsfNEEXPsubseteqmathsfEXPmath
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the complexity of finding the ground state energy density of a local
Hamiltonian on a lattice in the thermodynamic limit of infinite lattice size.
We formulate this rigorously as a function problem, in which we request an
estimate of the ground state energy density to some specified precision; and as
an equivalent promise problem, $\mathsf{GSED}$, in which we ask whether the
ground state energy density is above or below specified thresholds.
The ground state energy density problem is unusual, in that it concerns a
single, fixed Hamiltonian in the thermodynamic limit, whose ground state energy
density is just some fixed, real number. The only input to the computational
problem is the precision to which to estimate this fixed real number,
corresponding to the ground state energy density. Hardness of this problem for
a complexity class therefore implies that the solutions to all problems in the
class are encoded in this single number (analogous to Chaitin's constant in
computability theory).
This captures computationally the type of question most commonly encountered
in condensed matter physics, which is typically concerned with the physical
properties of a single Hamiltonian in the thermodynamic limit. We show that for
classical, translationally invariant, nearest neighbour Hamiltonians on a 2D
square lattice,
$\mathsf{P}^{\mathsf{NEEXP}}\subseteq\mathsf{EXP}^{\mathsf{GSED}}\subseteq
\mathsf{EXP}^{\mathsf{NEXP}}$, and for quantum Hamiltonians
$\mathsf{P}^{\mathsf{NEEXP}}\subseteq\mathsf{EXP}^{\mathsf{GSED}}\subseteq
\mathsf{EXP}^{\mathsf{QMA}_{EXP}}$. With some technical caveats on the oracle
definitions, the $\mathsf{EXP}$ in some of these results can be strengthened to
$\mathsf{PSPACE}$. We also give analogous complexity bounds for the function
version of $\mathsf{GSED}$.
Related papers
- On the Computational Complexity of Schrödinger Operators [6.1436827446807705]
We study computational problems related to the Schr"odinger operator $H = -Delta + V$ in the real space.
We prove that (i) simulating the dynamics generated by the Schr"odinger operator implements universal quantum computation, i.e., it is BQP-hard, and (ii) estimating the ground energy of the Schr"odinger operator is as hard as estimating that of local Hamiltonians with no sign problem (a.k.a. stoquastic Hamiltonians)
This result is particularly intriguing because the ground energy problem for general bosonic Hamiltonians is known
arXiv Detail & Related papers (2024-11-07T19:39:52Z) - On stability of k-local quantum phases of matter [0.4999814847776097]
We analyze the stability of the energy gap to Euclids for Hamiltonians corresponding to general quantum low-density parity-check codes.
We discuss implications for the third law of thermodynamics, as $k$-local Hamiltonians can have extensive zero-temperature entropy.
arXiv Detail & Related papers (2024-05-29T18:00:20Z) - Contactium: A strongly correlated model system [0.0]
We study the one-particle description of a system that comprises two fermions or bosons in a confinement interacting through the Fermi--Huang pseudopotential.
A detailed analysis of the one-particle description reveals several peculiarities that are not encountered in conventional model systems.
arXiv Detail & Related papers (2023-03-27T08:27:33Z) - Nonlocality under Computational Assumptions [51.020610614131186]
A set of correlations is said to be nonlocal if it cannot be reproduced by spacelike-separated parties sharing randomness and performing local operations.
We show that there exist (efficient) local producing measurements that cannot be reproduced through randomness and quantum-time computation.
arXiv Detail & Related papers (2023-03-03T16:53:30Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation.
For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z) - Finite temperature quantum condensations in the space of states: General
Proof [0.0]
We prove the extension to finite temperature of a class of quantum phase transitions, acting as condensations in the space of states.
We also show that the critical surface has universal features at high and low temperatures.
arXiv Detail & Related papers (2022-09-27T08:33:16Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations.
The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
arXiv Detail & Related papers (2022-06-17T17:55:43Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation.
We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals.
Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
arXiv Detail & Related papers (2021-08-19T16:16:48Z) - Hamiltonian Complexity in the Thermodynamic Limit [0.7863638253070437]
We study the complexity of estimating the ground energy of a fixed, translationally invariant Hamiltonian in the thermodynamic limit.
We show that this problem is contained in $mboxFEXPmboxQMA-EXP$ and is hard for $mboxFPmboxNEXP$.
As an ingredient in our construction, we study the problem of computing the ground energy of translationally invariant finite 1D chains.
arXiv Detail & Related papers (2021-07-13T16:00:11Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
We consider non-con minimax problems, $min_mathbfx max_mathhidoty f(mathbfdoty)$ efficiently.
arXiv Detail & Related papers (2019-06-02T03:03:45Z)
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.