Improved Approximation Algorithms for the EPR Hamiltonian

Ju, Nathan; Nagda, Ansh

doi:10.4230/LIPIcs.APPROX/RANDOM.2025.24

Improved Approximation Algorithms for the EPR Hamiltonian

Nathan Ju

UC Berkeley, CA, USA Ansh Nagda

UC Berkeley, CA, USA

Abstract

The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King [18]. We introduce a polynomial time $\frac{1+\sqrt{5}}{4}\approx 0.809$ -approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian, improving upon the previous state of the art of $0.72$ [17].

Keywords and phrases:

Approximation Algorithms, Quantum Local Hamiltonian

Category:

APPROX

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Approximation algorithms analysis

Supplementary Material:

Software (Source code): https://github.com/anshnagda/EPR-algorithm
archived at

swh:1:dir:0c84d61b32f7cc919be9311c24e8136b0e3412f1

DOI:

10.4230/LIPIcs.APPROX/RANDOM.2025.24

Event:

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Editors:

Alina Ene and Eshan Chattopadhyay

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Constraint Satisfaction Problems (CSPs) are a central class of computational problems in NP, capturing a wide range of decision problems where the goal is to determine whether there exists an assignment to variables that satisfies a given set of constraints. In the quantum setting, the analogous problem is known as the local Hamiltonian problem which is the central computational problem for the complexity class QMA. In this problem, one is given a local Hamiltonian of the form

H=\sum_{i\in[m]}h_{i},

where each term $h_{i}\in\mathbb{C}^{2^{n}\times 2^{n}}$ is a Hermitian matrix over $n$ qubits that only acts nontrivially on $O(1)$ qubits. Given a (mixed) quantum state $\rho$ , we say that the energy of $\rho$ is $\tr(\rho\cdot H)$ . In the maximization version of the problem, the objective is to compute the maximum possible energy achieved by any state, which we call the ground state energy¹¹1This is a slight deviation from the usual notion of the ground state being the minimum energy state. We remark that both the notions are equivalent up to replacing $H$ by $-H$ ; we use the maximization notion because it is notationally convenient.. Note that the ground state energy coincides with the maximum eigenvalue of $H$ :

\lambda_{\max}(H)=\max_{\rho\geq 0,\tr(\rho)=1}\tr(\rho\cdot H).

We remark that max-CSPs can be thought of as a special case of the local Hamiltonian problem where $h_{i}$ is a diagonal $2^{n}\times 2^{n}$ matrix whose $(x,x)$ entry indicates whether or not a particular predicate is satisfied by $x$ viewed as an assignment of $n$ Boolean variables. In this case, it is immediate that the ground state energy is equal to the maximum number of clauses that can be satisfied by any assignment, and is achieved by the product state $\outerproduct{x^{*}}{x^{*}}$ where $x^{*}$ is the optimal assignment.

Computing the ground state energy of a generic local Hamiltonians is computationally infeasible (QMA-hard), so we focus on approximating it in this work. Let $\mathcal{F}$ be a family of local Hamiltonians. For $\alpha\in[0,1]$ , an $\alpha$ -approximation algorithm for $\mathcal{F}$ is a classical algorithm²²2For the purposes of this paper we only consider classical algorithms, but one can also consider quantum algorithms. that, upon input $H\in\mathcal{F}$ , outputs a description of a (mixed) state $\rho$ achieving energy

\tr(\rho\cdot H)\geq\alpha\cdot\lambda_{\max}(H).

In this work, we consider the EPR Hamiltonian family $\mathcal{F}=\text{EPR}$ which was formally introduced by King [18]. A Hamiltonian $H\in\text{EPR}$ is parametrized by a weighted graph given as a symmetric matrix $w\in{\mathbb{R}}_{\geq 0}^{n\times n}$ , and is defined as

H=\sum_{i<j\in[n]}w_{ij}E_{ij},

where $E_{ij}$ is a projection onto the EPR state $\ket{\operatorname{EPR}}=\frac{\ket{00}+\ket{11}}{\sqrt{2}}$ on qubits $i$ and $j$ tensored with identity on the rest.

These Hamiltonians naturally arise in the study of quantum systems such as the antiferromagnetic Heisenberg model on lattices and the XXZ model, which have been extensively studied in the physics literature (e.g. [25, 7, 21, 5]).

From the point of view of computational complexity, the EPR Hamiltonian provides perhaps the simplest example of a local Hamiltonian that exhibits new challenges beyond traditional CSP theory. To illustrate this, one can show that among all product states, the one achieving maximal energy is always the trivial state $\rho=\outerproduct{0^{n}}{0^{n}}$ . This is in contrast to the “diagonal” case of CSPs in which the optimal state is equivalent to the optimal product state. As a result, the main challenge with the EPR Hamiltonian reduces to understanding the entanglement structure of the ground state.

Prior to our work, King [18] obtained a $1/\sqrt{2}$ -approximation for the EPR Hamiltonian, which was later slightly improved to $0.72$ [17]. Our main result is an improved approximation algorithm for EPR.

Theorem 1.

There is a polynomial time $\frac{1+\sqrt{5}}{4}\approx 0.809$ -approximation algorithm for the EPR problem.

$\blacktriangleright$ Remark 2.

In concurrent work, Apte et al. [3] achieved the same approximation ratio of $\frac{1+\sqrt{5}}{4}$ for the EPR Hamiltonian using a different algorithm and analysis.

1.1 Related work

The study of approximation algorithms for local Hamiltonian problems was initiated by Bravyi, Bansal, and Terhal [4] and Gharibian and Kempe [11] which have since been followed by a sequence of works (e.g. [9, 8, 14, 6]).

A line of work initiated by Gharibian and Parekh [12] studies approximation algorithms for a closely related problem to the EPR Hamiltonian, called Quantum Max Cut [23, 1, 24, 19, 18, 15, 28, 26]. The best known results in the literature are an algorithm showing an approximation ratio of $0.611$ [3] and a (conditional) hardness result ruling out approximation ratios beyond $0.956$ [16]. This leaves a large range of possible values for the optimal approximability by polynomial time algorithms.

For bipartite instances of the EPR Hamiltonian where one part has $O(1)$ vertices, Takahashi et al. [27] devised a polynomial time approximation scheme (PTAS). For general bipartite instances of the EPR Hamiltonian, [13] devised a $0.816$ -approximation algorithm.

2 Algorithm

2.1 An upper bound on $\lambda_{\max}(H)$

We will begin by describing an efficiently computable upper bound on $\lambda_{\max}(H)$ . Let us denote by $\textup{LP}(w)$ the optimal value of the following linear program, known as the fractional matching LP:

	$\displaystyle\max$	$\displaystyle\sum_{i<j}w_{ij}\cdot x_{ij}$
	$\displaystyle\text{s.t.}\ \sum_{j\neq i}x_{ij}$	$\displaystyle\leq 1\quad\text{for all $i\in[n]$}$
	$\displaystyle x_{ij}$	$\displaystyle\geq 0\quad\text{for all }i,j\in[n]$

Let $x=(x_{ij})_{i<j}$ be an optimal solution to the above LP. We say that the LP energy on edge $\{i,j\}$ is $\tilde{E}_{ij}=\frac{1+x_{ij}}{2}$ .

The star bound, proved by Anshu-Gosset-Morenz [1], gives a way to bound the ground state energy $\lambda_{\max}(H)$ in terms of the above linear program. We will need a version of this bound that applies to the EPR Hamiltonian (appearing in [18, Lemma 7] for example).

Lemma 3.

For any $n$ -qubit state $\rho$ and $i\in[n]$ ,

\sum_{j\neq i}\max(0,2\tr(\rho\cdot E_{ij})-1)\leq 1.

As a consequence, $\{\max(0,2\tr(\rho\cdot E_{ij})-1)\}_{i<j}$ always gives a feasible solution to the LP, implying that $\sum_{i<j}w_{ij}\max(0,2\tr(\rho\cdot E_{ij})-1)\leq\textup{LP}(w)$ . This implies the upper bound

\lambda_{\max}(H)=\max_{\rho\succeq 0,\tr(\rho)=1}\tr(\rho\cdot H)\leq\frac{% \sum_{i<j}w_{ij}+\textup{LP}(w)}{2}=\sum_{i<j}w_{ij}\tilde{E}_{ij}.

(1)

All the algorithms we present in this paper involve computing an optimal solution $x$ to $\textup{LP}(w)$ , and applying a rounding algorithm to $x$ to compute the description of a state $\rho$ achieving energy

\tr(\rho\cdot E_{ij})\geq\alpha\cdot\tilde{E}_{ij}

(2)

on every edge $\{i,j\}\in\binom{[n]}{2}$ for some $\alpha>0$ . By Equation 1, we have

\tr(\rho\cdot H)=\sum_{i<j}w_{ij}\cdot\tr(\rho\cdot E_{ij})\geq\alpha\cdot\sum% _{i<j}w_{ij}\tilde{E}_{ij}\geq\alpha\cdot\lambda_{\max}(H),

so this results in an $\alpha$ -approximation algorithm.

Let us describe the rough plan for our presentation of this rounding algorithm. First, in Section 2.2, we describe how to use a rounding strategy used in the work of Lee and Parekh [20] to achieve $\alpha=3/4$ in the special case that the interaction matrix $w$ is bipartite, that is, it is the adjacency matrix of a bipartite weighted graph. Next, in Section 2.3 we give an improved rounding algorithm achieving $\alpha=\frac{1+\sqrt{5}}{4}$ for bipartite instances. Finally, in Section 2.4 we show how to achieve the same approximation ratio $\alpha=\frac{1+\sqrt{5}}{4}$ for general non-bipartite instances, proving Theorem 1.

2.2 A $3/4$ -approximation in the bipartite case

Here we focus on the case that $w$ is the adjacency matrix of a weighted bipartite graph. For bipartite graphs, it was proved by Edmonds that the fractional matching LP is integral, i.e., its vertices are indicator vectors of matchings.

Lemma 4 ([10]).

For any weighted bipartite graph with adjacency matrix $w$ , $\textup{LP}(w)=w(M)$ , where $M$ is the maximum weight matching of the graph. That is, the optimal solution to $\textup{LP}(w)$ is achieved by an integer vector $x_{ij}=\mathbf{1}_{\{\{i,j\}\in M\}}$ .

We can find such an optimal solution using an algorithm for maximum weighted matching. Let $U\subseteq[n]$ be the set of vertices that do not appear in the matching $M$ . Consider the two states

\rho_{\text{prod}}=\outerproduct{0^{n}}{0^{n}},\quad\rho_{\text{match}}=\left(% \bigotimes_{\{i,j\}\in M}(\outerproduct{\operatorname{EPR}}{\operatorname{EPR}% })_{i,j}\right)\otimes\left(\bigotimes_{i\in U}\frac{I_{i}}{2}\right).

The rounding algorithm will output a random choice between $\rho_{\text{prod}}$ and $\rho_{\text{match}}$ . In particular, we output the state $\rho=(1-p)\cdot\rho_{\text{prod}}+p\cdot\rho_{\text{match}}$ for some choice of $p\in[0,1]$ .

Claim 5.

The energy attained on edge $\{i,j\}$ is

\tr(\rho\cdot E_{ij})=\begin{cases}\frac{1}{2}+\frac{p}{2}&\text{ if }\{i,j\}% \in M,\\ \frac{1}{2}-\frac{p}{4}\quad&\text{ if }\{i,j\}\notin M.\end{cases}

On the other hand, the LP energy on edge $\{i,j\}$ is

\tilde{E}_{ij}=\frac{1+x_{ij}}{2}=\begin{cases}1&\text{ if }\{i,j\}\in M,\\ \frac{1}{2}\quad&\text{ if }\{i,j\}\notin M.\end{cases}

If we set $p=1/2$ , then one can check that for each edge $\{i,j\}$ ,

\tr(\rho\cdot E_{ij})=\frac{3}{4}\tilde{E}_{ij},

proving Equation 2 for $\alpha=\frac{3}{4}$ .

2.3 An improvement in the bipartite case

Our improvement to this algorithm is simple to state – we interpolate between $\rho_{\text{prod}}$ and $\rho_{\text{match}}$ using quantum superposition rather than in probability. Concretely, let $M$ be the maximum matching and $U$ be the unmatched vertices as in Section 2.2. Define the tilted EPR state $\ket{\operatorname{EPR}_{\theta}}:=\sqrt{\theta}\ket{00}+\sqrt{1-\theta}\ket{11}$ . We will output the state

\rho=\left(\bigotimes_{\{i,j\}\in M}(\outerproduct{\operatorname{EPR}_{\theta}% }{\operatorname{EPR}_{\theta}})_{i,j}\right)\otimes\left(\bigotimes_{i\in U}% \left(\theta\outerproduct{0}{0}+(1-\theta)\outerproduct{1}{1}\right)_{i}\right).

(3)

Claim 6.

The energy attained on edge $\{i,j\}$ is

\tr(\rho\cdot E_{ij})=\begin{cases}\frac{1}{2}+\sqrt{\theta(1-\theta)}=\frac{1% }{2}+\gamma\quad&\text{ if }\{i,j\}\in M,\\ \frac{1}{2}-\theta(1-\theta)=\frac{1}{2}-\gamma^{2}\quad&\text{ if }\{i,j\}% \notin M,\end{cases}

where $\gamma=\sqrt{\theta(1-\theta)}$ .

Comparing Claim 6 to Claim 5, one can readily see that this algorithm performs strictly better; for instance, set $\gamma=p/2$ . Our new rounding scheme achieves strictly better energy on edges outside $M$ and identical energy on edges inside $M$ .

It remains to prove Claim 6, and then to analyze the approximation ratio of this rounding algorithm. We will repeatedly use the following simple properties of $\ket{\operatorname{EPR}_{\theta}}$ .

Claim 7.

Let $\gamma=\sqrt{\theta(1-\theta)}$ . The following are true.

1.

$\absolutevalue{\innerproduct{\operatorname{EPR}|\operatorname{EPR}_{\theta}}{% \operatorname{EPR}|\operatorname{EPR}_{\theta}}}^{2}=\frac{1}{2}+\gamma$ .
2.

$\tr_{[1]}\outerproduct{\operatorname{EPR}_{\theta}}{\operatorname{EPR}_{\theta% }}=\tr_{[2]}\outerproduct{\operatorname{EPR}_{\theta}}{\operatorname{EPR}_{% \theta}}=\theta\outerproduct{0}{0}+(1-\theta)\outerproduct{1}{1}$ .
3.

$\bra{\operatorname{EPR}}\left(\theta\outerproduct{0}{0}+(1-\theta)% \outerproduct{1}{1}\right)^{\otimes 2}\ket{\operatorname{EPR}}=\frac{1}{2}-% \gamma^{2}$ .

Now, one can compute all the 2-qubit marginals:

\tr_{[n]\setminus\{i,j\}}(\rho)=\begin{cases}\outerproduct{\operatorname{EPR}_% {\theta}}{\operatorname{EPR}_{\theta}}\quad&\text{ if }\{i,j\}\in M,\\ \left(\theta\outerproduct{0}{0}+(1-\theta)\outerproduct{1}{1}\right)^{\otimes 2% }\quad&\text{ if }\{i,j\}\notin M,\end{cases}

where for the second case we used that the $1$ -qubit marginals are all equal to $\tr_{[n]\setminus\{1\}}[\outerproduct{\operatorname{EPR}_{\theta}}{% \operatorname{EPR}_{\theta}}]=\theta\outerproduct{0}{0}+(1-\theta)% \outerproduct{1}{1}$ . By Claim 7, the energy achieved by each term $\{i,j\}$ is determined by

\bra{\operatorname{EPR}}\tr_{[n]\setminus\{i,j\}}(\rho)\ket{\operatorname{EPR}% }=\begin{cases}\frac{1}{2}+\sqrt{\theta(1-\theta)}=\frac{1}{2}+\gamma\quad&% \text{ if }\{i,j\}\in M,\\ \frac{1}{2}-\theta(1-\theta)=\frac{1}{2}-\gamma^{2}\quad&\text{ if }\{i,j\}% \notin M,\end{cases}

and Claim 6 follows immediately. Now let us analyze the approximation ratio. Similarly to Section 2.2, we have the LP energy

\tilde{E}_{ij}=\begin{cases}1&\text{ if }\{i,j\}\in M,\\ \frac{1}{2}\quad&\text{ if }\{i,j\}\notin M.\end{cases}

(4)

Setting $\gamma=\frac{\sqrt{5}-1}{4}$ , one can check using Equation 4 and Claim 6 that

\tr(\rho\cdot E_{ij})=\frac{1+\sqrt{5}}{4}\cdot\tilde{E}_{ij}

for each edge $\{i,j\}\in\binom{[n]}{2}$ . Thus, we have shown Equation 2 with $\alpha=\frac{1+\sqrt{5}}{4}$ as desired.

2.4 General Case

In the general non-bipartite case, we cannot apply Lemma 4; the fractional matching LP is not necessarily integral. Previous works proceeded by bounding the integrality gap of this LP, which is quite lossy. Our main idea is to take advantage of the fact that the fractional matching LP is half-integral.

Lemma 8 ([22, Theorem 7.5.1]).

For any weighted $n$ -vertex graph with adjacency matrix $w$ , there is a vertex-disjoint collection of edges $M\subset\binom{[n]}{2}$ and cycles $\mathcal{C}\subset 2^{\binom{[n]}{2}}$ such that $\textup{LP}(w)=w(M)+\frac{1}{2}\sum_{C\in\mathcal{C}}w(C)$ . That is, the optimal solution to $\textup{LP}(w)$ is achieved by the half-integer vector $x_{ij}=\mathbf{1}_{\{\{i,j\}\in M\}}+\frac{1}{2}\sum_{C\in\mathcal{C}}\mathbf{% 1}_{\{\{i,j\}\in C\}}$ .

In particular, (e.g. using the algorithm of Anstee [2]), one can efficiently find such a solution $x$ , i.e. a vertex-disjoint collection of edges $M\subset\binom{[n]}{2}$ and odd length cycles $\mathcal{C}$ such that the LP energies can be written as

\tilde{E}_{ij}=\frac{1+x_{ij}}{2}=\begin{cases}1\quad&\text{ if }\{i,j\}\in M,% \\ \frac{3}{4}\quad&\text{ if }\{i,j\}\in C\text{ for some }C\in\mathcal{C},\\ \frac{1}{2}\quad&\text{ otherwise }.\end{cases}

(5)

Let $U$ be the set of vertices absent from $M$ and $\mathcal{C}$ . The algorithm in the bipartite case (Equation 3) already suggests what quantum state we will output on the qubits involved in $M$ and $U$ . On the qubits in $C$ for some odd cycle $C\in\mathcal{C}$ of length $k$ , we will output a high energy state for the EPR Hamiltonian on the length $k$ cycle, i.e. $H_{\text{cycle}}=\sum_{i\in[k]}E_{i,i+1(\text{mod }k)}$ , subject to the constraint that all $1$ -qubit marginals are equal to $\theta\outerproduct{0}{0}+(1-\theta)\outerproduct{1}{1}$ . The following lemma (which we prove in Appendix A) shows that there is a way to achieve sufficiently large energy on the cycle edges.

Lemma 9.

For any integer $k$ , there is an efficient algorithm to compute the description of a $k$ -qubit state $\rho_{k}$ satisfying the following, where $\gamma=\frac{\sqrt{5}-1}{4}$ and $\theta\geq 1/2$ is the solution to $\sqrt{\theta(1-\theta)}=\gamma$ .

1.

For all $i\in[k]$ , $\tr(\rho_{k}\cdot E_{i,i+1(\textup{mod k})})>\frac{3}{4}\cdot\frac{1+\sqrt{5}}% {4}$ .
2.

For all $i\in[k]$ , the $1$ -qubit marginal $\tr_{[k]-i}[\rho_{k}]$ equals $\theta\outerproduct{0}{0}+(1-\theta)\outerproduct{1}{1}$ .
3.

For all $i,j\in[k]$ , $\tr(\rho_{k}\cdot E_{ij})>\frac{1}{2}\cdot\frac{1+\sqrt{5}}{4}$ .

$\blacktriangleright$ Remark 10.

The main idea behind the proof is that Items 1, 2, and 3 are all linear constraints in the positive semidefinite variable $\rho_{k}$ , and hence the Lemma reduces to solving a semidefinite program of size $2^{O(k)}$ . This can be verified numerically for $k$ small enough. When $k$ is large, we instead choose $\rho_{k}$ to be a tensor product of states on a disjoint collection of short paths; here the states on short paths are again found by numerically solving an appropriate semidefinite program.

The bounds in Lemma 9 are not tight – our numerical proof already shows that Items 1, 2, and 3 can be simultaneously improved. However, for ease of exposition we have chosen to write the weakest bounds that suffice to attain the required approximation ratio.

Our algorithm will output the state

\rho=\left(\bigotimes_{C\in\mathcal{C}}(\rho_{|C|})_{V(C)}\right)\otimes\left(% \bigotimes_{\{i,j\}\in M}(\outerproduct{\operatorname{EPR}_{\theta}}{% \operatorname{EPR}_{\theta}})_{i,j}\right)\otimes\left(\bigotimes_{i\in U}% \left(\theta\outerproduct{0}{0}+(1-\theta)\outerproduct{1}{1}\right)_{i}\right),

(6)

where $V(C)\subseteq[n]$ is the set of qubits in the cycle $C$ and $\rho_{|C|}$ is the state guaranteed by Lemma 9. Similarly to Section 2.3, we set $\gamma=\frac{\sqrt{5}-1}{4}$ and $\theta\geq 1/2$ such that $\sqrt{\theta(1-\theta)}=\gamma$ . Let us analyze the energy achieved by this algorithm. We have

\tr(\rho\cdot E_{ij})\geq\begin{cases}\frac{1+\sqrt{5}}{4}\quad&\text{ if }\{i% ,j\}\in M,\hfill(\lx@cref{creftype~refnum}{claim:bip-energy})\\ \frac{3}{4}\cdot\frac{1+\sqrt{5}}{4}\quad&\text{ if }\{i,j\}\in C\text{ for % some }C\in\mathcal{C},\hfill\qquad\qquad\qquad\qquad(\lx@cref{creftype~refnum}% {lem:cycle-state},\lx@cref{creftype~refnum}{item:1})\\ \frac{1}{2}\cdot\frac{1+\sqrt{5}}{4}\quad&\text{ otherwise}.\hfill(\text{1-% qubit marginals, }\lx@cref{creftype~refnum}{lem:cycle-state},\lx@cref{% creftype~refnum}{item:3})\end{cases}

To elaborate on the last case, we note that it must be that either qubits $i$ and $j$ are nonadjacent vertices in the same cycle $C\in\mathcal{C}$ , or they are in tensor product. If the former is true, we use the guarantee of Lemma 9, Item 3. Otherwise, we use the fact that all the $1$ -qubit marginals are equal to $\theta\outerproduct{0}{0}+(1-\theta)\outerproduct{1}{1}$ along with the calculations from Section 2.3 to conclude that the energy is $\frac{1}{2}-\gamma^{2}=\frac{1+\sqrt{5}}{8}$ .

Comparing with Equation 5, we immediately get that for every edge $\{i,j\}\in\binom{[n]}{2}$ ,

\tr(\rho\cdot E_{ij})\geq\frac{1+\sqrt{5}}{4}\tilde{E}_{ij},

proving Equation 2 with $\alpha=\frac{1+\sqrt{5}}{4}$ . As a result, we obtain an approximation algorithm for the EPR Hamiltonian with approximation ratio $\frac{1+\sqrt{5}}{4}$ , proving Theorem 1.

References

[1] Anurag Anshu, David Gosset, and Karen Morenz. Beyond product state approximations for a quantum analogue of max cut. arXiv preprint, 2020. arXiv:2003.14394.
[2] Richard P Anstee. A polynomial algorithm for b-matchings: an alternative approach. Information Processing Letters, 24(3):153–157, 1987. doi:10.1016/0020-0190(87)90178-5.
[3] Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud. Improved algorithms for quantum maxcut via partially entangled matchings. arXiv preprint, 2025. arXiv:2504.15276.
[4] Nikhil Bansal, Sergey Bravyi, and Barbara M Terhal. Classical approximation schemes for the ground-state energy of quantum and classical ising spin hamiltonians on planar graphs. arXiv preprint, 2007. arXiv:0705.1115.
[5] Rodney J Baxter. Partition function of the eight-vertex lattice model. Annals of Physics, 70(1):193–228, 1972.
[6] Thiago Bergamaschi. Improved product-state approximation algorithms for quantum local hamiltonians. arXiv preprint, 2022. arXiv:2210.08680.
[7] Hans Bethe. Zur theorie der metalle: I. eigenwerte und eigenfunktionen der linearen atomkette. Zeitschrift für Physik, 71(3):205–226, 1931.
[8] Fernando GSL Brandao and Aram W Harrow. Product-state approximations to quantum states. Communications in Mathematical Physics, 342:47–80, 2016.
[9] Sergey Bravyi, David Gosset, Robert König, and Kristan Temme. Approximation algorithms for quantum many-body problems. Journal of Mathematical Physics, 60(3), 2019.
[10] Jack Edmonds. Maximum matching and a polyhedron with 0, 1-vertices. Journal of research of the National Bureau of Standards B, 69(125-130):55–56, 1965.
[11] Sevag Gharibian and Julia Kempe. Approximation algorithms for qma-complete problems. SIAM Journal on Computing, 41(4):1028–1050, 2012. doi:10.1137/110842272.
[12] Sevag Gharibian and Ojas Parekh. Almost optimal classical approximation algorithms for a quantum generalization of max-cut. arXiv preprint, 2019. arXiv:1909.08846.
[13] Sander Gribling, Lennart Sinjorgo, and Renata Sotirov. Improved approximation ratios for the quantum max-cut problem on general, triangle-free and bipartite graphs. arXiv preprint, 2025. arXiv:2504.11120.
[14] Aram W Harrow and Ashley Montanaro. Extremal eigenvalues of local hamiltonians. Quantum, 1:6, 2017. doi:10.22331/Q-2017-04-25-6.
[15] Felix Huber, Kevin Thompson, Ojas Parekh, and Sevag Gharibian. Second order cone relaxations for quantum max cut, 2024. arXiv:2411.04120.
[16] Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, and John Wright. Unique games hardness of quantum max-cut, and a conjectured vector-valued borell’s inequality. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1319–1384. SIAM, 2023. doi:10.1137/1.9781611977554.CH48.
[17] Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, Juspreet Singh Sandhu, and Stuart Wayland. Monogamy of entanglement bounds and improved approximation algorithms for qudit hamiltonians. arXiv preprint, 2024. arXiv:2410.15544.
[18] Robbie King. An improved approximation algorithm for quantum max-cut on triangle-free graphs. Quantum, 7:1180, 2023. doi:10.22331/Q-2023-11-09-1180.
[19] Eunou Lee. Optimizing quantum circuit parameters via sdp, 2022. arXiv:2209.00789.
[20] Eunou Lee and Ojas Parekh. An Improved Quantum Max Cut Approximation via Maximum Matching. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 105:1–105:11, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2024.105.
[21] Elliott Lieb, Theodore Schultz, and Daniel Mattis. Two soluble models of an antiferromagnetic chain. Annals of Physics, 16(3):407–466, 1961.
[22] László Lovász and Michael D Plummer. Matching theory, volume 367. American Mathematical Soc., 2009.
[23] Ojas Parekh and Kevin Thompson. Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 102:1–102:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2021.102.
[24] Ojas Parekh and Kevin Thompson. An optimal product-state approximation for 2-local quantum hamiltonians with positive terms. arXiv preprint, 2022. doi:10.48550/arXiv.2206.08342.
[25] Anders W Sandvik. Computational studies of quantum spin systems. In AIP Conference Proceedings, volume 1297, pages 135–338. American Institute of Physics, 2010.
[26] 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.
[27] Jun Takahashi, Sam Slezak, and Elizabeth Crosson. Rapidly mixing loop representation quantum monte carlo for heisenberg models on star-like bipartite graphs, 2024. doi:10.48550/arXiv.2411.01452.
[28] 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, May 2024. doi:10.22331/Q-2024-05-22-1352.

Appendix A Proof of Lemma 9

For the reader’s convenience we restate Lemma 9 below. The code for verifying the numerical claims made in the below proof is available at https://github.com/anshnagda/EPR-algorithm.

Lemma 11 (Restatement of Lemma 9).

For any integer $k$ , there is an efficient algorithm to compute the description of a $k$ -qubit state $\rho_{k}$ satisfying the following, where $\gamma=\frac{\sqrt{5}-1}{4}$ and $\theta\geq 1/2$ is the solution to $\sqrt{\theta(1-\theta)}=\gamma$ .

1.

For all $i\in[k]$ , $\tr(\rho_{k}\cdot E_{i,i+1(\textup{mod k})})>\frac{3}{4}\cdot\frac{1+\sqrt{5}}% {4}$ .
2.

For all $i\in[k]$ , the $1$ -qubit marginal $\tr_{[k]-i}[\rho_{k}]$ equals $\theta\outerproduct{0}{0}+(1-\theta)\outerproduct{1}{1}$ .
3.

For all $i,j\in[k]$ , $\tr(\rho_{k}\cdot E_{ij})>\frac{1}{2}\cdot\frac{1+\sqrt{5}}{4}$ .

Proof.

For $k\leq 5$ , we numerically verify the claim by explicitly solving a semidefinite program.

Similarly, one can verify by solving a semidefinite program that there exists a $5$ -qubit state $\psi$ satisfying the following:

1.

$\frac{1}{4}\cdot\sum_{i\in[4]}\tr(E_{i,i+1}\cdot\psi)\geq 0.668$ .
2.

For all $i,j\in[5]$ , $\tr(E_{ij}\cdot\psi)>\frac{1}{2}\cdot\frac{1+\sqrt{5}}{4}$ .
3.

For all $i\in[5]$ , the $1$ -qubit marginal $\tr_{[5]-i}[\psi]$ equals $\theta\outerproduct{0}{0}+(1-\theta)\outerproduct{1}{1}$ .

Now assume $k\geq 7$ . Define the state

\rho^{\prime}_{k}=\outerproduct{\operatorname{EPR}_{\theta}}{\operatorname{EPR% }_{\theta}}^{\otimes\frac{k-5}{2}}\otimes\psi.

Let $\textsf{Shift}_{i}$ be the unitary that shifts qubits in the $k$ -cycle $i$ spots. We will set $\rho_{k}$ to be the shift-invariant state

\rho_{k}={\mathbb{E}}_{i\sim[k]}\left[\textsf{Shift}_{i}\cdot\rho^{\prime}_{k}% \cdot\textsf{Shift}_{i}^{\dagger}\right].

We will verify that $\rho_{k}$ satisfies the three requirements.

1.

Let $i\in[k]$ . We can write the energy $\tr(\rho_{k}\cdot E_{i,i+1(\textup{mod k})})$ as the average energy of a random edge $\{j,j+1(\text{mod }k)\}$ under $\rho^{\prime}_{k}$ . By definition of $\rho^{\prime}_{k}$ , one can compute

$\tr(\rho^{\prime}_{k}\cdot E_{j,j+1(\textup{mod k})})\geq\begin{cases}\frac{1+% \sqrt{5}}{4}\qquad&j\leq k-5\text{ odd},\\ \frac{1+\sqrt{5}}{8}\qquad&j\leq k-5\text{ even or }j=k.\end{cases}$

For the cases $k-5<j<k$ , the assumption on $\psi$ allows us to bound the energy as

$\sum_{k-5<j<k}\tr(\rho_{k}^{\prime}\cdot E_{j,j+1(\textup{mod k})})\geq 4\cdot 0% .668.$

Therefore

$\tr(\rho_{k}\cdot E_{i,i+1(\textup{mod k})})=\frac{\frac{k-5}{2}\cdot\frac{1+% \sqrt{5}}{4}+\frac{k-5}{2}\cdot\frac{1+\sqrt{5}}{8}+4\cdot 0.668+\frac{1+\sqrt% {5}}{8}}{k}.$

One can verify that $4\cdot 0.668+\frac{1+\sqrt{5}}{8}>5\cdot\frac{3}{4}\cdot\frac{1+\sqrt{5}}{4}$ , implying

$\tr(\rho\cdot E_{i,i+1(\textup{mod k})})>\frac{(k-5)\cdot\frac{3}{4}\cdot\frac% {1+\sqrt{5}}{4}+5\cdot\frac{3}{4}\cdot\frac{1+\sqrt{5}}{4}}{k}=\frac{3}{4}% \cdot\frac{1+\sqrt{5}}{4}.$
2.

It suffices to prove that the $1$ -qubit marginals of $\rho^{\prime}_{k}$ are equal to $\theta\outerproduct{0}{0}+(1-\theta)\outerproduct{1}{1}$ . For qubits $i\leq k-5$ , this follows from Claim 7, and for $i>k-4$ , this follows by definition of $\psi$ .
3.
Let $i\neq j$ . It suffices to prove $\tr(\rho^{\prime}_{k}\cdot E_{ij})>\frac{1}{2}\cdot\frac{1+\sqrt{5}}{4}$ the same for $\rho_{k}^{\prime}$ . We consider three cases.
- $\blacksquare$
  
  If $j=i+1$ for some odd $i\leq k-5$ , this is implied by Item 1.
- $\blacksquare$
  
  If $k-5<i,j\leq k$ , this is implied by the definition of $\psi$ .
- $\blacksquare$
  
  Otherwise, the 2-qubit marginal $\tr_{[n]\setminus\{i,j\}}(\rho^{\prime}_{k})$ equals $(\theta\outerproduct{0}{0}+(1-\theta)\outerproduct{1}{1})^{\otimes 2}$ , and this is implied by Claim 7.

$\hfill\blacktriangleleft$

[bib.bib1] [1] Anurag Anshu, David Gosset, and Karen Morenz. Beyond product state approximations for a quantum analogue of max cut. arXiv preprint, 2020. arXiv:2003.14394.

[bib.bib2] [2] Richard P Anstee. A polynomial algorithm for b-matchings: an alternative approach. Information Processing Letters, 24(3):153–157, 1987. doi:10.1016/0020-0190(87)90178-5.

[bib.bib3] [3] Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud. Improved algorithms for quantum maxcut via partially entangled matchings. arXiv preprint, 2025. arXiv:2504.15276.

[bib.bib4] [4] Nikhil Bansal, Sergey Bravyi, and Barbara M Terhal. Classical approximation schemes for the ground-state energy of quantum and classical ising spin hamiltonians on planar graphs. arXiv preprint, 2007. arXiv:0705.1115.

[bib.bib5] [5] Rodney J Baxter. Partition function of the eight-vertex lattice model. Annals of Physics, 70(1):193–228, 1972.

[bib.bib6] [6] Thiago Bergamaschi. Improved product-state approximation algorithms for quantum local hamiltonians. arXiv preprint, 2022. arXiv:2210.08680.

[bib.bib7] [7] Hans Bethe. Zur theorie der metalle: I. eigenwerte und eigenfunktionen der linearen atomkette. Zeitschrift für Physik, 71(3):205–226, 1931.

[bib.bib8] [8] Fernando GSL Brandao and Aram W Harrow. Product-state approximations to quantum states. Communications in Mathematical Physics, 342:47–80, 2016.

[bib.bib9] [9] Sergey Bravyi, David Gosset, Robert König, and Kristan Temme. Approximation algorithms for quantum many-body problems. Journal of Mathematical Physics, 60(3), 2019.

[bib.bib10] [10] Jack Edmonds. Maximum matching and a polyhedron with 0, 1-vertices. Journal of research of the National Bureau of Standards B, 69(125-130):55–56, 1965.

[bib.bib11] [11] Sevag Gharibian and Julia Kempe. Approximation algorithms for qma-complete problems. SIAM Journal on Computing, 41(4):1028–1050, 2012. doi:10.1137/110842272.

[bib.bib12] [12] Sevag Gharibian and Ojas Parekh. Almost optimal classical approximation algorithms for a quantum generalization of max-cut. arXiv preprint, 2019. arXiv:1909.08846.

[bib.bib13] [13] Sander Gribling, Lennart Sinjorgo, and Renata Sotirov. Improved approximation ratios for the quantum max-cut problem on general, triangle-free and bipartite graphs. arXiv preprint, 2025. arXiv:2504.11120.

[bib.bib14] [14] Aram W Harrow and Ashley Montanaro. Extremal eigenvalues of local hamiltonians. Quantum, 1:6, 2017. doi:10.22331/Q-2017-04-25-6.

[bib.bib15] [15] Felix Huber, Kevin Thompson, Ojas Parekh, and Sevag Gharibian. Second order cone relaxations for quantum max cut, 2024. arXiv:2411.04120.

[bib.bib16] [16] Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, and John Wright. Unique games hardness of quantum max-cut, and a conjectured vector-valued borell’s inequality. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1319–1384. SIAM, 2023. doi:10.1137/1.9781611977554.CH48.

[bib.bib17] [17] Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, Juspreet Singh Sandhu, and Stuart Wayland. Monogamy of entanglement bounds and improved approximation algorithms for qudit hamiltonians. arXiv preprint, 2024. arXiv:2410.15544.

[bib.bib18] [18] Robbie King. An improved approximation algorithm for quantum max-cut on triangle-free graphs. Quantum, 7:1180, 2023. doi:10.22331/Q-2023-11-09-1180.

[bib.bib19] [19] Eunou Lee. Optimizing quantum circuit parameters via sdp, 2022. arXiv:2209.00789.

[bib.bib20] [20] Eunou Lee and Ojas Parekh. An Improved Quantum Max Cut Approximation via Maximum Matching. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 105:1–105:11, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2024.105.

[bib.bib21] [21] Elliott Lieb, Theodore Schultz, and Daniel Mattis. Two soluble models of an antiferromagnetic chain. Annals of Physics, 16(3):407–466, 1961.

[bib.bib22] [22] László Lovász and Michael D Plummer. Matching theory, volume 367. American Mathematical Soc., 2009.

[bib.bib23] [23] Ojas Parekh and Kevin Thompson. Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 102:1–102:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2021.102.

[bib.bib24] [24] Ojas Parekh and Kevin Thompson. An optimal product-state approximation for 2-local quantum hamiltonians with positive terms. arXiv preprint, 2022. doi:10.48550/arXiv.2206.08342.

[bib.bib25] [25] Anders W Sandvik. Computational studies of quantum spin systems. In AIP Conference Proceedings, volume 1297, pages 135–338. American Institute of Physics, 2010.

[bib.bib26] [26] 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.

[bib.bib27] [27] Jun Takahashi, Sam Slezak, and Elizabeth Crosson. Rapidly mixing loop representation quantum monte carlo for heisenberg models on star-like bipartite graphs, 2024. doi:10.48550/arXiv.2411.01452.

[bib.bib28] [28] 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, May 2024. doi:10.22331/Q-2024-05-22-1352.

Improved Approximation Algorithms for the EPR Hamiltonian

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Supplementary Material:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1.

▶ Remark 2.

1.1 Related work

2 Algorithm

2.1 An upper bound on 𝝀𝐦𝐚𝐱⁢(𝑯)

Lemma 3.

2.2 A 𝟑/𝟒-approximation in the bipartite case

Lemma 4 ([10]).

Claim 5.

2.3 An improvement in the bipartite case

Claim 6.

Claim 7.

2.4 General Case

Lemma 8 ([22, Theorem 7.5.1]).

Lemma 9.

▶ Remark 10.

References

Appendix A Proof of Lemma 9

Lemma 11 (Restatement of Lemma 9).

Proof.

$\blacktriangleright$ Remark 2.

2.1 An upper bound on $\lambda_{\max}(H)$

2.2 A $3/4$ -approximation in the bipartite case

$\blacktriangleright$ Remark 10.