Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians

Zackary Jorquera; Alexandra Kolla; Steven Kordonowy; Juspreet Singh Sandhu; Stuart Wayland

doi:10.22331/q-2026-04-28-2088

Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians

Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, Juspreet Singh Sandhu, and Stuart Wayland

University of California, Santa Cruz, CA 95060, USA

Published:	2026-04-28, volume 10, page 2088
Editor:	Tom Gur
Eprint:	arXiv:2410.15544v4
Doi:	https://doi.org/10.22331/q-2026-04-28-2088
Citation:	Quantum 10, 2088 (2026).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We prove new monogamy of entanglement bounds for two-local qudit Hamiltonians of rank-one projectors without one-local terms. In particular, we certify the maximum energy in terms of the maximum matching of the underlying interaction graph via low-degree sum-of-squares proofs. Algorithmically, we show that a simple matching-based algorithm approximates the maximum energy to at least $1/d$ for general graphs and to at least $1/d + \Theta(1/D)$ for graphs with bounded degree, $D$. This outperforms random assignment, which, in expectation, achieves energy of only $1/d^2$ of the maximum energy for general graphs. Notably, on $D$-regular graphs with degree, $D \leq 5$, and for any local dimension, $d$, we show that this simple matching-based algorithm has an approximation guarantee of $1/2$. Lastly, when $d=2$, we present an algorithm achieving an approximation guarantee of $0.595$, beating that of [31], which gave an approximation ratio of $1/2$.

► BibTeX data

@article{Jorquera2026monogamyof,
  doi = {10.22331/q-2026-04-28-2088},
  url = {https://doi.org/10.22331/q-2026-04-28-2088},
  title = {Monogamy of {E}ntanglement {B}ounds and {I}mproved {A}pproximation {A}lgorithms for {Q}udit {H}amiltonians},
  author = {Jorquera, Zackary and Kolla, Alexandra and Kordonowy, Steven and Singh Sandhu, Juspreet and Wayland, Stuart},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {2088},
  month = apr,
  year = {2026}
}

► References

[1] Dorit Aharonov, Itai Arad, and Thomas Vidick, ``The Quantum PCP Conjecture'' (2013) arXiv:1309.7495 [quant-ph].
https://doi.org/10.1145/2491533.2491549
arXiv:1309.7495

[2] Anurag Anshu, David Gosset, and Karen Morenz, ``Beyond Product State Approximations for a Quantum Analogue of Max Cut'' 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020) 158, 7:1–7:15 (2020) ISSN: 1868-8969.
https://doi.org/10.4230/LIPIcs.TQC.2020.7
https://drops.dagstuhl.de/opus/volltexte/2020/12066

[3] Anurag Anshu, David Gosset, Karen J. Morenz Korol, and Mehdi Soleimanifar, ``Improved Approximation Algorithms for Bounded-Degree Local Hamiltonians'' Physical Review Letters 127, 250502 (2021) Publisher: American Physical Society.
https://doi.org/10.1103/PhysRevLett.127.250502

[4] Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, Lennart Sinjorgo, and James Sud, ``A 0.8395-approximation algorithm for the EPR problem'' (2025).
https://doi.org/10.48550/arXiv.2512.09896
arXiv:2512.09896

[5] Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud, ``Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings'' 33rd Annual European Symposium on Algorithms (ESA 2025) 351, 101:1–101:14 (2025).
https://doi.org/10.4230/LIPIcs.ESA.2025.101

[6] Sergey Bravyi, Arvid J. Bessen, and Barbara M. Terhal, ``Merlin-Arthur Games and Stoquastic Complexity'' (2006) arXiv:quant-ph/0611021.
https://doi.org/10.48550/arXiv.quant-ph/0611021
http://arxiv.org/abs/quant-ph/0611021

[7] Fernando G. S. L. Brandãoand Aram W. Harrow ``Product-State Approximations to Quantum States'' Communications in Mathematical Physics 342, 47–80 (2016).
https://doi.org/10.1007/s00220-016-2575-1

[8] Sabine Burgdorf, Igor Klep, and Janez Povh, ``Optimization of Polynomials in Non-Commuting Variables'' Springer International Publishing (2016).
https://doi.org/10.1007/978-3-319-33338-0

[9] Boaz Barakand David Steurer ``Proofs, beliefs and algorithms through the lens of Sum of Squares'' (2016).
https://www.sumofsquares.org/public/index.html

[10] Adam Bene Watts, Anirban Chowdhury, Aidan Epperly, J. William Helton, and Igor Klep, ``Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators'' Quantum 8, 1352 (2024) Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften.
https://doi.org/10.22331/q-2024-05-22-1352
https://quantum-journal.org/papers/q-2024-05-22-1352/

[11] Charlie Carlson, Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, and Stuart Wayland, ``Approximation Algorithms for Quantum Max-d-Cut'' (2023).
https://doi.org/10.48550/arXiv.2309.10957
http://arxiv.org/abs/2309.10957

[12] Toby S. Cubittand Ashley Montanaro ``Complexity Classification of Local Hamiltonian Problems'' 2014 IEEE 55th Annual Symposium on Foundations of Computer Science 120–129 (2014) ISSN: 0272-5428.
https://doi.org/10.1109/FOCS.2014.21

[13] Jack Edmonds ``Maximum matching and a polyhedron with 0,1-vertices'' Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics 69B, 125 (1965).
https://doi.org/10.6028/jres.069B.013
https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf

[14] Sevag Gharibianand Julia Kempe ``Approximation Algorithms for QMA-Complete Problems'' SIAM Journal on Computing 41, 1028–1050 (2012).
https://doi.org/10.1137/110842272

[15] Sevag Gharibianand Ojas Parekh ``Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut'' Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) 145, 31:1–31:17 (2019) ISSN: 1868-8969.
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.31
http://drops.dagstuhl.de/opus/volltexte/2019/11246

[16] Sander Gribling, Lennart Sinjorgo, and Renata Sotirov, ``Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs'' (2025).
https://doi.org/10.48550/arXiv.2504.11120
arXiv:2504.11120

[17] Yijie Han ``Tight bound for matching'' Journal of Combinatorial Optimization 23, 322–330 (2012).
https://doi.org/10.1007/s10878-010-9299-5

[18] Felix Huber, Kevin Thompson, Ojas Parekh, and Sevag Gharibian, ``Second order cone relaxations for quantum Max Cut'' (2024).
https://doi.org/10.2172/3018802
arXiv:2411.04120

[19] Nathan Juand Ansh Nagda ``Improved Approximation Algorithms for the EPR Hamiltonian'' Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) 353, 24:1–24:9 (2025).
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2025.24

[20] Robbie King ``An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs'' Quantum 7, 1180 (2023) Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften.
https://doi.org/10.22331/q-2023-11-09-1180
https://quantum-journal.org/papers/q-2023-11-09-1180/

[21] Julia Kempe, Oded Regev, and Ben Toner, ``Unique Games with Entangled Provers Are Easy'' SIAM Journal on Computing 39, 3207–3229 (2010) Publisher: Society for Industrial and Applied Mathematic.
https://doi.org/10.1137/090772885

[22] A.Y. Kitaev, A. Shen, and M.N. Vyalyi, ``Classical and Quantum Computation'' American Mathematical Society (2002).
https://doi.org/10.1090/gsm/047
https://books.google.de/books?id=08vZYhafYEAC

[23] Eunou Lee ``Optimizing Quantum Circuit Parameters via SDP'' 33rd International Symposium on Algorithms and Computation (ISAAC 2022) 248, 48:1–48:16 (2022).
https://doi.org/10.4230/LIPIcs.ISAAC.2022.48

[24] Eunou Leeand Ojas Parekh ``An Improved Quantum Max Cut Approximation via Maximum Matching'' DROPS-IDN/v2/document/10.4230/LIPIcs.ICALP.2024.105 (2024).
https://doi.org/10.4230/LIPIcs.ICALP.2024.105

[25] Hamoon Mousaviand Taro Spirig ``A Quantum Unique Games Conjecture'' (2024) arXiv:2409.20028 [quant-ph].
https://doi.org/10.4230/LIPIcs.ITCS.2025.76
http://arxiv.org/abs/2409.20028

[26] Kunal Marwahaand James Sud ``Quantum MaxCut Reference Website'' https://marwahaha.github.io/quantum-maxcut-reference/ (2025) Accessed: 2026-01-21.
https://marwahaha.github.io/quantum-maxcut-reference/

[27] Miguel Navascués, Stefano Pironio, and Antonio Acín, ``A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations'' New Journal of Physics 10, 073013 (2008).
https://doi.org/10.1088/1367-2630/10/7/073013

[28] Stephen Piddockand Ashley Montanaro ``Universal Qudit Hamiltonians'' Communications in Mathematical Physics 382, 721–771 (2021).
https://doi.org/10.1007/s00220-021-03940-3

[29] Ojas Parekhand Kevin Thompson ``Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms'' 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 198, 102:1–102:20 (2021) ISSN: 1868-8969.
https://doi.org/10.4230/LIPIcs.ICALP.2021.102
https://drops.dagstuhl.de/opus/volltexte/2021/14171

[30] Ojas Parekhand Kevin Thompson ``Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems'' 29th Annual European Symposium on Algorithms (ESA 2021) 204, 74:1–74:18 (2021) ISSN: 1868-8969.
https://doi.org/10.4230/LIPIcs.ESA.2021.74
https://drops.dagstuhl.de/opus/volltexte/2021/14655

[31] Ojas Parekhand Kevin Thompson ``An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms'' (2022) arXiv:2206.08342 [quant-ph].
https://doi.org/10.48550/arXiv.2206.08342
http://arxiv.org/abs/2206.08342

[32] Prasad Raghavendra ``Optimal algorithms and inapproximability results for every CSP?'' Proceedings of the fortieth annual ACM symposium on Theory of computing 245–254 (2008).
https://doi.org/10.1145/1374376.1374414

[33] Jun Takahashi, Chaithanya Rayudu, Cunlu Zhou, Robbie King, Kevin Thompson, and Ojas Parekh, ``An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max Cut'' (2023) arXiv:2307.15688 [quant-ph].
https://doi.org/10.48550/arXiv.2307.15688
http://arxiv.org/abs/2307.15688

[34] Wright, John ``Personal Communications'' Email (2023) Assistant Professor at University of California, Berkeley.

Cited by

[1] Ojas Parekh and Kevin Thompson, "An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms", arXiv:2206.08342, (2022).

[2] Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud, "Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings", arXiv:2504.15276, (2025).

[3] Sander Gribling, Lennart Sinjorgo, and Renata Sotirov, "Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs", arXiv:2504.11120, (2025).

[4] Wenxuan Tao and Fen Zuo, "Testing APS conjecture on regular graphs", arXiv:2507.10050, (2025).

[5] Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, Lennart Sinjorgo, and James Sud, "A 0.8395-approximation algorithm for the EPR problem", arXiv:2512.09896, (2025).

[6] Vincenzo Lipardi, David Mestel, and Georgios Stamoulis, "Product-State Approximation Algorithms for the Transverse Field Ising Model", arXiv:2601.13106, (2026).

[7] Ainesh Bakshi, Arpon Basu, Pravesh Kothari, and Anqi Li, "Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut", arXiv:2605.14994, (2026).

The above citations are from SAO/NASA ADS (last updated successfully 2026-08-09 22:19:58). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2026-08-09 22:19:57).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.