A 0.8395-approximation algorithm for the EPR problem

Fuente: arXiv
Saved in:
Bibliographic Details
Main Authors: Apte, Anuj, Lee, Eunou, Marwaha, Kunal, Parekh, Ojas, Sinjorgo, Lennart, Sud, James
Format: Preprint
Published: 2025
Subjects:
Online Access:
Tags: Add Tag
No Tags, Be the first to tag this record!
_version_ 1866909955203792896
author Apte, Anuj
Lee, Eunou
Marwaha, Kunal
Parekh, Ojas
Sinjorgo, Lennart
Sud, James
author_facet Apte, Anuj
Lee, Eunou
Marwaha, Kunal
Parekh, Ojas
Sinjorgo, Lennart
Sud, James
contents 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.
format Preprint
id arxiv_https___arxiv_org_abs_2512_09896
institution arXiv
publishDate 2025
record_format arxiv
spellingShingle A 0.8395-approximation algorithm for the EPR problem
Apte, Anuj
Lee, Eunou
Marwaha, Kunal
Parekh, Ojas
Sinjorgo, Lennart
Sud, James
Quantum Physics
Data Structures and 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.
title A 0.8395-approximation algorithm for the EPR problem
topic Quantum Physics
Data Structures and Algorithms
url https://arxiv.org/abs/2512.09896