2026-09-23T00:35:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27280 2026-09-05T20:17:31Z ddc:004 open_access

A 0.8395-Approximation Algorithm for the EPR Problem Apte, Anuj Lee, Eunou Marwaha, Kunal Parekh, Ojas Sinjorgo, Lennart Sud, James Quantum computing optimization approximation algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anuj Apte and Eunou Lee and Kunal Marwaha and Ojas Parekh and Lennart Sinjorgo and James Sud 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.144 urn:nbn:de:0030-drops-272806 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.144 eng https://creativecommons.org/licenses/by/4.0/legalcode