A Refined Algorithm For the EPR model

Wenxuan Tao, Fen Zuo · 2025

Read A Refined Algorithm For the EPR model by Wenxuan Tao, Fen Zuo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-08547.txt.

Introduction

Wenxuan Tao and Fen Zuo sharpen an algorithm for a quantum toy model with a famous name, in a 2025 paper. The EPR model was proposed two years earlier by King. It is a cousin of a classic magnetism model, equivalent to the quantum maximum-cut problem. In it, neighboring qubits prefer symmetric Bell pairings over the antisymmetric one, because that choice maximizes the energy. Two groups had independently reached the same accuracy guarantee using fractional matchings. The authors refine one of those methods.

Their twist uses uniform or near-uniform fractional matchings to spread entanglement as evenly as possible. On regular graphs the guarantee improves at once. On irregular graphs it holds when the matchings are chosen with care. Better guarantees for toy models often seed methods for the real optimization problems quantum computers may one day tackle.

Catalog record

CREATORWenxuan Tao, Fen Zuo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-08547

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Refined Algorithm For the EPR model Wenxuan Tao, Fen Zuo Abstract The Einstein-Podolsky-Rosen (EPR) model is an analogous model of the anti-ferromagnetic Heisenberg model or the equivalent quantum maximum-cut problem, proposed by R. King two years ago. Adjacent qubits in the model prefer symmetric EPR/Bell parings rather than the antisymmetric one, in order to maximize the energy. Recently, two groups independently develop specific algorithms for the highest-energy state with approximation ratio 1 + 5 4 ≈ .809 \frac{1+\sqrt{5}}{4}\approx.809 , based on maximum fractional matchings. Here we try to refine one of the two algorithms by devising homogeneous/quasi-homogeneous fractional matchings, with the aim to distribute quantum entanglement as much as possible. For regular graphs G d G_{d} , we immediately obtain increasing approximation ratios r d r_{d} with r 2 = 3 + 5 6 ≈ .872 r_{2}=\frac{3+\sqrt{5}}{6}\approx.872 . For irregular graphs, we show such a refinement could still guarantee nice performance if the fractional matchings are chosen properly. I The EPR model We start with the anti-ferromagnetic Heisenberg model, which is equivalent to the so-called Quantum Maximum Cut (QMC) problem. In the latter problem, the Hamiltonian is defined on a weighted graph G(V,E,w) : H^{\textrm{QMC}}_{G}=\sum_{(ij)}w_{ij}h_{ij}\equiv\frac{1}{2}\sum_{(ij)}w_{ij}(I_{i}I_{j}-X_{i}X_{j}-Z_{i}Z_{j}-Y_{i}Y_{j}), (1) where the summation is over all edges (ij)\in E_{G} , and all the weights are supposed to be positive. The aim is to maximize the corresponding energy, or the expectation value of the Hamiltonian. Thus adjacent qubits would favor the antisymmetric pairing |\psi_{-}\rangle=\frac{1}{2}(|01\rangle-|10\rangle). (2) The Einstein-Podolsky-Rosen (EPR) model could be considered as the symmetric counterpart King-2023 of QMC. Without loss of generality, the Hamiltonian could be taken as H^{\textrm{EPR}}_{G}=\sum_{(ij)}w_{ij}g_{ij}\equiv\frac{1}{2}\sum_{(ij)}w_{ij}(I_{i}I_{j}+X_{i}X_{j}+Z_{i}Z_{j}-Y_{i}Y_{j}). (3) Then adjacent qubits would favor the symmetric pairing |\phi_{+}\rangle=\frac{1}{2}(|00\rangle+|11\rangle), (4) in order to maximize the energy. According to the analyses in PM-2015 , QMC is QMA-hard and EPR is in StoqMA Bravyi-2006 . With the so-called monogamy of entanglement argument CKW-1999 , the maximum eigenvalue of both QMC and EPR could be bounded by maximum-weight fractional matching (MWFM) as AGM-2020 Lee-2024 : \lambda_{\textrm{max}}(H_{G})\leq w_{G}+w(\textrm{FM}_{G}). (5) Here w_{G} is total weight, and w(\textrm{FM}_{G}) is the value of the MWFM \textrm{FM}_{G} . Possible strengthening of the bound to maximum-weight matching is discussed in GSS-2025 APS-2025 . In the rest of the paper, we only consider the EPR model, and more specifically the highest-energy state of the EPR model. II THE ALMPS Algorithm The above upper bound suggests that one could devise nice approximation algorithms based on MWFM. This is the strategy adopted recently in both JN-2025 and ALMPS-2025 . They independently develop approximation algorithms for EPR with the same approximation ratio r_{0}\approx.809 , but the implementation are quite different. The algorithm in JN-2025 uses a heavy mixed state, which is not quite convenient to generalize. So we focus on the approach of ALMPS-2025 , and call it ALMPS for short. The ALMPS algorithm utilizes a nice state proposed in King-2023 , which we now review. II.1 Magic Graph States In the measurement-based quantum computing scenario, the so-called graph states are indispensable, which are defined as |\psi_{G}\rangle\equiv\prod_{(ij)}CZ_{ij}|+\rangle^{\otimes n}. (6) Since only CZ and H gates are involved, graph states are necessary Clifford. Ref. King-2023 introduces generalized graph states as |\chi\rangle\equiv\prod_{(ij)}\mathrm{e}^{\mathrm{i}\theta_{ij}P_{i}P_{j}}|0\rangle^{\otimes n}, (7) with P=TYT^{\dagger}=\frac{1}{\sqrt{2}}(X-Y),\quad Q=TXT^{\dagger}=\frac{1}{\sqrt{2}}(X+Y). (8) Here all the two-qubit gates \mathrm{e}^{\mathrm{i}\theta_{ij}P_{i}P_{j}} also communicate with each other as the CZ gates above, making the states well defined. Moreover, now |\chi\rangle necessarily involve a huge number of T gates, so we may call them magic graph states. Due to the inclusion of magic, we could expect them to possess strong expressive power. With the above definitions of P and Q gates, we may re-express the terms involving X and Y in the EPR Hamiltonian as X_{i}X_{j}-Y_{i}Y_{j}=P_{i}Q_{j}+Q_{i}P_{j}. (9) So to compute the energy, we need to calculate the expectation values of Z_{i}Z_{j} , P_{i}Q_{j} and Q_{i}P_{j} on |\chi\rangle . All these have been done in detail in King-2023 , with the concrete expressions: \displaystyle\langle\chi|Q_{i}P_{j}|\chi\rangle \displaystyle= \displaystyle\sin 2\theta_{ij}\prod_{k\in K}\cos 2\theta_{ik}, (10) \displaystyle\langle\chi|P_{i}Q_{j}|\chi\rangle \displaystyle= \displaystyle\sin 2\theta_{ij}\prod_{l\in L}\cos 2\theta_{jl}, (11) \displaystyle\langle\chi|Z_{i}Z_{j}|\chi\rangle \displaystyle= \displaystyle\sum_{S\subset T,|S|\textrm{even}}\prod_{s\in S}\sin 2\theta_{is}\sin 2\theta_{sj}\prod_{k\in K\setminus S}\cos 2\theta_{ik}\prod_{l\in L\setminus S}\cos 2\theta_{lj}. (12) Here K\equiv\{k\in V_{G}:k\sim i,k\neq j\},\quad L\equiv\{l\in V_{G}:l\sim j,l\neq i\}, (13) and T=\{t\in V_{G}:t\sim i,t\sim j\}. (14) One can see that only the expression of \langle\chi|Z_{i}Z_{j}|\chi\rangle inherits some quantumness, and may not be efficiently calculated with classical methods. With these explicit expressions, one may be tempted to directly variate all the parameters \{\theta_{ij}\} to get higher energies. Since the number of parameters is so huge, this would not be an easy task anyhow. Even this could be done efficiently, it would not necessarily guarantee a very nice approximation. In fact, we have the following claim: Claim 1. Variation of magic graph states |\chi\rangle gives an approximation ratio for EPR no larger than r_{2}=\frac{3+\sqrt{5}}{6}\approx.872 . This can be easily confirmed by considering G=K_{2,2} . It shows that, the power of the magic graph states |\chi\rangle in solving EPR has an obvious limitation. So instead of devising universal algorithms for all graphs, one could consider an alternative strategy and develop specific algorithms for specific graphs. This will be elucidated in detail later. Still, such a brute-force approach gives very nice results for many graphs, with approximation ratios often much larger than r_{2} . So we boldly make the following conjecture: Conjecture 1. Variation of magic graph states |\chi\rangle could achieve the approximation ratio r_{2} for EPR. We will give some evidences for this later. II.2 The ALMPS Algorithm The ALMPS algorithm considers more sophisticated choices for the parameters ALMPS-2025 . From the expressions ( 10 , 11 , 12 ) one can see that the energy on an individual edge is affected by the parameters on the adjacent edges. ALMPS-2025 uses MWFM to cleverly convert these parameters back to the one on the current edge. More precisely, they choose the parameters \theta_{ij} according to the matching fraction m_{ij} in MWFM as \cos 2\theta_{ij}=\exp[-\kappa\cdot m_{ij}], (15) where \kappa is a positive constant, and \theta_{ij} is restricted to be in [0,\pi/4] . Now if we abandon the higher powers in ( 12 ), we get the following estimation of the individual energy term: \langle\chi|g_{ij}|\chi\rangle\geq T(\kappa,m_{ij})\equiv\frac{1}{2}(1+\exp[-2\kappa(1-m_{ij})]+2\sqrt{1-\exp[-2\kappa m_{ij}]}\exp[-\kappa(1-m_{ij})]). (16) Since the right-hand side depends only on m_{ij} , we could easily bound it with m_{ij} as we want. Thus we define R(\kappa,m_{ij})\equiv T(\kappa,m_{ij})/(1+m_{ij}), (17) and try to maximize it for all the values that m_{ij} may take. According to Matching-1986 , every vertex of the fractional matching polytope take the basic form, which consists of disconnected edges and odd cycles. Therefore, MWFM of the basic form generally contains matching fractions 0,1/2,1 . In the degenerate case, other values could also appear. Therefore, one could consider the following maximum-minimum problem: r_{0}\equiv\max_{\kappa>0}\min_{x\in[0,1]}R(\kappa,x). (18) ALMPS-2025 proves that it is half the golden ratio \varphi=\frac{1+\sqrt{5}}{2} : r_{0}=\frac{\varphi}{2}\approx.809, (19) and the corresponding parameter is \kappa_{0}\equiv\frac{1}{2}\ln\varphi\approx.240. (20) With the parameter \kappa fixed this way, one could employ the upper bound ( 5 ) to show \displaystyle\frac{\langle\chi|H_{G}^{\textrm{EPR}}|\chi\rangle}{\lambda_{\textrm{max}}(H_{G}^{\textrm{EPR}})} \displaystyle\geq \displaystyle\frac{\langle\chi|H_{G}^{\textrm{EPR}}|\chi\rangle}{w_{G}+w(\textrm{FM}_{G})} (21) \displaystyle= \displaystyle\frac{\sum_{(ij)}w_{ij}\langle\chi|g_{ij}|\chi\rangle}{\sum_{(ij)}w_{ij}(1+m_{ij})} \displaystyle\geq \displaystyle\min_{x\in[0,1]}R(\kappa_{0},x)=r_{0}. Therefore, the ALMPS algorithm has an approximation ratio r(\textrm{ALMPS})\geq r_{0}\approx.809. (22) A simple analysis shows that, the appearance of both the matching fractions 0 and 1 forces the ratio to be no larger than r_{0} . This is emphasized recently in APS-2025 . Since the basic form

Read the complete text