Improved approximation algorithms for the EPR Hamiltonian

• URL: http://arxiv.org/abs/2504.10712v1
• Date: Mon, 14 Apr 2025 21:08:40 GMT
• Title: Improved approximation algorithms for the EPR Hamiltonian
• Authors: Nathan Ju, Ansh Nagda,
• Abstract summary: The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King (arXiv:2202589)<n>We introduce a time $frac1+sqrt54$-approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King (arXiv:2209.02589). We introduce a polynomial time $\frac{1+\sqrt{5}}{4}\approx 0.809$-approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian, improving upon the previous state of the art of $0.72$ (arXiv:2410.15544). As a special case, this also implies a $\frac{1+\sqrt{5}}{4}$-approximation for Quantum Max Cut on bipartite instances, improving upon the approximation ratio of $3/4$ that one can infer in a relatively straightforward manner from the work of Lee and Parekh (arXiv:2401.03616).

Related papers

• A Refined Algorithm For the EPR model [0.0]
  Two groups independently develop specific algorithms for the highest-energy state with approximation ratio $frac1+sqrt54approx.809$.<n>Here we try to refine one of the two algorithms by devising homogeneous/quasi-homogeneous fractional matchings.<n>For irregular graphs, we show such a refinement could still guarantee nice performance if the fractional matchings are chosen properly.
  arXiv  Detail & Related papers  (2025-06-10T08:12:14Z)
• Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings [0.18641315013048299]
  A novel ingredient in both of these algorithms is to partially entangle pairs of qubits associated to edges in a matching. This allows us to interpolate between product states and matching-based states with a tunable parameter.
  arXiv  Detail & Related papers  (2025-04-21T17:59:02Z)
• Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians [37.96754147111215]
  We prove new monogamy of entanglement bounds for two-local qudit Hamiltonians of rank-one projectors without one-local terms. In particular, we certify the ground state energy in terms of the maximum matching of the underlying interaction graph via low-degree sum-of-squares.
  arXiv  Detail & Related papers  (2024-10-21T00:10:51Z)
• Rigorous derivation of the Efimov effect in a simple model [68.8204255655161]
  We consider a system of three identical bosons in $mathbbR3$ with two-body zero-range interactions and a three-body hard-core repulsion of a given radius $a>0$.
  arXiv  Detail & Related papers  (2023-06-21T10:11:28Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  We propose a provably efficient reinforcement learning algorithm (both computationally and statistically) with general value function approximations. Our algorithm achieves reasonable regret bounds when applied to both the linear setting and the sparse high-dimensional linear setting.
  arXiv  Detail & Related papers  (2023-02-22T20:21:25Z)
• Improved Approximations for Extremal Eigenvalues of Sparse Hamiltonians [2.6763498831034043]
  We give a classical $1/(qk+1)$-approximation for the maximum eigenvalue of a $k$-sparse fermionic Hamiltonian with strictly $q$-local terms. More generally we obtain a $1/O(qk2)$-approximation for $k$-sparse fermionic Hamiltonians with terms of locality at most $q$.
  arXiv  Detail & Related papers  (2023-01-11T18:31:10Z)
• Optimizing sparse fermionic Hamiltonians [0.0]
  We consider the problem of approximating the ground state energy of a fermionic Hamiltonian using a Gaussian state. We prove that strictly $q$-local $rm textit sparse$ fermionic Hamiltonians have a constant Gaussian approximation ratio.
  arXiv  Detail & Related papers  (2022-11-29T19:00:01Z)
• An Improved Approximation Algorithm for Quantum Max-Cut [0.0]
  We give an approximation algorithm for Quantum Max-Cut which works by rounding an SDP relaxation to an entangled quantum state. For the EPR Hamiltonian, we give an approximation algorithm with approximation ratio $1 / sqrt2$ on all graphs.
  arXiv  Detail & Related papers  (2022-09-06T15:45:04Z)
• Some Remarks on the Regularized Hamiltonian for Three Bosons with Contact Interactions [77.34726150561087]
  We discuss some properties of a model Hamiltonian for a system of three bosons interacting via zero-range forces in three dimensions. In particular, starting from a suitable quadratic form $Q$, the self-adjoint and bounded from below Hamiltonian $mathcal H$ can be constructed. We show that the threshold value $gamma_c$ is optimal, in the sense that the quadratic form $Q$ is unbounded from below if $gammagamma_c$.
  arXiv  Detail & Related papers  (2022-07-01T10:01:14Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  We study reinforcement learning with linear function approximation where the underlying transition probability kernel of the Markov decision process (MDP) is a linear mixture model. We propose a new, computationally efficient algorithm with linear function approximation named $textUCRL-VTR+$ for the aforementioned linear mixture MDPs. To the best of our knowledge, these are the first computationally efficient, nearly minimax optimal algorithms for RL with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-15T18:56:46Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  We provide the first non-asymptotic, finite-time analysis for double Q-learning. We show that both synchronous and asynchronous double Q-learning are guaranteed to converge to an $epsilon$-accurate neighborhood of the global optimum.
  arXiv  Detail & Related papers  (2020-09-29T18:48:21Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  We show that a modified greedy algorithm can achieve an approximation factor of $0.305$. We derive a data-dependent upper bound on the optimum. It can also be used to significantly improve the efficiency of such algorithms as branch and bound.
  arXiv  Detail & Related papers  (2020-08-12T15:40:21Z)

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.