Hamiltonian Complexity in the Thermodynamic Limit

• URL: http://arxiv.org/abs/2107.06201v2
• Date: Sun, 7 Nov 2021 21:45:43 GMT
• Title: Hamiltonian Complexity in the Thermodynamic Limit
• Authors: Dorit Aharonov and Sandy Irani
• Abstract summary: 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.
• Score: 0.7863638253070437
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite progress in quantum Hamiltonian complexity, little is known about the computational complexity of quantum physics at the thermodynamic limit. Even defining the problem is not straight forward. We study the complexity of estimating the ground energy of a fixed, translationally invariant Hamiltonian in the thermodynamic limit, to within a given precision; the number of bits $n$ for the precision is the sole input to the problem. The complexity of this problem captures how difficult it is for the physicist to measure or compute another digit in the approximation of a physical quantity in the thermodynamic limit. We show that this problem is contained in $\mbox{FEXP}^{\mbox{QMA-EXP}}$ and is hard for $\mbox{FEXP}^{\mbox{NEXP}}$. This means that the problem is doubly exponentially hard in the size of the input. As an ingredient in our construction, we study the problem of computing the ground energy of translationally invariant finite 1D chains. A single Hamiltonian term, which is a fixed parameter of the problem, is applied to every pair of particles in a finite chain. The length of the chain is the sole input to the problem and the task is to compute an approximation of the ground energy. No thresholds are provided as in the standard formulation of the local Hamiltonian problem. We show that this problem is contained in $\mbox{FP}^{\mbox{QMA-EXP}}$ and is hard for $\mbox{FP}^{\mbox{NEXP}}$. Our techniques employ a circular clock in which the ground energy is calibrated by the length of the cycle. This requires more precise expressions for the ground states of the resulting matrices than was required for previous QMA-completeness constructions and even exact analytical bounds for the infinite case which we derive using techniques from spectral graph theory. To our knowledge, this is the first use of the circuit-to-Hamiltonian construction which shows hardness for a function class.

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)
• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma. This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles. Even with sublinear barriers, we use Feynman-Kac techniques to lift classical to quantum ones establishing tight lower bound $T_mathrmmix = 2Omega(nalpha)$.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
  We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. We present a quantum algorithm that uses $O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$ queries to the block-encoding for any $Gamma$.
  arXiv  Detail & Related papers  (2024-04-04T17:58:01Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• End-to-end complexity for simulating the Schwinger model on quantum computers [0.6449786007855248]
  We propose an efficient implementation of block-encoding of the Schwinger model Hamiltonian. As an end-to-end application, we compute the vacuum persistence amplitude. Our results provide insights into predictions about the performance of quantum computers in the FTQC era.
  arXiv  Detail & Related papers  (2023-11-29T06:36:11Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• 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)
• On the complexity of quantum partition functions [2.6937287784482313]
  We study the computational complexity of approximating quantities for $n$-qubit local Hamiltonians. A classical algorithm with $mathrmpoly(n)$ approximates the free energy of a given $2$-local Hamiltonian.
  arXiv  Detail & Related papers  (2021-10-29T00:05:25Z)
• Computational Complexity of the Ground State Energy Density Problem [0.0]
  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
  arXiv  Detail & Related papers  (2021-07-11T14:52:43Z)
• Quantum supremacy and hardness of estimating output probabilities of quantum circuits [0.0]
  We prove under the theoretical complexity of the non-concentration hierarchy that approximating the output probabilities to within $2-Omega(nlogn)$ is hard. We show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including trivial circuit with identity gates.
  arXiv  Detail & Related papers  (2021-02-03T09:20:32Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
  arXiv  Detail & Related papers  (2020-02-27T15:32:08Z)

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.