TY - GEN

T1 - An approximation algorithm for the MAX-2-local hamiltonian problem

AU - Hallgren, Sean

AU - Lee, Eunou

AU - Parekh, Ojas

N1 - Funding Information:
Funding Sean Hallgren: Partially supported by National Science Foundation awards CCF-1618287, CCF-1617710 and CNS-1617802, by a Vannevar Bush Faculty Fellowship from the US Department of Defense, and in part while the author was visiting the Simons Institute for the Theory of Computing. Ojas Parekh: Sandia National Laboratories is a multimission laboratory managed and operated by National Technology and Engineering Solutions of Sandia, LLC., a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA-0003525. Supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Accelerated Research for Quantum Computing and Quantum Algorithms Teams programs.
Publisher Copyright:
© 2020 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

PY - 2020/8/1

Y1 - 2020/8/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85091272313&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85091272313&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.APPROX/RANDOM.2020.59

DO - 10.4230/LIPIcs.APPROX/RANDOM.2020.59

M3 - Conference contribution

AN - SCOPUS:85091272313

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020

A2 - Byrka, Jaroslaw

A2 - Meka, Raghu

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020

Y2 - 17 August 2020 through 19 August 2020

ER -