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.ICALP.2021.102
URN: urn:nbn:de:0030-drops-141718
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14171/
Go to the corresponding LIPIcs Volume Portal

Parekh, Ojas ; Thompson, Kevin

Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms

pdf-format:
LIPIcs-ICALP-2021-102.pdf (0.8 MB)

Abstract

The Lasserre Hierarchy is a set of semidefinite programs which yield increasingly tight bounds on optimal solutions to many NP-hard optimization problems. The hierarchy is parameterized by levels, with a higher level corresponding to a more accurate relaxation. High level programs have proven to be invaluable components of approximation algorithms for many NP-hard optimization problems. There is a natural analogous quantum hierarchy, which is also parameterized by level and provides a relaxation of many (QMA-hard) quantum problems of interest. In contrast to the classical case, however, there is only one approximation algorithm which makes use of higher levels of the hierarchy. Here we provide the first ever use of the level-2 hierarchy in an approximation algorithm for a particular QMA-complete problem, so-called Quantum Max Cut. We obtain modest improvements on state-of-the-art approximation factors for this problem, as well as demonstrate that the level-2 hierarchy satisfies many physically-motivated constraints that the level-1 does not satisfy. Indeed, this observation is at the heart of our analysis and indicates that higher levels of the quantum Lasserre Hierarchy may be very useful tools in the design of approximation algorithms for QMA-complete problems.

BibTeX - Entry

@InProceedings{parekh_et_al:LIPIcs.ICALP.2021.102,
  author =	{Parekh, Ojas and Thompson, Kevin},
  title =	{{Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{102:1--102:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14171},
  URN =		{urn:nbn:de:0030-drops-141718},
  doi =		{10.4230/LIPIcs.ICALP.2021.102},
  annote =	{Keywords: Quantum Max Cut, Quantum Approximation Algorithms, Lasserre Hierarchy, Local Hamiltonian, Heisenberg model}
}

Keywords: Quantum Max Cut, Quantum Approximation Algorithms, Lasserre Hierarchy, Local Hamiltonian, Heisenberg model
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

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