DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2025.101

Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings

Authors: Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

We introduce a 0.611-approximation algorithm for Quantum MaxCut and a (1+√5)/4 ≈ 0.809-approximation algorithm for the EPR Hamiltonian of [King, 2023]. A novel ingredient in both of these algorithms is to partially entangle pairs of qubits associated to edges in a matching, while preserving the direction of their single-qubit Bloch vectors. This allows us to interpolate between product states and matching-based states with a tunable parameter.

Cite as

Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud. Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 101:1-101:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{apte_et_al:LIPIcs.ESA.2025.101,
  author =	{Apte, Anuj and Lee, Eunou and Marwaha, Kunal and Parekh, Ojas and Sud, James},
  title =	{{Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{101:1--101:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.101},
  URN =		{urn:nbn:de:0030-drops-245705},
  doi =		{10.4230/LIPIcs.ESA.2025.101},
  annote =	{Keywords: Quantum computing, Quantum MaxCut, Maximum matching}
}

Search Results

Documents authored by Apte, Anuj

Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings

Abstract

Cite as

Thanks for your feedback!

Could not send message