Conjectured Bounds for 2-Local Hamiltonians via Token Graphs

The gist The authors explain how 2-local Hamiltonians like Quantum MaxCut, XY, and EPR relate to the spectral radii of token graphs and conjecture new bounds for these radii based on properties of the graph G.

Graph Theory Perspective

The paper establishes a graph theory perspective by defining the k-th token graph Fk(G) as a simple graph whose vertices are k-tuples of V, where adjacency is determined by symmetric difference being an edge in G with corresponding edge weight we (Page 3). They then define key matrices: the Laplacian L(G) and signless Laplacian Q(G), and state the conjectures for unweighted graphs regarding the maximum eigenvalues of these matrices on token graphs (Page 4). These conjectures are: Conjecture 1. λmax (L(Fk (G))) ≤ m + k., Conjecture 2. λmax (Q (Fk (G))) ≤ m + k., Conjecture 3. λmax (A (Fk (G))) ≤ ½(m + k) and Conjecture 4. λmin (A (Fk (G))) ≥ −½(m + k). These conjectures are shown to imply bounds for all weighted graphs via Lemma 1, which relates them to the maximum weight matching Mk(G) as Conjecture 1 ⇒ λmax (L(Fk (G))) ≤ W(G) + Mk(G), etc. (Page 8).

Hamiltonian and Token Graph Equivalence

The core of the work is showing that the Hamiltonians QMC, XY, and EPR can be expressed as direct sums of matrices related to token graphs Fk(G) (Page 10). Specifically:

1. For QMC, HQMC(G) is equivalent to a direct sum over the Laplacian matrices L(Fk(G)) for 0 ≤ k ≤ n (Page 12).

2. For XY, HXY (G) is equivalent to a direct sum over scaled and shifted adjacency matrices W2I − A(Fk(G)) for 0 ≤ k ≤ n (Page 12).

3. For EPR, HEP R(G) is equivalent under unitary transformation to a direct sum over the signless Laplacian matrices Q(Fk(G)) for 0 ≤ k ≤ n (Page 13).

This equivalence immediately reveals that the maximum energy of QMC is at most that of EPR (Page 5), and it allows conjectures on spectral radii to be translated into combinatorial upper bounds for the maximum energies of these Hamiltonians (Page 5).

Implications for Approximation Ratios

The conjectured bounds on token graph spectra directly imply combinatorial upper bounds on the maximum energies of QMC, XY, and EPR (Lemma 13) (Page 7). These bounds are then used to augment convex relaxations used in existing approximation algorithms with matching-based constraints (Section 5.1) (Page 20). This augmentation allows polynomial-time algorithms to obey these spectral bounds, which in turn implies improved approximation ratios for QMC, XY, and EPR (Page 6). For instance, the analysis shows that Algorithm 3 augmented with the matching-based separation oracle obtains a 0.614-approximation for QMC (Corollary 10) (Page 23).

Physical Interpretation and Entanglement

The upper bounds on maximum eigenvalues have condensed matter interpretations as lower bounds on the ground state energy of corresponding physical systems by a sign flip and ignoring identity terms (Page 6). Furthermore, Conjecture 1 implies a new connection between pairwise concurrence and matchings: X(i,j)∈E wijcij ≤ M(G), which helps explain why matchings have played a critical role in recent approximation algorithms for QMC, EPR, and XY (Page 7).

Numerical Evidence and Further Conjectures

The conjectures were verified by checking all non-isomorphic unweighted graphs up to order ten and a suite of weighted graphs (Page 17). Numerical evaluation of approximation ratios achieved by Algorithm 3 also provides evidence that algorithms may perform better than the worst-case guarantees implied by the conjectures (Table 2) (Page 24). The authors also present additional numerical experiments, such as testing the maximum cut-based bound λmax (L(Fk (G))) ≤ W(G) + C(G)2 + k, which is stronger than Conjecture 1, and conjecture Conjecture 7: λmin (A (Fk (G))) ≥ −C(G) + Mk(G)2 for all G and all 1 ≤ k ≤ ⌊n/2⌋ (Page 39). The paper concludes by listing open problems, including proving Conjectures 1–6 and determining if any classical graph invariants yield the minimum value k for which λmax (L(Fk (G))) = λmax HQMC(G) (Page 25).

How it works

The proof of Lemma 13, which allows the reduction of proving statements on all graphs G to proving them on biconnected factor-critical graphs F, relies on showing that if a bound is violated for G, it must be violated by a subgraph in F (Page 18). This reduction is crucial for inductive proofs (Page 45). The proof of Conjecture 1 ⇒ λmax HQMC(G) ≤ W(G) + M(G) involves contradiction by assuming the opposite and showing that the resulting minimal counterexample must violate one of the LP constraints in Lemma 20 (Page 37).

Final Summary

The paper provides a comprehensive framework connecting graph theory, specifically token graphs, to quantum local Hamiltonians, establishing conjectures on their spectral radii that yield tight combinatorial bounds on maximum energies for QMC, XY, and EPR (Page 4). These bounds are then used to design efficient approximation algorithms that achieve state-of-the-art approximation ratios (Page 6). The work demonstrates how spectral properties of token graphs allow for a fully classical characterization of QMA-complete problems like MaxCut (Page 25). The ultimate goal is to tighten the analysis of existing algorithms and determine if classical graph invariants can yield the minimum value k for which certain spectral equalities hold (Page 25).

1. Improve approximation algorithms for QMC, XY, and EPR by incorporating matching-based constraints into convex relaxations, allowing polynomial-time solutions to obey tighter spectral bounds: We introduce matching-augmented convex relaxations that iteratively add constraints derived from the matching polytope to the underlying convex relaxation. This enables an efficient algorithm to find augmented SDP solutions obeying the W(H) + M(H) bound for any subgraph H of G.

2. Enhance state preparation capabilities for quantum Hamiltonians by leveraging eigenvector properties of token graphs: We show how to efficiently augment any polynomial-time solvable convex relaxation for the 2-local Hamiltonian problems with additional matching-based constraints (Section 5.1). This allows the preparation of a tensor product of 1 and 2-qubit states with approximation guarantees, such as the 5/8 = 0.625-approximation for QMC via Algorithm 3 augmented with a matching-based separation oracle.

3. Develop new algorithmic primitives for EPR by utilizing optimal states characterized by positive amplitudes in the Pauli-Y basis: For any connected graph G, there exists a quantum state χ⟩ satisfying TrHEP R(G) χ⟩ = λmax HEP R (G), ⟨zχ⟩ ∈ R+, ∀ z⟩ ∈ [+i⟩, −i⟩]⊗n. This leads to the efficient preparation of a quantum Dicke state which achieves an energy bound of Dn/k = (W(G)/n(n-1) for n even, W(G)/(n+(n-1) for n odd).

4. Improve the analysis and bounds on the maximum energy of QMC, XY, and EPR by translating spectral conjectures into combinatorial bounds: "We show that by leveraging the equivalence between commonly-studied 2-local Hamiltonians and eigenspectra of token graphs, the conjectures also imply combinatorial upper bounds on the maximum energies of QMC, XY, and EPR (Lemma 13)." This provides tighter analysis for approximation ratios derived from existing algorithms.

5. Establish new entanglement bounds by connecting pairwise concurrence to matchings: Under Conjecture 1, Equation (6) implies a new connection between pairwise concurrence and matchings: X(i,j)∈E wij cij ≤ M(G), (10). This suggests that matchings have played a critical role in recent approximation algorithms for QMC, EPR, and XY.

We explain how the maximum energy of the Quantum MaxCut, XY, and EPR Hamiltonians on a graph G are related to the spectral radii of the token graphs of G. From numerical study, we conjecture new bounds for these spectral radii based on properties of G. We show how these conjectures tighten the analysis of existing algorithms, implying state-of-the-art approximation ratios for all three Hamiltonians. Our conjectures also provide simple combinatorial bounds on the ground state energy of the antiferromagnetic Heisenberg model, which we prove for bipartite graphs.