2026-07-25T02:54:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12662 2024-03-06T10:51:23Z ddc:004 open_access

An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem Hallgren, Sean Lee, Eunou Parekh, Ojas approximation algorithm quantum computing local Hamiltonian mean-field theory randomized rounding We present a classical approximation algorithm for the MAX-2-Local Hamiltonian problem. This is a maximization version of the QMA-complete 2-Local Hamiltonian problem in quantum computing, with the additional assumption that each local term is positive semidefinite. The MAX-2-Local Hamiltonian problem generalizes NP-hard constraint satisfaction problems, and our results may be viewed as generalizations of approximation approaches for the MAX-2-CSP problem. We work in the product state space and extend the framework of Goemans and Williamson for approximating MAX-2-CSPs. The key difference is that in the product state setting, a solution consists of a set of normalized 3-dimensional vectors rather than boolean numbers, and we leverage approximation results for rank-constrained Grothendieck inequalities. For MAX-2-Local Hamiltonian we achieve an approximation ratio of 0.328. This is the first example of an approximation algorithm beating the random quantum assignment ratio of 0.25 by a constant factor. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sean Hallgren and Eunou Lee and Ojas Parekh 2020 Is Part Of LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2020.59 urn:nbn:de:0030-drops-126629 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.59 eng https://creativecommons.org/licenses/by/3.0/legalcode