A note on lower bounds to variational problems with guarantees

• URL: http://arxiv.org/abs/2301.06142v1
• Date: Sun, 15 Jan 2023 16:48:57 GMT
• Title: A note on lower bounds to variational problems with guarantees
• Authors: J. Eisert
• Abstract summary: Variational methods play an important role in the study of quantum many body problems. This note stresses that for translationally invariant lattice Hamiltonians, one can easily derive efficiently computable lower bounds to ground state energies.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Variational methods play an important role in the study of quantum many body problems, both in the flavour of classical variational principles based on tensor networks as well as of quantum variational principles in near-term quantum computing. This brief pedagogical note stresses that for translationally invariant lattice Hamiltonians, one can easily derive efficiently computable lower bounds to ground state energies that can and should be compared with variational principles providing upper bounds. As small technical results, it is shown that (i) the Anderson bound and a (ii) common hierarchy of semi-definite relaxations both provide approximations with performance guarantees that scale like a constant in the energy density for cubic lattices. (iii) Also, the Anderson bound is systematically improved as a hierarchy of semi-definite relaxations inspired by the marginal problem.

Related papers

• Assessing the query complexity limits of quantum phase estimation using symmetry aware spectral bounds [0.0]
  computational cost of quantum algorithms for physics and chemistry is closely linked to the spectrum of the Hamiltonian. We introduce a hierarchy of symmetry-aware spectral bounds that provide a unified understanding of the performance of quantum phase estimation algorithms.
  arXiv  Detail & Related papers  (2024-03-07T18:38:49Z)
• Hamiltonian truncation tensor networks for quantum field theories [42.2225785045544]
  We introduce a tensor network method for the classical simulation of continuous quantum field theories. The method is built on Hamiltonian truncation and tensor network techniques. One of the key developments is the exact construction of matrix product state representations of global projectors.
  arXiv  Detail & Related papers  (2023-12-19T19:00:02Z)
• Lower Bounding Ground-State Energies of Local Hamiltonians Through the Renormalization Group [0.0]
  We show how to formulate a tractable convex relaxation of the set of feasible local density matrices of a quantum system. The coarse-graining maps of the underlying renormalization procedure serve to eliminate a vast number of those constraints. This can be used to obtain rigorous lower bounds on the ground state energy of arbitrary local Hamiltonians.
  arXiv  Detail & Related papers  (2022-12-06T14:39:47Z)
• Beyond the Edge of Stability via Two-step Gradient Updates [49.03389279816152]
  Gradient Descent (GD) is a powerful workhorse of modern machine learning. GD's ability to find local minimisers is only guaranteed for losses with Lipschitz gradients. This work focuses on simple, yet representative, learning problems via analysis of two-step gradient updates.
  arXiv  Detail & Related papers  (2022-06-08T21:32:50Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  We prove the first high-probability results with logarithmic dependence on the confidence level for methods for solving monotone and structured non-monotone VIPs. Our results match the best-known ones in the light-tails case and are novel for structured non-monotone problems. In addition, we numerically validate that the gradient noise of many practical formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
  arXiv  Detail & Related papers  (2022-06-02T15:21:55Z)
• Decimation technique for open quantum systems: a case study with driven-dissipative bosonic chains [62.997667081978825]
  Unavoidable coupling of quantum systems to external degrees of freedom leads to dissipative (non-unitary) dynamics. We introduce a method to deal with these systems based on the calculation of (dissipative) lattice Green's function. We illustrate the power of this method with several examples of driven-dissipative bosonic chains of increasing complexity.
  arXiv  Detail & Related papers  (2022-02-15T19:00:09Z)
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization [40.21627891283402]
  This paper investigates the problem of computing the equilibrium of competitive games. Motivated by the algorithmic role of entropy regularization, we develop provably efficient extragradient methods.
  arXiv  Detail & Related papers  (2021-05-31T17:51:15Z)
• Gauge invariant quantum circuits for $U(1)$ and Yang-Mills lattice gauge theories [0.0]
  A new class of parametrized quantum circuits can represent states belonging only to the physical sector of the total Hilbert space. This class of circuits is compact yet flexible enough to be used as a variational ansatz to study ground state properties.
  arXiv  Detail & Related papers  (2021-05-12T18:00:10Z)
• Quantitative Propagation of Chaos for SGD in Wide Neural Networks [39.35545193410871]
  In this paper, we investigate the limiting behavior of a continuous-time counterpart of the Gradient Descent (SGD) We show 'propagation of chaos' for the particle system defined by this continuous-time dynamics under different scenarios. We identify two under which different mean-field limits are obtained, one of them corresponding to an implicitly regularized version of the minimization problem at hand.
  arXiv  Detail & Related papers  (2020-07-13T12:55:21Z)
• Efficient variational contraction of two-dimensional tensor networks with a non-trivial unit cell [0.0]
  tensor network states provide an efficient class of states that faithfully capture strongly correlated quantum models and systems. We generalize a recently proposed variational uniform matrix product state algorithm for capturing one-dimensional quantum lattices. A key property of the algorithm is a computational effort that scales linearly rather than exponentially in the size of the unit cell.
  arXiv  Detail & Related papers  (2020-03-02T19:01:06Z)
• Variational-Correlations Approach to Quantum Many-body Problems [1.9336815376402714]
  We investigate an approach for studying the ground state of a quantum many-body Hamiltonian. The challenge set by the exponentially-large Hilbert space is circumvented by approximating the positivity of the density matrix. We demonstrate the ability of this approach to produce long-range correlations, and a ground-state energy that converges to the exact result.
  arXiv  Detail & Related papers  (2020-01-17T19:52:54Z)

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.