DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.144

A 0.8395-Approximation Algorithm for the EPR Problem

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

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

We give an efficient 0.8395-approximation algorithm for the EPR Hamiltonian. Our improvement comes from a new nonlinear monogamy-of-entanglement bound on star graphs and a refined parameterization of a shallow quantum circuit from previous works. We also prove limitations showing that current methods cannot achieve substantially better approximation ratios, indicating that further progress will require fundamentally new techniques.

Cite as

Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, Lennart Sinjorgo, and James Sud. A 0.8395-Approximation Algorithm for the EPR Problem. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 144:1-144:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{apte_et_al:LIPIcs.ESA.2026.144,
  author =	{Apte, Anuj and Lee, Eunou and Marwaha, Kunal and Parekh, Ojas and Sinjorgo, Lennart and Sud, James},
  title =	{{A 0.8395-Approximation Algorithm for the EPR Problem}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{144:1--144:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.144},
  URN =		{urn:nbn:de:0030-drops-272806},
  doi =		{10.4230/LIPIcs.ESA.2026.144},
  annote =	{Keywords: Quantum computing, optimization, approximation algorithms}
}

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

A 0.8395-Approximation Algorithm for the EPR Problem

Abstract

Cite as

Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings

Abstract

Cite as

Thanks for your feedback!

Could not send message