Pith. sign in

REVIEW 3 major objections 4 minor 33 references

Testing APS conjecture on regular graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For the EPR model on Henning–Yeo k-regular graphs, the FED lower bound on maximum energy stays below the APS matching bound for k=3 through 10.

desk verdict A careful but underpowered negative test of the APS conjecture on Henning-Yeo graphs; the simplified King formula is a small useful result, but reproducibility and the final 'accept' suggestion need work. read the letter →

arxiv 2507.10050 v1 pith:AR5RL5ZX submitted 2025-07-14 quant-ph cond-mat.stat-mechmath-phmath.COmath.MP

Wenxuan Tao , Fen Zuo This is my paper
classification quant-phcond-mat.stat-mechmath-phmath.COmath.MP
keywords EPRmodelAPSconjecturequantummaxcutregulargraphsHenning-Yeofractionalmatchingmaximumapproximationalgorithm
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tests a conjectured strengthening of the known upper bound on the maximum energy of the EPR model, a quantum Hamiltonian on weighted graphs. The known bound is $\lambda_{\max} \le w(G)+w(FM_G)$, where $w(G)$ is the total edge weight and $w(FM_G)$ is the value of a maximum-weight fractional matching. The APS conjecture says the bound still holds when $w(FM_G)$ is replaced by $w(M_G)$, the value of a maximum ordinary matching. The authors test this on Henning–Yeo regular graphs, a family of $k$-regular graphs whose maximum matchings are as small as possible, which should make the conjecture hardest to satisfy. Using their FED approximation algorithm to obtain strong lower bounds on $\lambda_{\max}$, they compare the normalized energy $\hat r_k$ with the normalized APS threshold $\hat m_k$ for $k=3,\dots,10$, in unweighted and weighted versions with internal-to-external weight ratio 10. In every case $\hat r_k$ remains below $\hat m_k$, so the numerical results show no evidence that the APS conjecture could be violated.

What carries the argument

The machinery is a comparison of two normalized quantities built from a single quantum construction. The FED algorithm (Fractional Entanglement Distribution) assigns rotation angles to a magic graph state according to a nearly uniform fractional matching, and the state's expectation value provides a lower bound on $\lambda_{\max}$. The core identity is the simplified expectation formula $$\langle\chi|Z_iZ_j|\chi\rangle = \frac{1}{2}\Bigl(1+(\$cos^{2}$ 2\$\theta$-\$sin^{2}$ 2\$\theta$)^t\Bigr)\prod_{k\in\widetilde K}\cos 2\theta_{ik}\prod_{l\in\widetilde L}\cos 2\theta_{lj},$$ where $t$ is the number of common neighbours of $i$ and $j$, and the products run over their non-common neighbours. This formula collects all higher-order contributions that earlier analyses neglected, and the paper evaluates it on the quasi-complete building blocks that make up the Henning–Yeo graphs. The decisive test is whether the normalized FED lower bound $\hat r_k$ exceeds the normalized APS threshold $\hat m_k$; the graph class is chosen so that ordinary matchings are as small as possible, making $\hat m_k$ the smallest target the APS bound can offer in this family.

What would settle it

Compute $\lambda_{\max}$ of the EPR Hamiltonian exactly, or bound it with a certified hierarchy, on the smallest Henning–Yeo graph of each degree $k=3,\dots,10$, and compare with $w(G)+w(M_G)$; a single graph with $\lambda_{\max}$ above the APS bound would falsify the conjecture and show the FED lower bound was too weak.

Watch

Extended reading notes

Core claim

The central discovery is empirical: on the Henning–Yeo $k$-regular graphs the APS conjecture survives a targeted stress test. The violation condition would be $\hat r_k > \hat m_k$, where $\hat r_k$ is the FED lower bound on the energy divided by $w(G)+w(FM_G)$ and $\hat m_k=(w(G)+w(M_G))/(w(G)+w(FM_G))$ is the corresponding normalized APS ceiling. Because the Henning–Yeo construction makes $w(M_G)$ as small as possible relative to $w(FM_G)$, the shifted ratio $\hat m_k$ is as low as this family allows, leaving the least possible room between a good energy lower bound and the conjectured ceiling. The authors compute $\hat r_k$ for $k=3$ through 10, including the higher-order terms in the exact expectation value via a simplified binomial formula; these corrections improve the base FED ratios by only about .001–.002. Giving the internal edges ten times the weight of the external edges lowers both $\hat m_k$ and $\hat r_k$, shrinking the gap but never closing it, with the closest weighted case $\hat r_{10}^{w}=.958$ below $\hat m_{10}^{w}=.992$. The paper concludes that the results give no hint that the APS conjecture is violated.

Load-bearing premise

The whole comparison stands or falls on the assumption that the energies the FED algorithm calculates are genuinely achievable by some quantum state; if the simplified formula overestimates the energy, then seeing those numbers stay below the APS bound proves nothing.

Editorial extensions

If this is right

  • On every Henning–Yeo graph tested, with $k=3,\dots,10$ and with weight ratio 10, the FED lower bound stays strictly below the APS bound, so this family yields no counterexample.
  • The higher-order corrections to the $Z_iZ_j$ expectation change the normalized energy by only about .001–.002, which is far smaller than the gap to the APS threshold; the original approximations are adequate for this qualitative test.
  • Weighting the odd components more heavily shrinks the gap but not enough to close it; the closest weighted case leaves $\hat r_{10}^{w}=.958$ against $\hat m_{10}^{w}=.992$.
  • The paper infers that accepting the conjecture and exploring its consequences is more productive than searching for counterexamples, since the required approximation ratios would be at least .97 (unweighted) and .95 (weighted).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A stronger exact check on the smallest Henning–Yeo graphs would remove the main residual doubt: FED supplies a lower bound, and only a certified upper bound or exact diagonalization can show whether the true maximum energy could sit above the APS bound.
  • The no-violation pattern is a single data family; testing random $k$-regular graphs, where matchings are near-perfect, and other weight ratios would show whether the result is special to the tight-matching construction.
  • Because the APS conjecture follows from the token-graph conjectures, any regular-graph counterexample would refute those conjectures as well; conversely, proving the bound on regular graphs would be a natural first step toward the general statement.
  • The paper's ratio comparison suggests the real obstruction to resolving the conjecture is not the matching gap but the hardness of approximating EPR energies close to 1; algorithms beyond the .809 baseline would need to improve by roughly 15 percentage points to test weighted cases.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper tests the APS conjecture, which states that the maximum energy of the EPR Hamiltonian on a weighted graph is at most w(G)+w(MWM), where MWM is the maximum-weight matching. The test is performed on Henning-Yeo k-regular graphs for k=3..10, a family in which maximum matchings are known to take tight lower bounds relative to fractional matchings. The authors use their previously proposed FED algorithm to compute lower bounds on the maximum EPR energy and compare these lower bounds with the normalized APS bound. In both the unweighted case and a weighted case with internal/external weight ratio dw=10, the FED lower bounds remain below the APS bounds, and the authors conclude that their numerical results show no evidence that the APS conjecture could be violated.

Significance. The choice of Henning-Yeo graphs is a meaningful stress test: on these graphs the maximum matching is as small as possible relative to the fractional matching, so the APS bound is comparatively tight. The FED lower bounds are close to the APS bounds, with gaps as small as about 0.001 in the weighted table, so the reported test is nontrivial. The paper does not provide a proof or a definitive confirmation of the conjecture, and its contribution is numerical evidence that is consistent with the conjecture. Because the central comparison rests on lower bounds computed with an algorithm from the authors' prior work, the strength of the paper depends on the reproducibility and correctness of those numerical lower bounds; the manuscript does not currently supply enough detail to verify them.

major comments (3)
  1. [IV.B and Appendix B, Eq. (B6)] The weighted-case approximation ratios in Table V rely on applying the simplified King formula to edges of the odd-degree Henning-Yeo construction, but the paper does not verify the formula's condition edge class by edge class. The derivation of Eq. (B6) requires that, for each edge ij, all angles on the edges joining the common-neighbor set T to i and j are identical. With separate angles theta1, theta2, theta3 assigned to internal edges, external edges incident to the quasi-complete blocks, and other external edges, it is not automatic that this condition holds for every internal edge in H_{k+2}^x and H_{k+1}^{x,y}; the text only states that higher-order terms appear for internal edges. Please supply the missing verification or compute the full expression. Without it, the quantity hatted r_k^w is not established as a lower bound on the EPR ground energy, and Table V cannot support the no-violation claim.
  2. [II.B and IV.B] The weighted-case FED construction is underspecified at the point where it could change the result. The text says that for weighted graphs all weights are 'rounded into integers properly' and represented by multi-edges before assigning matching fractions m_ij=1/d_ij, but it does not specify the rounding rule or prove that this multi-edge representation preserves the Henning-Yeo structure used in Appendix B. Parallel edges change common-neighbor sets and edge degrees, so the simplified formula may not apply to the rounded multi-edge graph even if it applies to the original weighted graph. If the FED expectation is computed on the rounded multi-edge graph, the reported hatted r_k^w values in Table V may not be valid lower bounds for the weighted EPR Hamiltonian. Please justify this step or avoid the round-trip through multi-edges.
  3. [IV.B and Table V] The numerical evidence is not reproducible from the manuscript. The paper does not report the optimized values of kappa, theta1, theta2, theta3, the matching fractions in the weighted construction, the graph order parameter p for each k, or the averaging over Henning-Yeo instances that justifies the claim of weak dependence; no code or raw data are provided. Since the reported gaps are as small as 0.001 for k=9,10, an undocumented algorithmic choice could plausibly change the sign of the comparison. Please include these parameters or a code/data supplement so that the lower bounds can be independently checked.
minor comments (4)
  1. [I, Eq. (4)] There are typographical errors in the introduction: 'Parekn' should be 'Parekh', and the text after Eq. (4) contains the stray characters '£º'.
  2. [IV.A and Table IV] The statement that the improved ratios hatted r_k 'vary very slightly' across Henning-Yeo instances is not quantified. Since the differences between r_k and hatted r_k are already only about 0.001-0.002, please provide the observed spread or state the number of instances tested.
  3. [V] The sentence 'we would better accept its validity and study its consequences' overstates the logical force of the numerical evidence. The data are consistent with the APS conjecture but cannot establish its validity; please rephrase this as a speculative conclusion.
  4. [IV.B] In the sentence introducing the weighted construction, 'odd components' appears to mean the quasi-complete blocks that become odd components under the Tutte-Berge argument; please clarify the terminology to avoid confusion with the parity of k.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: FED lower bounds are computed independently and compared against MWM/MWFM ratios without assuming the APS conjecture.

full rationale

The paper tests the APS conjecture by constructing magic graph states via the FED algorithm and comparing the resulting lower bound on the EPR energy with the APS upper bound w(G)+w(MWM). The comparison in Tables IV and V is between r-hat_k = <chi|H|chi> / (w(G)+w(FMFM)) and m-hat_k = (w(G)+w(MWM)) / (w(G)+w(FMFM)); a violation would require r-hat_k >= m-hat_k. Neither quantity is defined in terms of the other, and the FED expectation values are obtained from King's formulas (10)-(12) and the ALMPS lower-bound function T(kappa,m) in Eq. (16), both of which are external to this paper. The self-citation to [14] supplies the FED construction idea m_ij=1/d_ij and the general ratio inequality (25), but for the specific k-regular Henning-Yeo graphs the ratios r_k and r-hat_k are computed directly from Eq. (28) and the simplified King formula, not from the APS conjecture. The weighted case relies on the same simplified formula; its validity condition--identical angles on edges incident to each common-neighbor set--is asserted rather than fully demonstrated, which is an omitted-proof/correctness risk rather than circularity. No step in the derivation reduces to its own input or to the conjecture being tested.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central test leans on algorithm parameters from a previous self-cited paper and on an unproved weighted extension of the FED algorithm, but no new physical entities are introduced. The free parameters are algorithmic choices rather than physical constants, and the axioms are mostly standard results or domain assumptions from prior work.

free parameters (4)
  • kappa_k (FED optimization parameter) = 0.324 to 0.0544 for k=2 to 10 (Tab. I)
    Chosen by maximizing the minimum edge energy ratio over matching fractions; determines the rotation angles in FED and is inherited from the authors' prior paper.
  • weight ratio dw = w1/w2 = 10
    Chosen by hand in Section IV.B because the decrease in the approximation ratio almost vanishes at dw >= 10; it is an ad hoc choice intended to enlarge the gap between MWM and MWFM.
  • matching fraction assignment m_ij = 1/d_ij = 1/d_ij for each edge
    A heuristic from the FED algorithm (Eq. 27) that fixes the fractional matching weights and hence the rotation angles; not derived from first principles.
  • internal/external rotation angles theta1, theta2, theta3 = not listed in the paper
    In the weighted FED, separate angles are assigned to internal and external edges of the quasi-complete components; their values are not reported, but they directly determine the numerical energy estimates in Tables IV and V.
assumptions (5)
  • domain assumption lambda_max(H_G) <= w(G) + w(FM_G) (MWFM upper bound)
    Used as the baseline upper bound for EPR maximum energy; proven via the quantum Lasserre hierarchy in [6] and taken as input.
  • domain assumption Magic graph states (Eq. 6) with expectation formulas (10)-(12) can approximate the EPR ground state energy
    Assumes King's variational ansatz and the computed expectation values; inherited from [2].
  • standard math The Tutte-Berge theorem and the Henning-Yeo construction realize the tight lower bounds on maximum matching
    Used in Section III to select graphs with minimum matching size; standard result from [11].
  • ad hoc to paper The weighted FED construction preserves the approximation guarantee when weights are rounded to integers and multi-edges are used
    The weighted generalization of FED is asserted without a full proof of the approximation ratio for arbitrary weight ratios, especially with separate angles.
  • ad hoc to paper The simplified King formula (B6) applies to the Henning-Yeo quasi-complete graphs with the angle assignments used
    Assumes all edges incident to common-neighbor sets carry identical angles and that other angle dependences factor as written; this is not verified in full for the multi-angle weighted cases.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Testing APS conjecture on regular graphs." pith.science (2026). https://pith.science/paper/AR5RL5ZX

@misc{pith2026250710050,
  author       = {Pith},
  title        = {Pith review of: Testing APS conjecture on regular graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AR5RL5ZX}},
  note         = {Machine review of arXiv:2507.10050}
}
read the original abstract

The maximum energy of the EPR model on a weighted graph is known to be upper-bounded by the sum of the total weight and the value of maximum-weight fractional matching~(MWFM). Recently, Apte, Parekh and Sud~(APS) conjecture that the bound could be strengthened by replacing MWFM with maximum weight matching~(MWM). Here we test this conjecture on a special class of regular graphs that Henning and Yeo constructed many years ago. On this class of regular graphs, MWMs achieve tight lower bounds. As for the maximum energy of the EPR model, we have recently devised a new algorithm called Fractional Entanglement Distribution~(FED) based on quasi-homogeneous fractional matchings, which could achieve rather high accuracy. Applying the FED algorithm to the EPR model on Henning-Yeo graphs, we could thus obtain energy as high as possible and matching value as low as possible, and then make high-precision tests of the APS conjecture. Nevertheless, our numerical results do not show any evidence that the APS conjecture could be violated.

Figures

Figures reproduced from arXiv: 2507.10050 by the authors.

Figure 1
Figure 1. For edge ij, the set T composes of all common neighbours of i and j. In one situation ⟨χ|ZiZj |χ⟩ could be greatly simplified, that is when all the edges incident to T are assigned identical rotation angles. Notice that we do not require the angles on the other edges of i and j to be the same. Therefore, we define K˜ ≡ K \ T, L˜ ≡ L \ T, (B1) and set ˜k = |K˜ |, ˜l = |L˜|. (B2) 18 [PITH_FULL_IMAGE:figures/full_fig_… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

33 extracted references · 25 canonical work pages

  1. [1]

    Take an arbitrary k-regular graph Xp, which could contain multi-edges

    work page

  2. [2]

    Quasi-Complete Graphs 19 References 21 I. INTRODUCTION For the classical Maximum Cut problem, we have the famous Goemans-Williamson algorithm based on semidefinite programming, which could achieve an approximation ratio at least .878 [1]. Quantum Maximum Cut (QMC) is the natural quantum lift of the classical problem, in which adja- cent qubits prefer anti...

    work page

  3. [3]

    Label the resulting graph by Gk p

    For each edge ofXp, insert a copyH u′,v′ k+1 of the quasi-complete graphH x,y k+1 in such a way: delete edge uv, add uu′ and vv ′. Label the resulting graph by Gk p. Obviously its order is |Gk p| = p(k2 + k + 2)/2. Also it is not difficult to prove that its maximum matching achieves the lower bound. Just delete the vertex set of Xp and apply the Tutte-Ber...

    work page

  4. [4]

    [https://iopscience.iop.org/article/10.1088/1367-2630/10/7/073013]

    Miguel Navascues, Stefano Pironio, and Antonio Acín, 2008, Convergent hierarchy of semidefinite programs characterizing the set of quantum correlations, New Journal of Physics 10, 073013, 2008. [https://iopscience.iop.org/article/10.1088/1367-2630/10/7/073013]

    doi:10.1088/1367-2630/10/7/073013 2008

  5. [5]

    Delete an arbitrary edge xy from the complete graph Kk+1, and get quasi-complete graphH x,y k+1

    work page

  6. [6]

    [https://arxiv.org/abs/2401.03616]

    Eunou Lee, Ojas Parekh, 2024, An improved Quantum Max Cut approximation via Maximum Match- ing, [ https://doi.org/10.4230/LIPIcs.ICALP.2024.105]. [https://arxiv.org/abs/2401.03616]

    arXiv 2024

  7. [7]

    Construct a bipartite graph T k p , such that one vertex set is V1 = {u1, u2, ..., up}, an- other set is V2 = {v1, v2, ..., vp(k−1)+1}, and choose the neighbours of each ui as N (ui) = {v(k−1)(i−1)+1, v(k−1)(i−1)+2..., v(k−1)(i−1)+k}

    work page

  8. [8]

    Delete the following edges to get a quasi-complete graph H wk+2 k+1 : H wk+2 k+2 = Kk+2 −   (k−3)/2[ i=0 {w2i+1w2i+2}   ∪ {wkwk+2, wk+1wk+2}

    Start with the complete graph Kk+2 with vertex set {w1, w2, ..., wk+2}. Delete the following edges to get a quasi-complete graph H wk+2 k+1 : H wk+2 k+2 = Kk+2 −   (k−3)/2[ i=0 {w2i+1w2i+2}   ∪ {wkwk+2, wk+1wk+2}. (35)

    work page

Show all 33 references
  1. [9]

    Then connect v with each xj

    For each vertex v of V2 with degree dv < k, make k − dv copies H xj k+2 of H wk+2 k+2 , where 1 ≤ j ≤ k − dv. Then connect v with each xj. 10 Denote the final graph as H k p . Its order is |H k p | = n = p(k3 − 3k) + k2 + 2k + 1. One can check that its maximum matching also ac...

  2. [10]

    Therefore, we choose one rotation angle θ1 for the internal edges of H x,y k+1, and θ2 for the remaining ones

    When k is even, we get one identical fraction for the internal edges of H x,y k+1, and another one the external edges. Therefore, we choose one rotation angle θ1 for the internal edges of H x,y k+1, and θ2 for the remaining ones

  3. [11]

    We assign θ1, θ2 and θ3 to them respectively

    When k is odd, we get three different matching fractions: one for the internal edges ofH x k+2, one for the external edges incident to H x k+2, and one for the other external ones. We assign θ1, θ2 and θ3 to them respectively. We then perform the remaining steps of the FED alg...

  4. [12]

    Fractional Entanglement Distribution

    obtains the same approximation ratio with a different quantum state, and will not be discussed here. B. FED algorithm Although the approximation ratio .809 obtained in [12] and [13] is much larger than those in previous studies, it seems not good enough for testing the APS con...

  5. [13]

    proves that this is half the gold ratio φ = (1 + √ 5)/2: r0 = φ 2 ≈ .809, (19) and the parameter κ is given by κ0 ≡ 1 2 ln φ ≈ .240. (20) With the energy ratio on individual edges, [13] then prove that the total energy could achieve the same approximation ratio r(ALMPS) ≡ ⟨χ|H...

  6. [14]

    Goemans and D.P

    M. Goemans and D.P. Williamson, 1995, Improved approximation algorithms for MAX-CUT and satisfiability problems using semidefinite programming, Journal of the ACM, 42 (1995), 1115-1145

    1995

  7. [16]

    Lasserre, 2002, An explicit equivalent positive semidefinite program for nonlinear 0-1 programs, SIAM J

    Jean B. Lasserre, 2002, An explicit equivalent positive semidefinite program for nonlinear 0-1 programs, SIAM J. on Optimization , 12(3):756¨C769, March 2002. [https://epubs.siam.org/doi/10.1137/S1052623400380079]

    2002 doi

  8. [17]

    Fernando GSL Brandão and Aram W Harrow, 2016, Product-state approximations to quantum states, Communications in Mathematical Physics 342(1):47¨C80, 2016

    2016

  9. [18]

    Wootters, 1999 Distributed Entanglement, Phys.Rev

    Valerie Coffman, Joydip Kundu, William K. Wootters, 1999 Distributed Entanglement, Phys.Rev. A61:052306,2000. [https://arxiv.org/abs/quant-ph/9907047]

    1999 arXiv

  10. [19]

    Anuj Apte, Ojas Parekh, James Sud, 2025, Conjectured Bounds for 2-Local Hamiltonians via Token Graphs, [https://arxiv.org/abs/2506.03441]

    2025 arXiv

  11. [20]

    Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, Juspreet Singh Sandhu, Stuart Wayland, 2024, Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians, [https://arxiv.org/abs/2410.15544]

    2024 arXiv

  12. [21]

    Sander Gribling, Lennart Sinjorgo, Renata Sotirov, 2025, Improved approximation ratios for the Quan- tum Max-Cut problem on general, triangle-free and bipartite graphs, [https://arxiv.org/abs/2504.11120]

    2025 arXiv

  13. [22]

    Henning, Anders Yeo, 2007, Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph, Graphs and Combinatorics 23:647¨C657 (2007)

    Michael A. Henning, Anders Yeo, 2007, Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph, Graphs and Combinatorics 23:647¨C657 (2007)

    2007

  14. [23]

    Nathan Ju, Ansh Nagda, 2025, Improved approximation algorithms for the EPR Hamiltonian, 15 [https://arxiv.org/abs/2504.10712]

    2025 arXiv

  15. [26]

    Tutte, 1947, The factorization of linear graphs, Journal of the London Mathematical Society , 22 (1947), 107¨C111

    W.T. Tutte, 1947, The factorization of linear graphs, Journal of the London Mathematical Society , 22 (1947), 107¨C111

    1947

  16. [27]

    Berge, 1958, Sur le couplage maximum d’ un graphe,Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences (Paris) Sér

    C. Berge, 1958, Sur le couplage maximum d’ un graphe,Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences (Paris) Sér . I Math. 247 (1958), 258¨C259

    1958

  17. [28]

    Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, John Wright, 2021, Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell’s inequality, [https://arxiv.org/abs/2111.01254]

    2021 arXiv

  18. [29]

    16 Appendix A: King Formulae First we repeat some definitions

    Subhash Khot, 2002, On the power of unique 2-prover 1-round games, In Proceedings of the 34th Annual ACM Symposium on Theory of Computing , pages 767¨C775, 2002. 16 Appendix A: King Formulae First we repeat some definitions. On a weighted graph G = {V, E, w}, the Hamiltonian o...

    2002

  19. [30]

    (A8) where K ≡ {k ∈ VG : k ∼ i, k̸= j}, L ≡ {l ∈ VG : l ∼ j, l̸= i}, (A9) and T ≡ {t ∈ VG : t ∼ i, t∼ j}

    gives the complete expressions in the general case: ⟨χ|QiPj|χ⟩ = sin 2 θij Y k∈K cos 2θik, (A6) ⟨χ|PiQj|χ⟩ = sin 2 θij Y l∈L cos 2θjl, (A7) ⟨χ|ZiZj|χ⟩ = X S⊂T,|S|even Y s∈S sin 2θis sin 2θsj Y k∈K\S cos 2θik Y l∈L\S cos 2θlj. (A8) where K ≡ {k ∈ VG : k ∼ i, k̸= j}, L ≡ {l ∈ VG...

  20. [31]

    Thus ⟨χ|ZiZj|χ⟩ = 1 2 1 + (cos2 2θ − sin2 2θ)n−2

    Complete Graphs On complete graphs, every other vertex is adjacent to bothi and j, so t = n−2, and ˜K = ˜L = ∅. Thus ⟨χ|ZiZj|χ⟩ = 1 2 1 + (cos2 2θ − sin2 2θ)n−2 . (B7)

  21. [32]

    H x,y k+1 for even k are very close to Kk+1, while H x k+2 for odd k are very close to Kk+2

    Quasi-Complete Graphs In the Henning-Yeo construction [4], lots of quasi-complete graphs H x,y k+1 and H x k+2 are used. H x,y k+1 for even k are very close to Kk+1, while H x k+2 for odd k are very close to Kk+2. Now we calculate (B6) for these two kinds of graphs. Let us fir...

  22. [33]

    [https://arxiv.org/abs/2209.02589]

    Robbie King, 2023, An Improved Approximation Algorithm for Quantum Max-Cut, Quantum 7, 1180 (2023). [https://arxiv.org/abs/2209.02589]

    2023 arXiv

  23. [34]

    Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, James Sud, 2025, Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings, [https://arxiv.org/abs/2504.15276]

    2025 arXiv

  24. [35]

    Wenxuan Tao, Fen Zuo, 2025, A Refined Algorithm For the EPR model, [https://arxiv.org/abs/2506.08547]

    2025 arXiv

  25. [36]

    Henning, Anders Yeo, 2007, Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph, Graphs and Combinatorics 23:647¨C657 (2007)

    Michael A. Henning, Anders Yeo, 2007, Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph, Graphs and Combinatorics 23:647¨C657 (2007). 21

    2007

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.