Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings

Apte, Anuj; Lee, Eunou; Marwaha, Kunal; Parekh, Ojas; Sud, James

doi:10.4230/LIPIcs.ESA.2025.101

Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings

Anuj Apte

University of Chicago, IL, USA Eunou Lee Korea Institute for Advanced Study, Seoul, South Korea Kunal Marwaha

University of Chicago, IL, USA Ojas Parekh

Sandia National Laboratories, Albuquerque, NM, USA James Sud

University of Chicago, IL, USA

Abstract

We introduce a $0.611$ -approximation algorithm for Quantum MaxCut and a $\frac{1+\sqrt{5}}{4}\approx 0.809$ -approximation algorithm for the EPR Hamiltonian of [12]. A novel ingredient in both of these algorithms is to partially entangle pairs of qubits associated to edges in a matching, while preserving the direction of their single-qubit Bloch vectors. This allows us to interpolate between product states and matching-based states with a tunable parameter.

Keywords and phrases:

Quantum computing, Quantum MaxCut, Maximum matching

Funding:

Eunou Lee: E.L is supported by a KIAS Individual Grant CG093801 at Korea Institute for Advanced Study.

Kunal Marwaha: K.M acknowledges support from AFOSR (FA9550-21-1-0008).

Ojas Parekh: O.P. acknowledges that this material is based upon work supported by the U.S. Department of Energy, Office of Science, Accelerated Research in Quantum Computing, Fundamental Algorithmic Research toward Quantum Utility (FAR-Qu).

James Sud: J.S acknowledges that this work is funded in part by the STAQ project under award NSF Phy-232580; in part by the US Department of Energy Office of Advanced Scientific Computing Research, Accelerated Research for Quantum Computing Program.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Approximation algorithms analysis

Related Version:

Full Version: https://arxiv.org/pdf/2504.15276 [2]

Acknowledgements:

This work is supported by a collaboration between the US DOE and other Agencies. The work of A.A is supported by the Data Science Institute at the University of Chicago. This article has been authored by an employee of National Technology & Engineering Solutions of Sandia, LLC under Contract No. DE-NA0003525 with the U.S. Department of Energy (DOE). The employee owns all right, title and interest in and to the article and is solely responsible for its contents. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this article or allow others to do so, for United States Government purposes. The DOE will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan https://www.energy.gov/downloads/doe-public-access-plan.

Funding:

K.M and J.S. acknowledge that this material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. 2140001.

DOI:

10.4230/LIPIcs.ESA.2025.101

Event:

33rd Annual European Symposium on Algorithms (ESA 2025)

Editors:

Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman

Series and Publisher:

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

1 Introduction

Given a graph $G(V,E,w)$ with positive edge weights $w:E\rightarrow\mathbb{R}_{+}$ and a $2$ -local Hamiltonian term $h$ , define the $n$ -qubit Hamiltonian

\displaystyle H_{G}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=% }}\sum_{(i,j)\in E(G)}w_{ij}\cdot h_{ij}\,,

where $h_{ij}$ is the local term $h$ applied on qubits $(i,j)$ . For two particular local terms $h$ , we are interested in the problem of computing the maximum energy of $H_{G}$ , which we denote as $\lambda_{max}(H_{G})$ , for any $G$ . This is not an easy task in general: deciding if $\lambda_{max}(H_{G})$ is above some threshold with inverse polynomial accuracy is known to be ${\mathsf{QMA}}$ -hard [18].

In the first problem, we choose the local term

\displaystyle h^{QMC}_{ij}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def% }}}{{=}}\frac{1}{2}\left(I_{i}I_{j}-X_{i}X_{j}-Y_{i}Y_{j}-Z_{i}Z_{j}\right)=2% \ket{\psi_{-}}_{ij}\bra{\psi_{-}}_{ij}\,,

where $\ket{\psi_{-}}=\frac{1}{\sqrt{2}}\left(\ket{01}-\ket{10}\right)$ is the singlet state. This problem has recently been studied under the name Quantum MaxCut (QMC) [7]. In the statistical mechanics literature, Hamiltonians $H_{G}$ defined by $h^{QMC}$ are instances of the zero-field quantum Heisenberg XXX_1/2 model. The decision version of QMC is ${\mathsf{QMA}}$ -hard [18].

In the second problem, we choose the local term

\displaystyle h^{EPR}_{ij}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def% }}}{{=}}\frac{1}{2}\left(I_{i}I_{j}+X_{i}X_{j}-Y_{i}Y_{j}+Z_{i}Z_{j}\right)=2% \ket{\phi_{+}}_{ij}\bra{\phi_{+}}_{ij}\,,

where $\ket{\phi_{+}}=\frac{1}{\sqrt{2}}\left(\ket{00}+\ket{11}\right)$ . This problem, named EPR by [12], is thought to be easier than QMC, since Hamiltonians $H_{G}$ defined by $h^{EPR}$ are stoquastic (sign-problem free) [18, 5]. In fact, it is not yet clear if EPR can be solved in polynomial time.

In lieu of exactly computing $\lambda_{max}(H_{G})$ , we may try to approximate this value. In both problems, the local term $h$ is positive semidefinite, so $\lambda_{max}(H_{G})\geq 0$ . We judge an approximation by its approximation ratio. Suppose we can find efficiently computable functions $\ell,u$ such that for all graphs $G$ ,

\displaystyle 0\leq\ell(G)\leq\lambda_{max}(H_{G})\leq u(G)\,.

Then, the approximation ratio $\alpha$ is at least

\displaystyle\alpha\geq\min_{G}\frac{\ell(G)}{\lambda_{max}(H_{G})}\geq\min_{G% }\frac{\ell(G)}{u(G)}\,.

In most works, the upper bound $u$ is determined by solving a semidefinite programming (SDP) relaxation of the maximization problem [3, 7, 16, 19, 20, 9]. The source of such SDP relaxations are generally hierarchies of SDPs that provide increasingly better upper bounds $u$ at the cost of solving larger-sized SDPs. The quantum moment-SOS hierarchy, typically based on Pauli operators, is widely employed for quantum local Hamiltonian problems. This hierarchy is an instance of the NPA hierarchy [15] and is also known as the quantum Lasserre hierarchy [16]. The second level of the quantum moment-SOS hierarchy is necessary for good approximations, since critical monogamy-of-entanglement properties begin to emerge at that level [16, 17].

The lower bound $\ell$ is usually determined by an algorithm that prepares a state with this energy. Several approximation algorithms have been proposed for QMC and EPR, using product states [7, 16, 17, 12], matchings [1, 16, 17, 14, 10, 8], and short variational circuits [1, 13, 12, 11, 8]. During the preparation of this manuscript, the best known approximation ratios for these problems were improved to $\alpha\geq 0.603$ for QMC [8] and $\alpha\geq\frac{1+\sqrt{5}}{4}\approx 0.809$ for EPR [11].

We provide a new algorithm for both problems. For each algorithm, we start from a good product state. We then choose a matching in $G$ and partially rotate matched qubits towards an entangled state. Our novel contribution is to perform this rotation such that individual single-qubit Bloch vectors are preserved, up to a rescaling of magnitude. This allows us to evaluate the energy of our entangled state in terms of the energy of the product state. For EPR, we use a fractional matching and provide a circuit-based algorithm. For QMC, we explicitly describe a tensor-product of single and two-qubit states, which interpolates between the product state and an integer matching-based state with a single tunable parameter. For QMC, we additionally introduce the technique of choosing a maximum-weight matching with respect to rescaled edge weights. One interpretation of this approach is that we widen the search space of our algorithm to include matchings other than the maximum-weight matching of $G$ . Combining these techniques allows us to achieve state-of-the-art approximation ratios on each problem:

Theorem 1.

For EPR, $\alpha\geq\frac{\varphi}{2}\approx 0.809$ , where $\varphi\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\frac{1+% \sqrt{5}}{2}\approx 1.618$ is the golden ratio.

Theorem 2.

For QMC, $\alpha\geq 0.611$ .

$\blacktriangleright$ Remark 3.

Theorem 1 was shown simultaneously and independently by [11] using a different algorithm. The algorithm of [11] also partially entangles edges while preserving single-qubit marginals. However, we believe both our algorithm and analysis are simpler.

$\blacktriangleright$ Remark 4.

Theorem 2 requires an improved upper bound in addition to new algorithmic techniques. The technique of finding a matching with respect to rescaled edge weights was simultaneously and independently used by [8]; however, they use this as part of an improved approximation algorithm for QMC on triangle-free graphs rather than general graphs. Our QMC approximation does rely on a strengthening by [8] of a class of upper bounds first used in the work [14]. Without this strengthened bound, we still achieve an approximation ratio $\alpha\geq 0.610$ .

Our approximation algorithm finds a quantum state $\rho_{G}$ such that $\mathrm{Tr}\left(H_{G}\rho_{G}\right)\geq\ell(G)$ . For the EPR Hamiltonian, the analysis of our algorithm is optimal: there exist graphs $G$ (such as the single-edge graph) where

\displaystyle\frac{\ell(G)}{u(G)}\leq\frac{\bra{\psi_{G}}H_{G}\ket{\psi_{G}}}{% \lambda_{max}(G)}=\frac{1+\sqrt{5}}{4}\,.

For QMC, however, it is possible that a better analysis of this algorithm (particularly of $u(G)$ ) would give a larger approximation ratio.

We stress the novelty of this work is new algorithmic techniques for QMC and EPR. We use these techniques to immediately improve the approximation ratios for each algorithm, however we believe that these techniques, potentially combined with previous methods, may lead to further improvements in approximation ratios for both algorithms. In the remainder of this work, we introduce necessary notation, describe each algorithm, and prove Theorems 1 and 2. We defer some technical lemmas to the appendix, which can be found in the full version of this paper [2].

2 Preliminaries

2.1 Graph theory

Let $G(V,E,w)$ denote a graph with vertex set $V$ , edge set $E$ , and positive edge weights $w:E\rightarrow\mathbb{R}_{+}$ . In this work, we always take $V={\left[n\right]}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}% }\{1,2,\dots,n\}$ . We let $W_{G}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\sum_{(i,j)% \in E}w_{ij}$ . When $G$ is inferred by context, we simply write $W$ . Define $N(v)$ as the set of neighbors of a vertex $v\in V$ . For convenience, we index edges by either $e$ or $(i,j)$ , or simply $i j$ in subscripts.

A fractional matching of a graph $G(V,E,w)$ is a function $m:E(G)\to[0,1]$ that assigns a value to each edge in $G$ , such that the sum over values $\sum_{j\in N(i)}m_{ij}$ is at most $1$ for any vertex $i$ . If $m_{ij}\in\{0,1\}$ for all edges $(i,j)$ , we say that $m$ is an integral matching. For an integral matching $m$ , we say an edge $(i,j)$ is in the matching if $m_{ij}=1$ . The weight $\textrm{Wt}(m)$ of a matching $m$ is defined as $\textrm{Wt}(m)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}% \sum_{(i,j)\in E(G)}w_{ij}\,m_{ij}$ . We define $\textnormal{FM}_{G}$ (or $\textnormal{M}_{G}$ ) to be the maximum total weight of any fractional (or integral) matching of $G$ . For convenience, we sometimes let $\textnormal{M}_{G}$ also denote the set of edges in the maximum-weight integral matching of $G$ . When the graph is clear from context we drop the subscript $G$ . Optimal integral and fractional matchings can be computed in polynomial time, for example with linear programming [6].

2.2 Quantum computation

We refer to $\vec{\sigma}=\left(X,Y,Z\right)$ as the canonical Pauli matrices. As such, we can define the Bloch vector $\vec{B}(\rho)$ of any $1$ -qubit density matrix $\rho$ as the vector $(b_{x},b_{y},b_{z})$ in the unit sphere $\textrm{S}^{2}$ such that

\displaystyle\rho=\frac{1}{2}(I+\vec{B}(\rho)\cdot\vec{\sigma})\stackrel{{% \scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\frac{1}{2}(I+b_{x}X+b_{y}Y+% b_{z}Z)\,.

Pure states correspond to unit Bloch vectors. Let $\ket{\psi_{-}}=\frac{1}{\sqrt{2}}\left(\ket{01}-\ket{10}\right)$ be the singlet state, and $\ket{\phi_{+}}=\frac{1}{\sqrt{2}}\left(\ket{00}+\ket{11}\right)$ be the EPR state.

2.3 Previous algorithms

In our work, we use two previously known algorithms as subroutines:

1.

The algorithm $\mathrm{PROD}$ takes a graph $G(V,E,w)$ as an input, and outputs a good product state $\rho_{PROD}$ . For EPR, we define $\rho_{PROD}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\ket{0% }^{\otimes n}\bra{0}^{\otimes n}$ . For QMC, we define $\mathrm{PROD}$ to be the output of the [7] rounding algorithm applied to the some fixed constant level $k$ of the quantum moment-SOS hierarchy, as in [17] and [14]. This is the only part of our algorithm for QMC that relies on an SDP. As described in [17, Sec 2.2], the output from the SDP can be interpreted as a pseudo-density matrix. It is called a pseudo-density matrix because it satisfies only some of the constraints of a valid density matrix. Furthermore, the SDP at any constant $\ell$ can be solved in polynomial time.
2.

The algorithm $\mathrm{MATCH}$ takes a graph $G(V,E,w)$ as an input, and outputs a product of 2-qubit states $\rho_{MATCH}$ . It was first formally proposed in [14]. The algorithm first finds a maximum-weight integral matching $\textnormal{M}_{G}$ . For EPR (and for QMC), it outputs the tensor product of $\ket{\phi_{+}}_{ij}\bra{\phi_{+}}_{ij}$ (and $\ket{\psi_{-}}_{ij}\bra{\psi_{-}}_{ij}$ for QMC) for every pair of vertices $(i,j)$ in the matching, and the maximally mixed state for every vertex $i$ not in the matching. This obtains energy $2$ on matched edges and $1/2$ on unmatched edges, for a total of $(3\textnormal{M}_{G}+W_{G})/2$ .

3 Our Algorithms

To motivate our algorithms, consider the following simple graph $G$ :

This graph is bipartite, so QMC and EPR are equivalent under local rotations [12]. We thus focus on EPR for simplicity. It is easy to compute that $\lambda_{max}(H_{G})=3$ . The optimal product state $\rho_{PROD}$ is $\rho_{0}^{\otimes 3}$ , where $\rho_{0}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\ket{0}% \bra{0}$ , and achieves energy $2$ . The algorithm $\mathrm{MATCH}$ computes the maximum matching $\textnormal{M}_{G}=\left\{(a,b)\right\}$ and returns the state $\rho_{MATCH}$ as described in Section 2. This state gains energy $2$ on edge $(i,j)$ and $1/2$ on edge $(b,c)$ , achieving total energy $5/2$ . Thus, the algorithm of [14], which returns the better of $\rho_{PROD}$ and $\rho_{MATCH}$ , achieves $5/6\approx 0.833$ of the optimal energy.

Our algorithms do better by interpolating between $\rho_{PROD}$ and $\rho_{MATCH}$ , rather than taking the better of the two. For our example $G$ , the unitary

\displaystyle U=e^{i\theta\left(\frac{X_{a}-Y_{a}}{\sqrt{2}}\otimes\frac{X_{b}% -Y_{b}}{\sqrt{2}}\right)}\,,

takes $\rho_{PROD}$ to $\rho^{\prime}$ , a tensor product of a two-qubit state $\rho_{ab}$ and a single-qubit state $\rho_{c}$ . The parameter $\theta$ sets the entanglement for $\rho_{ab}$ : when $\theta=0$ , $\rho_{ab}$ is a product state; when $\theta=\pi/4$ , $\rho_{ab}$ is fully rotated into the EPR state. As such, we view this approach as smoothly interpolating between $\rho_{PROD}$ and $\rho_{MATCH}$ in superposition. It can be easily verified that the energy obtained by $\rho^{\prime}$ on edge $(a,b)$ is $\mathrm{Tr}{\left[h^{EPR}_{ab}\rho^{\prime}\right]}=1+2\cos\theta\sin\theta$ , and the single qubit marginals of $a$ and $b$ are given by

\displaystyle\rho^{\prime}_{a}\stackrel{{\scriptstyle\mathrm{% \scriptscriptstyle def}}}{{=}}\mathrm{Tr}_{bc}{\left[\rho^{\prime}\right]}=% \cos{2\theta}\rho_{0}+2\sin^{2}{\theta}I=\rho^{\prime}_{b}\,.

In particular, note that the single qubit marginals are simply rescaled and shifted by the identity. This fact aids in the analysis: we can still evaluate the energy of $(b,c)$ in terms of $\rho_{PROD}$ , even though the edge is not in our matching:

	$\displaystyle\mathrm{Tr}{\left[h^{EPR}_{bc}\rho^{\prime}\right]}$	$\displaystyle=\mathrm{Tr}{\left[h^{EPR}_{bc}\left(\rho^{\prime}_{b}\otimes\rho% ^{\prime}_{c}\right)\right]}$
		$\displaystyle=\mathrm{Tr}{\left[h^{EPR}_{bc}\left(\rho^{\prime}_{b}\otimes\rho% _{0}\right)\right]}$
		$\displaystyle=\mathrm{Tr}{\left[h^{EPR}_{bc}\left(\left(\cos{2\theta}\rho_{0}+% 2\sin^{2}{\theta}\,\left(I/2\right)\right)\otimes\rho_{0}\right)\right]}$
		$\displaystyle=\mathrm{Tr}{\left[h^{EPR}_{bc}\left(\cos{2\theta}\rho_{PROD}+% \sin^{2}{\theta}\,I\otimes\rho_{0}\right)\right]}$
		$\displaystyle=\cos{2\theta}+\sin^{2}\theta=\cos^{2}\theta\,.$

Thus the total energy is given by

\displaystyle\mathrm{Tr}{\left[(h^{EPR}_{ab}+h^{EPR}_{bc})\rho^{\prime}\right]% }=1+2\cos\theta\sin\theta+\cos^{2}\theta\,.

The parameter $\theta$ can be optimized over; in this example, taking $\theta\approx.554$ yields

\displaystyle\mathrm{Tr}{\left[(h^{EPR}_{ab}+h^{EPR}_{bc})\rho^{\prime}\right]% }\approx 2.618,

outperforming both $\rho_{PROD}$ and $\rho_{MATCH}$ .

In this example, the analysis simplifies nicely because the initial product state is the symmetric state $\rho_{0}^{\otimes n}$ , and because the graph is bipartite. For EPR on general graphs, we provide a circuit-based algorithm that prepares an entangled state based on a fractional matching in the graph. This state still works by partially entangling edges according to the matching while preserving single-qubit marginals, but it does not have a simple interpretation in terms of $\rho_{MATCH}$ . We leave open the possibility that a $(\frac{1+\sqrt{5}}{4})$ -approximation algorithm can be achieved with a tensor product of one and two-qubit states that simply interpolates between $\rho_{PROD}$ and $\rho_{MATCH}$ . For QMC, our algorithm does indeed interpolate between $\rho_{PROD}$ and $\rho_{MATCH}$ . However the algorithm and analysis become slightly more complicated. Crucial to our analysis is the following lemma:

Lemma 5 (Energy obtained by QMC algorithm on matched and unmatched edges).

Given two $1$ -qubit pure states $\rho_{i},\rho_{j}$ and a real parameter $\theta\in[0,\pi/2]$ , there exists a $2$ -qubit pure state $\rho_{ij}$ such that

	$\displaystyle\mathrm{Tr}{\left[{h^{QMC}\rho_{ij}}\right]}$	$\displaystyle=\frac{(1+\sin{\theta})\left(1-\vec{B}(\rho_{i})\cdot\vec{B}(\rho% _{j})\right)}{2}\,,$
	$\displaystyle\vec{B}(\mathrm{Tr}_{j}{\left[\rho_{ij}\right]})$	$\displaystyle=\cos{\theta}\cdot\vec{B}(\rho_{i})\,,$
	$\displaystyle\vec{B}(\mathrm{Tr}_{i}{\left[\rho_{ij}\right]})$	$\displaystyle=\cos{\theta}\cdot\vec{B}(\rho_{j})\,.$

The last two constraints in Lemma 5 indicate that the Bloch vectors of the single-qubit marginals of $\rho_{ij}$ are rescaled Bloch vectors of $\rho_{i}$ and $\rho_{j}$ , respectively. This is analogous to the argument in our example, where the marginals are rescaled and shifted by the identity. This again allows us to compute the energy of unmatched edges in terms of $\rho_{PROD}$ . The parameter $\theta\,$ again sets the entanglement in $\rho_{ij}$ : when $\theta=0$ , $\rho_{ij}$ is a product state; when $\theta=\pi/2$ , $\rho_{ij}$ is maximally entangled. The proof of Lemma 5 is given in the appendix of [2].

3.1 EPR

Using the intuition from our example, we introduce the following algorithm for EPR:

Algorithm 1 (Fractional matching algorithm for EPR).

Given a weighted graph $G(V,E,w)$ :

1.

Define the $1$ -qubit Hamiltonian

$\displaystyle P\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}% \frac{1}{\sqrt{2}}(X-Y)\,,$

and the angle

$\displaystyle\theta\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=% }}\frac{\ln\left(\varphi\right)}{2}\approx 0.240\,,$ (1)

where $\varphi=\frac{1+\sqrt{5}}{2}$ is the golden ratio.
2.

Find a fractional matching $(m_{uv})_{(u,v)\in E}$ of maximum weight (e.g., via linear programming).
3.

Output the state

$\displaystyle\ket{\chi}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}% }{{=}}\prod_{(u,v)\in E}e^{i\gamma_{uv}P_{u}P_{v}}\ket{0}^{\otimes n}\,,$ (2)

where

$\displaystyle\gamma_{uv}$ $\displaystyle=\frac{1}{2}\cos^{-1}\exp{\left[-\theta\cdot m_{uv}\right]}\ \in% \ [0,\pi/2]\,.$ (3)

The unitary $e^{i\gamma P_{u}P_{v}}$ rotates the state $\ket{00}_{ij}$ towards the Bell state $\ket{\phi^{+}}$ ; this circuit was proposed in the approximation algorithm of [12].

3.2 QMC

Our algorithm for QMC relies on the following subroutine, which we call $\mathrm{PMATCH}$ since it places partially entangled 2-qubit states on the edges of a matching, while $\mathrm{MATCH}$ places maximally entangled states:

Algorithm 2 ( $\mathrm{PMATCH}$ ).

Given a weighted graph $G(V,E,w)$ and a real parameter $\theta\in{\left[0,\pi/2\right]}$ :

1.

Prepare the state $\rho_{PROD}=\bigotimes_{i\in[n]}\rho_{i}$ by running the $\mathrm{PROD}$ algorithm on QMC from Section 2 for some fixed, constant SDP level $\ell$ .
2.

For each edge $(i,j)\in E$ , compute $t_{ij}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\vec{B}(% \rho_{i})\cdot\vec{B}(\rho_{j})$ from $\rho_{PROD}$ .
3.

Find a maximum-weight integral matching $\widetilde{M}\subseteq E$ on the reweighted graph $G(V,E^{\prime},\widetilde{w})$ , where

$\displaystyle\widetilde{w}_{ij}=w_{ij}\cdot\left(\frac{\sin{\theta}\left(1-t_{% ij}\left(1+\sin{\theta}\right)\right)}{2}\right)^{+}\,,$ (4)

and $E^{\prime}=\{(i,j)\in E\ |\ \widetilde{w}_{ij}>0\}$ . Here, we use the notation $(\cdot)^{+}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\max(0% ,\cdot)$ from [14].
4.

Let $\rho_{PMATCH}\left(\theta\right)$ be the state starting from $\rho_{PROD}$ , but for each edge $(i,j)$ in $\widetilde{M}$ , replace $\rho_{i}\otimes\rho_{j}$ with the state $\rho_{ij}$ described in Lemma 5, parametrized by $\rho_{i},\rho_{j},\theta$ .
5.

Output the state $\rho_{PMATCH}\left(\theta\right)$ .

Our algorithm for QMC chooses the better of the algorithms $\mathrm{PMATCH}$ and $\mathrm{MATCH}$ :

Algorithm 3 (Combined algorithm for QMC).

Given a weighted graph $G(V,E,w)$ :

1.

Prepare the state $\rho_{MATCH}$ by running the $\mathrm{MATCH}$ algorithm from Section 2.
2.

Prepare the state $\rho_{PMATCH}\left(\theta\right)$ by running $\mathrm{PMATCH}$ with parameter $\theta=1.286$ .
3.

Output the state out of $\rho_{MATCH}$ and $\rho_{PMATCH}(\theta)$ obtaining larger energy on the QMC Hamiltonian $H_{G}$ .

4 Analysis

We upper-bound the maximum energy $\lambda_{max}(H_{G})$ of QMC and EPR Hamiltonians using a quantifiable monogamy of entanglement:

Lemma 6 (Monogamy of Entanglement, e.g. [14, Lemma 1]).

For both EPR and QMC, and for all graphs $G(V,E,w)$ , we have

\displaystyle\lambda_{max}(H_{G})\leq W_{G}+\textnormal{FM}_{G}\,.

For QMC, our analysis improves with better upper bounds on $\lambda_{max}(H_{G})$ . We use an inequality of the form $W_{G}+\textnormal{M}_{G}/d$ ; this first appears in [14, Lemma 4] with the constant $d=4/5$ . By a detailed analysis and numerical verification on graphs with up to $13$ vertices, this constant was recently improved to $14/15$ in [8]:

Lemma 7 (Strengthened monogamy of entanglement, [8, Lemma 3.10]).

For QMC, and for all graphs $G(V,E,w)$ , we have

\displaystyle\lambda_{max}(H_{G})\leq W_{G}+\frac{\textnormal{M}_{G}}{d}\,,

where $d=\frac{14}{15}$ . Additionally, the bound holds for the optimal value of the $13$ -th level of the quantum moment SoS hierarchy.

4.1 EPR

We now prove Theorem 1. Given the state in Equation 2

\displaystyle\ket{\chi}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}% }{{=}}\prod_{(i,j)\in E}e^{i\gamma_{ij}P_{i}P_{j}}\ket{0}^{\otimes n}\,,

(5)

[12, Lemma 9] showed that the energy on the local term $h^{EPR}_{ij}$ is at least

\displaystyle\bra{\chi}h_{ij}^{EPR}\ket{\chi}\geq\frac{1}{2}\left(1+A_{ij}B_{% ij}+\sin 2\gamma_{ij}\cdot(A_{ij}+B_{ij})\right)\,,

(6)

where

	$\displaystyle A_{ij}$	$\displaystyle\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}% \prod_{k\in N(i)\setminus\{j\}}\cos 2\gamma_{ik}\,,$
	$\displaystyle B_{ij}$	$\displaystyle\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}% \prod_{k\in N(j)\setminus\{i\}}\cos 2\gamma_{jk}\,.$

In Algorithm 1, the output state $\ket{\chi}$ is in the form of Equation 5. Using the angles $\gamma_{ij}$ specified by Equation 3, we have

$\displaystyle A_{ij}$	$\displaystyle=\exp{\left[-\theta\!\!\sum_{k\in N(i)\setminus\{j\}}\!\!m_{ik}% \right]}\geq\exp{\left[-\theta(1-m_{ij})\right]}\,,$	(7)
$\displaystyle B_{ij}$	$\displaystyle=\exp{\left[-\theta\!\!\sum_{k\in N(j)\setminus\{i\}}\!\!m_{jk}% \right]}\geq\exp{\left[-\theta(1-m_{ij})\right]}\,,$	(8)
$\displaystyle\sin 2\gamma_{ij}$	$\displaystyle=\sqrt{1-\cos^{2}2\gamma_{ij}}=\sqrt{1-\exp{\left[-2\theta m_{ij}% \right]}}\,.$	(9)

The inequalities in the first two lines follow because $m$ is a matching. For example, we have $m_{ij}+\sum_{k\in N(i)\setminus\{j\}}m_{ik}\leq 1$ . Using Equation 6, the energy of $\ket{\chi}$ on $h_{ij}^{QMC}$ is at least

\displaystyle T(\theta,m_{ij})\stackrel{{\scriptstyle\mathrm{% \scriptscriptstyle def}}}{{=}}\frac{1}{2}\left(1+\exp{\left[-2\theta(1-m_{ij})% \right]}+2\sqrt{1-\exp{\left[-2\theta m_{ij}\right]}}\exp{\left[-\theta(1-m_{% ij})\right]}\right)\,.

(10)

We combine Equation 10 with Lemma 6 to bound the approximation ratio on any graph $G(V,E,w)$ :

\displaystyle\frac{\bra{\chi}H_{G}\ket{\chi}}{\lambda_{max}(H_{G})}\geq\frac{% \sum_{(i,j)\in E}w_{ij}\cdot T(\theta,m_{ij})}{\sum_{(i,j)\in E}w_{ij}\left(1+% m_{ij}\right)}\,.

Each term in the numerator and denominator is positive, so the approximation ratio is at least the approximation ratio of the worst edge

\displaystyle\min_{(i,j)\in E}\frac{T(\theta,m_{ij})}{1+m_{ij}}\geq\min_{x\in[% 0,1]}\frac{T(\theta,x)}{1+x}\,.

(11)

Recall from Equation 1 that we take $\theta=\frac{1}{2}\ln\varphi$ . We empirically identified $\theta$ as the angle that maximizes the approximation ratio in this analysis. Substituting this value into $T(\theta,x)$ in Equation 10, the RHS of Equation 11 yields the minimization problem

\displaystyle\min_{x\in[0,1]}{\left[\frac{1}{2(1+x)}\left(1+\varphi^{-(1-x)}+2% \sqrt{1-\varphi^{-x}}\cdot\varphi^{-\frac{1}{2}(1-x)}\right)\right]},

whose value is found to be $\varphi/2$ by the following lemma:

Lemma 8.

Given $\varphi\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\frac{1+% \sqrt{5}}{2}$ , we have that

\displaystyle\min_{x\in[0,1]}{\left[\frac{1}{2(1+x)}\left(1+\varphi^{-(1-x)}+2% \sqrt{1-\varphi^{-x}}\cdot\varphi^{-\frac{1}{2}(1-x)}\right)\right]}=\frac{1+% \sqrt{5}}{4}=\frac{\varphi}{2}\,.

(12)

The proof of Lemma 8 is given in the appendix of [2].

4.2 QMC

We now analyze Algorithm 3 and prove the $0.611$ -approximation in Theorem 2. We first introduce some helpful notation. Fix a graph $G(V,E,w)$ . Let $\tilde{\rho}$ be the pseudo-density matrix outputted by solving the SDP of the level- $\ell$ quantum moment-SOS hierarchy (described in Section 2.3). We define

\displaystyle g_{ij}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{% =}}\mathrm{Tr}[h_{ij}^{QMC}\tilde{\rho}]\,,\quad\quad s_{ij}\stackrel{{% \scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\frac{1}{3}\mathrm{Tr}{\left% [(X_{i}X_{j}+Y_{i}Y_{j}+Z_{i}Z_{j})\tilde{\rho}\right]}\,.

The first value is the energy obtained by $\tilde{\rho}$ on $h_{ij}^{QMC}$ ; the second value is the expected value of $\tilde{\rho}$ with respect to the traceless components of the term $h_{ij}^{QMC}$ . It is straightforward to show that $g_{ij}=\frac{1}{2}(1-3s_{ij})$ . The output of the SDP gives an upper bound to the optimal energy:

\displaystyle\lambda_{max}(H_{G})\leq\sum_{(i,j)\in E}w_{ij}\cdot g_{ij}=\sum_% {(i,j)\in E}w_{ij}\cdot\frac{1-3s_{ij}}{2}\,.

(13)

Fix a positive integer $k$ and suppose Lemma 7 is true for $d=\frac{2k}{2k+1}$ . Then, consider a reweighting $\widetilde{G}(V,E,u)$ of the graph $G$ where $u_{ij}\geq 0$ . Let $x\in\mathbb{R}^{E}$ be a vector with

\displaystyle x_{ij}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{% =}}d\left(g_{ij}-1\right)^{+}=d\left(-\frac{1+3s_{ij}}{2}\right)^{+}.

Here, we again use the notation $(\cdot)^{+}\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}\max(% \,\cdot\,,0)$ from [14], which ensures

\displaystyle\left(-\frac{1+3s_{ij}}{2}\right)^{+}\in{\left[0,1\right]}\,,% \quad\quad\forall(i,j)\in E.

It is shown (e.g. in [8, Lemma 3.4]) that $x$ is in the integral matching polytope of $\widetilde{G}$ . This means that $x$ is a convex combination of integral matchings $\left\{m_{\ell}\right\}_{1\leq\ell\leq k}$ . Since the weight of any integral matching $m_{\ell}$ on $\widetilde{G}$ is at most $\textnormal{M}_{\widetilde{G}}$ , the weight of $x$ on $\widetilde{G}$ is also at most $\textnormal{M}_{\widetilde{G}}$ . Thus,

\displaystyle\sum_{(i,j)\in E}u_{ij}\cdot d\cdot\left(-\frac{1+3s_{ij}}{2}% \right)^{+}\leq\textnormal{M}_{\widetilde{G}}\,.

(14)

Equation 14 in this context was first used in [16] and also appears in [14, Lemma 4] and [10, Lemma C.2].

We now find a lower bound for the energy obtained by the matching state $\rho_{PMATCH}\left(\theta\right)$ in $\mathrm{PMATCH}$ . We consider the energy on a case-by-case basis in the following lemma:

Lemma 9.

Consider the state $\rho_{PMATCH}$ and matching $\widetilde{M}$ from Algorithm 2. For $x\in\{0,1,2\}$ , let $\widetilde{S}_{x}$ be the subset of edges not in $\widetilde{M}$ (e.g. $\widetilde{S}_{x}\subseteq E\setminus\widetilde{M}$ ) where each edge in $\widetilde{S}_{x}$ has $x$ matched endpoints in $\widetilde{M}$ . Then the energy of $\rho_{PMATCH}$ on an edge $(i,j)$ is exactly

\displaystyle\mathrm{Tr}{\left[h_{ij}^{QMC}\rho_{PMATCH}\right]}=\begin{cases}% \frac{1}{2}\left(1+\sin\theta\right)\left(1-t_{ij}\right),&(i,j)\in\widetilde{% M}\,,\\ \frac{1}{2}(1-t_{ij}),&(i,j)\in\widetilde{S}_{0}\,,\\ \frac{1}{2}\left(1-t_{ij}\cos\theta\right),&(i,j)\in\widetilde{S}_{1}\,,\\ \frac{1}{2}\left(1-t_{ij}\cos^{2}\theta\right),&(i,j)\in\widetilde{S}_{2}\,.% \end{cases}

where, $t_{ij}$ is defined in Algorithm 2.

Proof.

The case when $(i,j)\in\widetilde{M}$ follows directly from how we choose $\rho_{PMATCH}$ in Algorithm 2, Step 4. For all other edges, recall that $t_{ij}$ is the inner product of the Bloch vectors of qubits $i$ and $j$ with respect to the product state $\rho_{PROD}$ . The reduced density matrix of $\rho_{\mathrm{PMATCH}}$ on qubits $i$ and $j$ is a product state $\sigma_{i}\otimes\sigma_{j}$ . By [12, Lemma 10], the energy of $\sigma_{i}\otimes\sigma_{j}$ on $h^{QMC}_{ij}$ is

\displaystyle\frac{1}{2}\left(1-\vec{B}(\sigma_{i})\cdot\vec{B}(\sigma_{j})% \right)\,.

We handle each remaining case separately:

1.

$(i,j)\in\widetilde{S}_{0}$ : Here, the product state is exactly $\rho_{i}\otimes\rho_{j}$ , and so $\vec{B}(\sigma_{i})\cdot\vec{B}(\sigma_{j})=t_{ij}$ by definition.¹¹1Although $\widetilde{M}$ is a maximum matching, its edge set $E^{\prime}$ is a subset of $E$ , and so $\widetilde{S}_{0}$ may be non-empty.
2.

$(i,j)\in\widetilde{S}_{1}$ : Without loss of generality, $i$ belongs to a matched edge in $\widetilde{M}$ and $j$ is not in a matched edge. Lemma 5 implies that $\vec{B}(\sigma_{i})$ is rescaled to $\vec{B}(\sigma_{i})\cos\theta$ , and so $\vec{B}(\sigma_{i})\cdot\vec{B}(\sigma_{j})=t_{ij}\cos\theta$ .
3.

$(i,j)\in\widetilde{S}_{2}$ : $i$ and $j$ belong to two different matched edges. Therefore, it has both Bloch vectors rescaled, i.e. $\vec{B}(\sigma_{i})\cdot\vec{B}(\sigma_{j})=\left(\vec{B}(\rho_{i})\cdot\vec{B% }(\rho_{j})\right)\cos^{2}\theta=t_{ij}\cos^{2}\theta$ .

$\hfill\blacktriangleleft$

Lemma 9 allows us to compute the energy obtained by the state $\rho_{PMATCH}\left(\theta\right)$ :

	$\displaystyle\mathrm{PMATCH}(\theta)\stackrel{{\scriptstyle\mathrm{% \scriptscriptstyle def}}}{{=}}\sum_{(i,j)\in E}w_{ij}\cdot\mathrm{Tr}[h_{ij}^{% QMC}\rho_{PMATCH}]$
	$\displaystyle=\sum_{(i,j)\in\widetilde{M}}\frac{w_{ij}}{2}\left(1+\sin\theta% \right)\left(1-t_{ij}\right)+\sum_{(i,j)\in\widetilde{S}_{0}}\frac{w_{ij}}{2}% \left(1-t_{ij}\right)$
	$\displaystyle\hskip 60.0pt+\sum_{(i,j)\in\widetilde{S}_{1}}\frac{w_{ij}}{2}% \left(1-t_{ij}\cos\theta\right)+\sum_{(i,j)\in\widetilde{S}_{2}}\frac{w_{ij}}{% 2}\left(1-t_{ij}\cos^{2}\theta\right)$
	$\displaystyle=\sum_{(i,j)\in E}\frac{w_{ij}}{2}\left(1-t_{ij}\cos^{2}\theta% \right)+\sum_{(i,j)\in\widetilde{M}}\frac{w_{ij}}{2}\left(\left(1+\sin\theta% \right)\left(1-t_{ij}\right)-(1-t_{ij}\cos^{2}\theta)\right)$
	$\displaystyle\hskip 60.0pt+\sum_{(i,j)\in\widetilde{S}_{0}}\frac{w_{ij}t_{ij}}% {2}\left(\cos^{2}\theta-1\right)+\sum_{(i,j)\in\widetilde{S}_{1}}\frac{w_{ij}t% _{ij}}{2}\left(\cos^{2}\theta-\cos\theta\right)$
	$\displaystyle=\sum_{(i,j)\in E}\frac{w_{ij}}{2}\left(1-t_{ij}\cos^{2}\theta% \right)+\sum_{(i,j)\in\widetilde{M}}\frac{w_{ij}}{2}\left(\sin{\theta}\left(1-% t_{ij}\left(1+\sin{\theta}\right)\right)\right)$
	$\displaystyle\hskip 60.0pt-\sum_{(i,j)\in\widetilde{S}_{0}}\frac{w_{ij}t_{ij}}% {2}\sin^{2}\theta+\sum_{(i,j)\in\widetilde{S}_{1}}\frac{w_{ij}t_{ij}}{2}\left(% \cos^{2}\theta-\cos\theta\right)\,.$		(15)

Note that $\widetilde{M}$ is a maximum-weight integral matching with respect to the rescaled weights defined in Equation 4. Thus, we can invoke Equation 14 to replace the sum over $\widetilde{M}$ in Equation 15 with a sum over $E$ . Since the rescaled weights are positive for all edges in $\widetilde{M}$ , we have

	$\displaystyle\mathrm{PMATCH}(\theta)$	$\displaystyle\geq\!\sum_{(i,j)\in E}\frac{w_{ij}}{2}\Bigg(1-t_{ij}\cos^{2}% \theta+d\big(\sin{\theta}\left(1-t_{ij}\left(1+\sin{\theta}\right)\right)\big)% \left(-\frac{1+3s_{ij}}{2}\right)^{+}\Bigg)$
		$\displaystyle\hskip 18.49988pt-\sum_{(i,j)\in\widetilde{S}_{0}}\frac{w_{ij}t_{% ij}}{2}\sin^{2}\theta+\sum_{(i,j)\in\widetilde{S}_{1}}\frac{w_{ij}t_{ij}}{2}% \left(\cos^{2}\theta-\cos\theta\right)\,.$		(16)

Note that $t_{ij}$ is a random variable because $\mathrm{PROD}$ is a randomized algorithm. The analysis of $\mathrm{PROD}$ in [7] is based on [4], which shows that $\mathbb{E}{\left[t_{ij}\right]}=F(s_{ij})$ . A definition of $F$ in the context of QMC appears in [17, Equation 3]. For our purposes, it is enough to note that $F$ is an odd function because it has the form

F(s)=c\cdot s\cdot G(s^{2})\,,

(17)

where $c>0$ is a constant and $G\geq 0$ is a hypergeometric function. Since Section 4.2 is linear in $t_{ij}$ , we use linearity of expectation to conclude

		$\displaystyle\mathbb{E}{\left[\mathrm{PMATCH}(\theta)\right]}\geq$
		$\displaystyle\sum_{(i,j)\in E}\frac{w_{ij}}{2}\Bigg(1-F(s_{ij})\cos^{2}\theta+% d\sin{\theta}\left(1-F(s_{ij})\left(1+\sin{\theta}\right)\right)\left(-\frac{1% +3s_{ij}}{2}\right)^{+}\Bigg)$
		$\displaystyle\hskip 20.00003pt-\sum_{(i,j)\in\widetilde{S}_{0}}\frac{w_{ij}}{2% }F(s_{ij})\sin^{2}\theta+\sum_{(i,j)\in\widetilde{S}_{1}}\frac{w_{ij}}{2}\Big(% \!\left(\cos^{2}\theta-\cos\theta\right)\,F(s_{ij})\Big)\,.$		(18)

The following lemma lets us analyze the performance of Algorithm 3, which takes the better of two algorithms, $\mathrm{MATCH}$ and $\mathrm{PMATCH}$ .

Lemma 10 (Reducing worst-case bounds to a single edge).

Suppose we have a collection of $k$ approximation algorithms $\{A_{\ell}\}_{\ell\in{\left[k\right]}}$ and an upper bound on the maximum energy $\lambda_{max}(H_{G})\leq\sum_{e\in E}w_{e}b_{e}$ , where $b_{e}\in B=(0,b_{max}]$ for all $e\in E$ , and $b_{max}$ is a constant. Furthermore, suppose that the energy that algorithm $A_{\ell}$ earns on edge $e$ is a function of $b_{e}$ , which we denote $a_{\ell}(b_{e})$ , such that $A_{\ell}$ earns $\sum_{e\in E}w_{e}\,a_{\ell}(b_{e})$ . Then, by running each of $A_{\ell\in[k]}$ and taking the output with the maximum energy, we can obtain an approximation ratio

\displaystyle\alpha\geq\max_{\mu_{\ell}}\;\min_{b}\sum_{\ell}\mu_{\ell}\frac{a% _{\ell}(b)}{b},

where the maximum is taken over valid probability distributions

\displaystyle\{\ \mu\ |\ \sum_{\ell\in[k]}\mu_{\ell}=1,\;0\leq\mu_{\ell}\leq 1% \;\forall\ell\in[k]\ \}\,,

and the minimum is taken over $b\in B$ .

Proof.

Given a specific graph $G$ , outputting the best of $A_{\ell}$ is at least as good as outputting the result of $A_{\ell}$ with probability $\mu_{\ell}$ , for all $\ell\in[k]$ and for any possible $\mu$ . Now, given a fixed distribution $\mu,$ the approximation ratio is at least

	$\displaystyle\alpha$	$\displaystyle\geq\;\sum_{\ell}\mu_{\ell}\frac{\sum_{e\in E}w_{e}\,a_{\ell}(b_{% e})}{\sum_{e\in E}w_{e}b_{e}}$
		$\displaystyle=\;\sum_{\ell}\mu_{\ell}\sum_{e\in E}\left(\frac{w_{e}b_{e}}{\sum% _{e\in E}w_{e}b_{e}}\right)\frac{a_{\ell}(b_{e})}{b_{e}}$
		$\displaystyle\geq\;\min_{e\in E}\,\sum_{\ell}\mu_{\ell}\frac{a_{\ell}(b_{e})}{% b_{e}}$
		$\displaystyle\geq\;\min_{b\in B}\sum_{\ell}\mu_{\ell}\frac{a_{\ell}(b)}{b}\,.$

The third line follows because

\displaystyle\left\{\frac{w_{e}b_{e}}{\sum_{e\in E}w_{e}b_{e}}\right\}_{e\in E}

is a distribution over $E$ . Since the statement is true for all possible distributions $\mu$ , we take the maximum over $\mu$ to finish the lemma. $\hfill\blacktriangleleft$

We apply Lemma 10 with the SDP upper bound in Equation 13 and our two algorithms $\mathrm{MATCH}$ and $\mathrm{PMATCH}$ as described in Algorithm 3. For $\mathrm{PMATCH}$ , we consider the minimum of three different functions, depending on if an edge is in $\widetilde{S}_{0}$ , in $\widetilde{S}_{1}$ , or otherwise. For $\mathrm{MATCH}$ , we derived in Section 2.3 that the energy obtained by $\mathrm{MATCH}$ on $G$ is $\frac{3\textnormal{M}+W}{2}$ . Since M is a maximum-weight matching with respect to $G$ , we may invoke Equation 14 to express

\displaystyle\textnormal{M}\geq\sum_{(i,j)\in E}w_{ij}\,\cdot d\cdot\left(-% \frac{1+3s_{ij}}{2}\right)^{+}\,,

implying that $\mathrm{MATCH}$ achieves energy at least

\displaystyle\frac{3\textnormal{M}+W}{2}\geq\sum_{(i,j)\in E}\frac{w_{ij}}{2}% \left(1+3d\left(-\frac{1+3s_{ij}}{2}\right)^{+}\right)\,.

We have lower-bounded the energy that each algorithm earns on an edge $(i,j)$ as a function of $s_{ij}$ . Note that the SDP upper bound is trivial (i.e. at most $0$ ) when $s_{ij}\geq\frac{1}{3}$ , so we may search over $s\in[-1,1/3)$ . Altogether, Lemma 10 implies that Algorithm 3 obtains approximation ratio at least

$\displaystyle\alpha$	$\displaystyle\geq\max_{\mu\in{\left[0,1\right]},\,\theta\in{\left[0,\pi/2% \right]}}\min\Big\{\min_{s\in[-1,1/3)}\;\ \mu\,E_{PM}(\theta)+(1-\mu)E_{M},$
	$\displaystyle\hskip 127.99988pt\min_{s\in[-1,1/3)}\;\;\mu\,E_{PM}^{\prime}(% \theta)+(1-\mu)E_{M},$
	$\displaystyle\hskip 127.99988pt\min_{s\in[-1,1/3)}\;\;\mu\,E_{PM}^{\prime% \prime}(\theta)+(1-\mu)E_{M}\Big\}\,,$	(19)

$\displaystyle E_{PM}(\theta)$	$\displaystyle\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}% \frac{1-F(s)\cos^{2}\theta+d\sin{\theta}\left(1-F(s)\left(1+\sin{\theta}\right% )\right)\cdot\big(-\frac{1+3s}{2}\big)^{+}}{1-3s}\,,$	(20)
$\displaystyle E_{PM}^{\prime}(\theta)$	$\displaystyle\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}% \frac{1-F(s)\cos\theta+d\sin{\theta}\left(1-F(s)\left(1+\sin{\theta}\right)% \right)\cdot\big(-\frac{1+3s}{2}\big)^{+}}{1-3s}\,,$	(21)
$\displaystyle E_{PM}^{\prime\prime}(\theta)$	$\displaystyle\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}% \frac{1-F(s)+d\sin{\theta}\left(1-F(s)\left(1+\sin{\theta}\right)\right)\cdot% \big(-\frac{1+3s}{2}\big)^{+}}{1-3s}\,,$	(22)
$\displaystyle E_{M}$	$\displaystyle\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}% \frac{1+3\,d\,(-\frac{1+3s}{2})^{+}}{1-3s}\,.$	(23)

In the above, $\mu$ is demoted to a scalar (which fully describes a probability distribution over two variables). Equation 23 is the approximation ratio obtained by $\mathrm{MATCH}$ on an edge with $s=s_{ij}$ . The expected approximation ratio obtained by $\mathrm{PMATCH}$ is Equation 22 on an edge in $\widetilde{S}_{0}$ , Equation 21 on an edge in $\widetilde{S}_{1}$ , and is Equation 20 on all other edges.

We further simplify Equation 19. Recall that $F$ is an odd function (Equation 17). So, for all $\theta\in[0,\pi/2]$ we have $E_{PM}^{\prime\prime}(\theta)\leq E_{PM}^{\prime}(\theta)\leq E_{PM}(\theta)$ when $s>0$ and $E_{PM}(\theta)\leq E_{PM}^{\prime}(\theta)\leq E_{PM}^{\prime\prime}(\theta)$ when $s\leq 0$ . So we may rewrite Equation 19 as

\displaystyle\alpha

\displaystyle\geq\hskip-11.04124pt\max_{\mu\in{\left[0,1\right]},\,\theta\in{% \left[0,\pi/2\right]}}\hskip-4.015pt\min\Big\{\min_{s\in[-1,0)}\mu\,E_{PM}(% \theta)+(1-\mu)E_{M},\min_{s\in[0,1/3)}\mu\,E_{PM}^{\prime\prime}(\theta)+(1-% \mu)E_{M}\Big\}\,.

(24)

One may then search over the three free parameters $\mu$ , $\theta$ , and $s$ using an enumeration of the feasible ranges. For a more efficient approach, it is also possible to solve a linear program where the number of variables and constraints is based on an enumeration of the feasible ranges for $s$ and $\theta$ . We obtain $\alpha>0.611$ for $d=14/15$ at $\theta=1.286$ and $\mu=0.861$ . By Lemma 7, our algorithm thus achieves a $0.611$ -approximation in expectation if $\ell=13$ . If the factor $d$ in Lemma 7 is improved to $1$ , we would obtain $\alpha>0.614$ at $\theta=1.288$ and $\mu=0.881$ .

$\blacktriangleright$ Remark 11.

We may simplify Equation 19 by assuming $s\in[-1,0)$ . This is because if $s\in[0,1/3)$ then $E_{M}\geq 1$ and $E_{PM}^{\prime\prime}(\theta)\geq 1$ for all $\theta\in[0,\pi/2]$ . This follows from $F$ being odd, and in addition $|F(s)|\leq|s|$ for all $s\in[-1,1]$ .

5 Discussion

In this work, we introduce two novel techniques for constructing algorithms for the Quantum MaxCut and EPR Hamiltonians on arbitrary graphs. The main techniques are a) partially entangling edges in a matching towards an entangled state while maintaining the direction of the marginal Bloch vectors as b) choosing matching with respect to reweighted graphs. We show that these techniques immediately lead to state-of-the-art approximation ratios for both problems. We believe that these techniques may be combined with other methods to obtain further improvements, and encourage further studies in this direction.

References

[1] Anurag Anshu, David Gosset, and Karen Morenz. Beyond product state approximations for a quantum analogue of Max Cut. LIPIcs, Volume 158, TQC 2020, 158:7:1–7:15, 2020. doi:10.4230/LIPIcs.TQC.2020.7.
[2] Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud. Improved algorithms for quantum maxcut via partially entangled matchings, 2025. arXiv:2504.15276.
[3] Fernando G. S. L. Brandão and Aram W. Harrow. Product-state Approximations to Quantum Ground States, December 2014. arXiv:1310.0017.
[4] Jop Briet, Fernando Mario de Oliveira Filho, and Frank Vallentin. The positive semidefinite Grothendieck problem with rank constraint, 2010. doi:10.1007/978-3-642-14165-2_4.
[5] Toby Cubitt and Ashley Montanaro. Complexity classification of local Hamiltonian problems, March 2016. arXiv:1311.3161.
[6] Jack Edmonds. Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17:449–467, January 1965. doi:10.4153/CJM-1965-045-4.
[7] Sevag Gharibian and Ojas Parekh. Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut. LIPIcs, Volume 145, APPROX/RANDOM 2019, 145:31:1–31:17, 2019. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.31.
[8] Sander Gribling, Lennart Sinjorgo, and Renata Sotirov. Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs, April 2025. arXiv:2504.11120.
[9] Felix Huber, Kevin Thompson, Ojas Parekh, and Sevag Gharibian. Second order cone relaxations for quantum Max Cut, November 2024. arXiv:2411.04120.
[10] Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, Juspreet Singh Sandhu, and Stuart Wayland. Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians, November 2024. arXiv:2410.15544.
[11] Nathan Ju and Ansh Nagda. Improved approximation algorithms for the EPR Hamiltonian, April 2025. doi:10.48550/arXiv.2504.10712.
[12] Robbie King. An Improved Approximation Algorithm for Quantum Max-Cut. Quantum, 7:1180, November 2023. doi:10.22331/q-2023-11-09-1180.
[13] Eunou Lee. Optimizing quantum circuit parameters via SDP, September 2022. arXiv:2209.00789.
[14] Eunou Lee and Ojas Parekh. An improved Quantum Max Cut approximation via matching, February 2024. arXiv:2401.03616.
[15] Miguel Navascues, Stefano Pironio, and Antonio Acin. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 10(7):073013, July 2008. doi:10.1088/1367-2630/10/7/073013.
[16] Ojas Parekh and Kevin Thompson. Application of the Level-$2$ Quantum Lasserre Hierarchy in Quantum Approximation Algorithms. LIPIcs, Volume 198, ICALP 2021, 198:102:1–102:20, 2021. doi:10.4230/LIPIcs.ICALP.2021.102.
[17] Ojas Parekh and Kevin Thompson. An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms, June 2022. doi:10.48550/arXiv.2206.08342.
[18] Stephen Piddock and Ashley Montanaro. The complexity of antiferromagnetic interactions and 2D lattices, December 2015. arXiv:1506.04014.
[19] Jun Takahashi, Chaithanya Rayudu, Cunlu Zhou, Robbie King, Kevin Thompson, and Ojas Parekh. An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max Cut, August 2023. arXiv:2307.15688.
[20] 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.

[bib.bib1] [1] Anurag Anshu, David Gosset, and Karen Morenz. Beyond product state approximations for a quantum analogue of Max Cut. LIPIcs, Volume 158, TQC 2020, 158:7:1–7:15, 2020. doi:10.4230/LIPIcs.TQC.2020.7.

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

[bib.bib3] [3] Fernando G. S. L. Brandão and Aram W. Harrow. Product-state Approximations to Quantum Ground States, December 2014. arXiv:1310.0017.

[bib.bib4] [4] Jop Briet, Fernando Mario de Oliveira Filho, and Frank Vallentin. The positive semidefinite Grothendieck problem with rank constraint, 2010. doi:10.1007/978-3-642-14165-2_4.

[bib.bib5] [5] Toby Cubitt and Ashley Montanaro. Complexity classification of local Hamiltonian problems, March 2016. arXiv:1311.3161.

[bib.bib6] [6] Jack Edmonds. Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17:449–467, January 1965. doi:10.4153/CJM-1965-045-4.

[bib.bib7] [7] Sevag Gharibian and Ojas Parekh. Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut. LIPIcs, Volume 145, APPROX/RANDOM 2019, 145:31:1–31:17, 2019. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.31.

[bib.bib8] [8] Sander Gribling, Lennart Sinjorgo, and Renata Sotirov. Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs, April 2025. arXiv:2504.11120.

[bib.bib9] [9] Felix Huber, Kevin Thompson, Ojas Parekh, and Sevag Gharibian. Second order cone relaxations for quantum Max Cut, November 2024. arXiv:2411.04120.

[bib.bib10] [10] Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, Juspreet Singh Sandhu, and Stuart Wayland. Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians, November 2024. arXiv:2410.15544.

[bib.bib11] [11] Nathan Ju and Ansh Nagda. Improved approximation algorithms for the EPR Hamiltonian, April 2025. doi:10.48550/arXiv.2504.10712.

[bib.bib12] [12] Robbie King. An Improved Approximation Algorithm for Quantum Max-Cut. Quantum, 7:1180, November 2023. doi:10.22331/q-2023-11-09-1180.

[bib.bib13] [13] Eunou Lee. Optimizing quantum circuit parameters via SDP, September 2022. arXiv:2209.00789.

[bib.bib14] [14] Eunou Lee and Ojas Parekh. An improved Quantum Max Cut approximation via matching, February 2024. arXiv:2401.03616.

[bib.bib15] [15] Miguel Navascues, Stefano Pironio, and Antonio Acin. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 10(7):073013, July 2008. doi:10.1088/1367-2630/10/7/073013.

[bib.bib16] [16] Ojas Parekh and Kevin Thompson. Application of the Level-$2$ Quantum Lasserre Hierarchy in Quantum Approximation Algorithms. LIPIcs, Volume 198, ICALP 2021, 198:102:1–102:20, 2021. doi:10.4230/LIPIcs.ICALP.2021.102.

[bib.bib17] [17] Ojas Parekh and Kevin Thompson. An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms, June 2022. doi:10.48550/arXiv.2206.08342.

[bib.bib18] [18] Stephen Piddock and Ashley Montanaro. The complexity of antiferromagnetic interactions and 2D lattices, December 2015. arXiv:1506.04014.

[bib.bib19] [19] Jun Takahashi, Chaithanya Rayudu, Cunlu Zhou, Robbie King, Kevin Thompson, and Ojas Parekh. An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max Cut, August 2023. arXiv:2307.15688.

[bib.bib20] [20] 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 Algorithms for Quantum MaxCut via Partially Entangled Matchings

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1.

Theorem 2.

▶ Remark 3.

▶ Remark 4.

2 Preliminaries

2.1 Graph theory

2.2 Quantum computation

2.3 Previous algorithms

3 Our Algorithms

Lemma 5 (Energy obtained by QMC algorithm on matched and unmatched edges).

3.1 EPR

Algorithm 1 (Fractional matching algorithm for EPR).

3.2 QMC

Algorithm 2 (PMATCH).

Algorithm 3 (Combined algorithm for QMC).

4 Analysis

Lemma 6 (Monogamy of Entanglement, e.g. [14, Lemma 1]).

Lemma 7 (Strengthened monogamy of entanglement, [8, Lemma 3.10]).

4.1 EPR

Lemma 8.

4.2 QMC

Lemma 9.

Proof.

Lemma 10 (Reducing worst-case bounds to a single edge).

Proof.

▶ Remark 11.

5 Discussion

References

$\blacktriangleright$ Remark 3.

$\blacktriangleright$ Remark 4.

Algorithm 2 ( $\mathrm{PMATCH}$ ).

$\blacktriangleright$ Remark 11.