Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2410.15544 · Quantum

Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians

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

Published Apr 28, 2026• 0 citations
arXivHTMLPDF

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 + Θ ( 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 ≤ 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 \cite{parekh_optimal_2022}, which gave an approximation ratio of 1 / 2 .

DOI
10.22331/q-2026-04-28-2088

Related papers

Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems.

Ojas Parekh, Kevin Thompson

The quantum k-Local Hamiltonian problem is a natural generalization of classical constraint satisfaction problems (k-CSP) and is complete for QMA, a quantum analog of NP. Although the complexity of k-Local Hamiltonian problems has been well studied, only a handful of approximation results are known. For Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural quantum generalization of classical Max 2-SAT, the best known approximation algorithm was the trivial random assignment, yielding a 0.75-approximation. We present the first approximation algorithm beating this bound, a classical polynomial-time 0.764-approximation. For strictly quadratic instances, which are maximally entangled instances, we provide a 0.801 approximation algorithm, and numerically demonstrate that our algorithm is likely a 0.821-approximation. We conjecture these are the hardest instances to approximate. We also give improved approximations for quantum generalizations of other related classical 2-CSPs. Finally, we exploit quantum connections to a generalization of the Grothendieck problem to obtain a classical constant-factor approximation for the physically relevant special case of strictly quadratic traceless 2-Local Hamiltonians on bipartite interaction graphs, where a inverse logarithmic approximation was the best previously known (for general interaction graphs). Our work employs recently developed techniques for analyzing classical approximations of CSPs and is intended to be accessible to both quantum information scientists and classical computer scientists.

arXiv:2012.12347•Leibniz international proceedings in informatics•Aug 1, 2021•5 citations

An Improved Quantum Max Cut Approximation via Maximum Matching

Eunou Lee, Ojas Parekh

Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Eunou Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.

Leibniz international proceedings in informatics•Jan 1, 2024•0 citations

A 0.8395-approximation algorithm for the EPR problem

Anuj Apte, Eunou Lee, Kunal Marwaha +3 more

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.

quant-pharXiv:2512.09896•Leibniz international proceedings in informatics•Dec 11, 2025•0 citations

An improved Quantum Max Cut approximation via matching

Eunou Lee, Parekh, Ojas

Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.

arXiv:2401.03616•Jan 8, 2024•0 citations

Approximation Algorithms for Quantum Max-ddd-Cut

Charlie Carlson, Zackary Jorquera, Alexandra Kolla +2 more

We initiate the algorithmic study of the Quantum Max-$d$-Cut problem, a quantum generalization of the well-known Max-$d$-Cut problem. The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions. Equivalently, this problem is physically motivated by the $SU(d)$-Heisenberg model, a spin glass model that generalized the well-known Heisenberg model over qudits. We develop a polynomial-time randomized approximation algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees. Moreover, we prove the tightness of our analysis by presenting an algorithmic gap instance for Quantum Max-d-Cut problem with $d \geq 3$.

arXiv:2309.10957•Sep 19, 2023•0 citations

An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms

Ojas Parekh, Thompson, Kevin

We resolve the approximability of the maximum energy of the Quantum Max Cut (QMC) problem using product states. A classical 0.498-approximation, using a basic semidefinite programming relaxation, is known for QMC, paralleling the celebrated 0.878-approximation for classical Max Cut. For Max Cut, improving the 0.878-approximation is Unique-Games-hard (UG-hard), and one might expect that improving the 0.498-approximation is UG-hard for QMC. In contrast, we give a classical 1/2-approximation for QMC that is unconditionally optimal, since simple examples exhibit a gap of 1/2 between the energies of an optimal product state and general quantum state. Our result relies on a new nonlinear monogamy of entanglement inequality on a triangle that is derived from the second level of the quantum Lasserre hierarchy. This inequality also applies to the quantum Heisenberg model, and our results generalize to instances of Max 2-Local Hamiltonian where each term is positive and has no 1-local parts. Finally, we give further evidence that product states are essential for approximations of 2-Local Hamiltonian.

arXiv:2206.08342•Jun 16, 2022•6 citations
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 + Θ ( 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 ≤ 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 \cite{parekh_optimal_2022}, which gave an approximation ratio of 1 / 2 .
The quantum k-Local Hamiltonian problem is a natural generalization of classical constraint satisfaction problems (k-CSP) and is complete for QMA, a quantum analog of NP. Although the complexity of k-Local Hamiltonian problems has been well studied, only a handful of approximation results are known. For Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural quantum generalization of classical Max 2-SAT, the best known approximation algorithm was the trivial random assignment, yielding a 0.75-approximation. We present the first approximation algorithm beating this bound, a classical polynomial-time 0.764-approximation. For strictly quadratic instances, which are maximally entangled instances, we provide a 0.801 approximation algorithm, and numerically demonstrate that our algorithm is likely a 0.821-approximation. We conjecture these are the hardest instances to approximate. We also give improved approximations for quantum generalizations of other related classical 2-CSPs. Finally, we exploit quantum connections to a generalization of the Grothendieck problem to obtain a classical constant-factor approximation for the physically relevant special case of strictly quadratic traceless 2-Local Hamiltonians on bipartite interaction graphs, where a inverse logarithmic approximation was the best previously known (for general interaction graphs). Our work employs recently developed techniques for analyzing classical approximations of CSPs and is intended to be accessible to both quantum information scientists and classical computer scientists.
Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Eunou Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.
Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.
We initiate the algorithmic study of the Quantum Max-ddd-Cut problem, a quantum generalization of the well-known Max-ddd-Cut problem. The Quantum Max-ddd-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, ddd-dimensional qudits over all local interactions. Equivalently, this problem is physically motivated by the SU(d)SU(d)SU(d)-Heisenberg model, a spin glass model that generalized the well-known Heisenberg model over qudits. We develop a polynomial-time randomized approximation algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees. Moreover, we prove the tightness of our analysis by presenting an algorithmic gap instance for Quantum Max-d-Cut problem with d≥3d \geq 3d≥3.
We resolve the approximability of the maximum energy of the Quantum Max Cut (QMC) problem using product states. A classical 0.498-approximation, using a basic semidefinite programming relaxation, is known for QMC, paralleling the celebrated 0.878-approximation for classical Max Cut. For Max Cut, improving the 0.878-approximation is Unique-Games-hard (UG-hard), and one might expect that improving the 0.498-approximation is UG-hard for QMC. In contrast, we give a classical 1/2-approximation for QMC that is unconditionally optimal, since simple examples exhibit a gap of 1/2 between the energies of an optimal product state and general quantum state. Our result relies on a new nonlinear monogamy of entanglement inequality on a triangle that is derived from the second level of the quantum Lasserre hierarchy. This inequality also applies to the quantum Heisenberg model, and our results generalize to instances of Max 2-Local Hamiltonian where each term is positive and has no 1-local parts. Finally, we give further evidence that product states are essential for approximations of 2-Local Hamiltonian.