License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.74
URN: urn:nbn:de:0030-drops-146554
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14655/
Go to the corresponding LIPIcs Volume Portal

Parekh, Ojas ; Thompson, Kevin

Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems

pdf-format:
LIPIcs-ESA-2021-74.pdf (0.8 MB)

Abstract

The quantum k-Local Hamiltonian problem is a natural generalization of classical constraint satisfaction problems (k-CSP) and is complete for QMA, a quantum analog of NP. Although the complexity of k-Local Hamiltonian problems has been well studied, only a handful of approximation results are known. For Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural quantum generalization of classical Max 2-SAT, the best known approximation algorithm was the trivial random assignment, yielding a 0.75-approximation. We present the first approximation algorithm beating this bound, a classical polynomial-time 0.764-approximation. For strictly quadratic instances, which are maximally entangled instances, we provide a 0.801 approximation algorithm, and numerically demonstrate that our algorithm is likely a 0.821-approximation. We conjecture these are the hardest instances to approximate. We also give improved approximations for quantum generalizations of other related classical 2-CSPs. Finally, we exploit quantum connections to a generalization of the Grothendieck problem to obtain a classical constant-factor approximation for the physically relevant special case of strictly quadratic traceless 2-Local Hamiltonians on bipartite interaction graphs, where a inverse logarithmic approximation was the best previously known (for general interaction graphs). Our work employs recently developed techniques for analyzing classical approximations of CSPs and is intended to be accessible to both quantum information scientists and classical computer scientists.

BibTeX - Entry

@InProceedings{parekh_et_al:LIPIcs.ESA.2021.74,
  author =	{Parekh, Ojas and Thompson, Kevin},
  title =	{{Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{74:1--74:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14655},
  URN =		{urn:nbn:de:0030-drops-146554},
  doi =		{10.4230/LIPIcs.ESA.2021.74},
  annote =	{Keywords: Quantum Approximation Algorithms, Local Hamiltonian}
}

Keywords: Quantum Approximation Algorithms, Local Hamiltonian
Collection: 29th Annual European Symposium on Algorithms (ESA 2021)
Issue Date: 2021
Date of publication: 31.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI