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.TQC.2020.7
URN: urn:nbn:de:0030-drops-120660
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12066/
Go to the corresponding LIPIcs Volume Portal

Anshu, Anurag ; Gosset, David ; Morenz, Karen

Beyond Product State Approximations for a Quantum Analogue of Max Cut

pdf-format:
LIPIcs-TQC-2020-7.pdf (0.5 MB)

Abstract

We consider a computational problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits located at the vertices of a graph. Previous work has shed light on this problem’s approximability by product states. For any instance of this problem the maximum energy attained by a product state is lower bounded by the Max Cut of the graph and upper bounded by the standard Goemans-Williamson semidefinite programming relaxation of it. Gharibian and Parekh described an efficient classical approximation algorithm for this problem which outputs a product state with energy at least 0.498 times the maximum eigenvalue in the worst case, and observe that there exist instances where the best product state has energy 1/2 of optimal. We investigate approximation algorithms with performance exceeding this limitation which are based on optimizing over tensor products of few-qubit states and shallow quantum circuits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case. We also show that for any instance defined by a 3 or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation).

BibTeX - Entry

@InProceedings{anshu_et_al:LIPIcs:2020:12066,
  author =	{Anurag Anshu and David Gosset and Karen Morenz},
  title =	{{Beyond Product State Approximations for a Quantum Analogue of Max Cut}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Steven T. Flammia},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12066},
  URN =		{urn:nbn:de:0030-drops-120660},
  doi =		{10.4230/LIPIcs.TQC.2020.7},
  annote =	{Keywords: Approximation algorithms, Quantum many-body systems}
}

Keywords: Approximation algorithms, Quantum many-body systems
Collection: 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)
Issue Date: 2020
Date of publication: 08.06.2020

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