Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians

• URL: http://arxiv.org/abs/2210.08680v1
• Date: Mon, 17 Oct 2022 00:55:35 GMT
• Title: Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians
• Authors: Thiago Bergamaschi
• Abstract summary: Ground state energy and the free energy of Quantum Local Hamiltonians are fundamental quantities in quantum many-body physics. We develop new techniques to find classical, additive error product-state approximations for these quantities on certain families of Quantum $k$-Local Hamiltonians.
• Score: 0.15229257192293202
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The ground state energy and the free energy of Quantum Local Hamiltonians are fundamental quantities in quantum many-body physics, however, it is QMA-Hard to estimate them in general. In this paper, we develop new techniques to find classical, additive error product-state approximations for these quantities on certain families of Quantum $k$-Local Hamiltonians. Namely, those which are either dense, have low threshold rank, or are defined on a sparse graph that excludes a fixed minor, building on the methods and the systems studied by Brand\~ao and Harrow, Gharibian and Kempe, and Bansal, Bravyi and Terhal. We present two main technical contributions. First, we discuss a connection between product-state approximations of local Hamiltonians and combinatorial graph property testing. We develop a series of weak Szemer\'edi regularity lemmas for $k$-local Hamiltonians, built on those of Frieze and Kannan and others. We use them to develop constant time sampling algorithms, and to characterize the `vertex sample complexity' of the Local Hamiltonian problem, in an analog to a classical result by Alon, de la Vega, Kannan and Karpinski. Second, we build on the information-theoretic product-state approximation techniques by Brand\~ao and Harrow, extending their results to the free energy and to an asymmetric graph setting. We leverage this structure to define families of algorithms for the free energy at low temperatures, and new algorithms for certain sparse graph families.

Related papers

• 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)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms [48.869199703062606]
  A fundamental problem in quantum many-body physics is that of finding ground states of local Hamiltonians. We introduce two approaches that achieve a constant sample complexity, independent of system size $n$, for learning ground state properties.
  arXiv  Detail & Related papers  (2024-05-28T18:00:32Z)
• An efficient and exact noncommutative quantum Gibbs sampler [0.0]
  We construct the first efficiently implementable and exactly detailed-balanced Lindbladian for Gibbs states of arbitrary noncommutative Hamiltonians. Our construction can also be regarded as a continuous-time quantum analog of the Metropolis-Hastings algorithm.
  arXiv  Detail & Related papers  (2023-11-15T18:51:24Z)
• Analysis of sum-of-squares relaxations for the quantum rotor model [0.0]
  The noncommutative sum-of-squares hierarchy was introduced by Navascu'es-Pironio-Ac'i as a sequence of semidefinite programming relaxations for approximating quantum values of nonlocal games. Recent work has started to analyze the hierarchy for approximating ground energies of local Hamiltonians.
  arXiv  Detail & Related papers  (2023-11-15T14:53:22Z)
• 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)
• Quantum approximation algorithms for many-body and electronic structure problems [0.0]
  Three algorithms produce approximate ground states for many-body and electronic structure problems. They can be used stand-alone or in conjunction with existing quantum algorithms for ground states.
  arXiv  Detail & Related papers  (2021-11-15T21:30:53Z)
• 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)
• 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)
• 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)

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.