License: 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.2019.31
URN: urn:nbn:de:0030-drops-112463
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11246/
Go to the corresponding LIPIcs Volume Portal

Gharibian, Sevag ; Parekh, Ojas

Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut

pdf-format:
LIPIcs-APPROX-RANDOM-2019-31.pdf (0.5 MB)

Abstract

Approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a physically motivated quantum generalization of Max-Cut, known as the quantum Heisenberg model. This model is notoriously difficult to solve exactly, even on bipartite graphs, in stark contrast to the classical setting of Max-Cut. Here we show, for any interaction graph, how to classically and efficiently obtain approximation ratios 0.649 (anti-feromagnetic XY model) and 0.498 (anti-ferromagnetic Heisenberg XYZ model). These are almost optimal; we show that the best possible ratios achievable by a product state for these models is 2/3 and 1/2, respectively.

BibTeX - Entry

@InProceedings{gharibian_et_al:LIPIcs:2019:11246,
  author =	{Sevag Gharibian and Ojas Parekh},
  title =	{{Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11246},
  URN =		{urn:nbn:de:0030-drops-112463},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.31},
  annote =	{Keywords: Approximation algorithm, Max-Cut, local Hamiltonian, QMA-hard, Heisenberg model, product state}
}

Keywords: Approximation algorithm, Max-Cut, local Hamiltonian, QMA-hard, Heisenberg model, product state
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

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