Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.59
URN: urn:nbn:de:0030-drops-126629
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12662/
Hallgren, Sean ; Lee, Eunou ; Parekh, Ojas
An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{hallgren_et_al:LIPIcs:2020:12662,
author = {Sean Hallgren and Eunou Lee and Ojas Parekh},
title = {{An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {59:1--59:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-164-1},
ISSN = {1868-8969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12662},
URN = {urn:nbn:de:0030-drops-126629},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.59},
annote = {Keywords: approximation algorithm, quantum computing, local Hamiltonian, mean-field theory, randomized rounding}
}
| Keywords: | approximation algorithm, quantum computing, local Hamiltonian, mean-field theory, randomized rounding | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 11.08.2020 |
