Conjectured Bounds for 2-Local Hamiltonians via Token Graphs
Anuj Apte, Ojas Parekh, James Sud · 2025
Read Conjectured Bounds for 2-Local Hamiltonians via Token Graphs by Anuj Apte, Ojas Parekh, James Sud (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-03441.txt.
Introduction
Anuj Apte, Ojas Parekh, and James Sud link hard quantum energy problems to the spectra of token graphs. Their 2025 paper studies three energy models placed on a graph. Each model asks for the highest or lowest energy state of a quantum system. Token graphs are built from a base graph by tracking groups of tokens on its points, and their spectra carry the key values.
Number tests lead the trio to guess new bounds for those spectra, based on plain traits of the base graph. The guesses tighten the math behind known algorithms for all three models. As a result, the promised accuracy of those algorithms reaches the best known level. The guesses also give simple bounds for a classic magnetism model. The team proves those bounds for graphs that split into two camps.
Catalog record
| CREATOR | Anuj Apte, Ojas Parekh, James Sud |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-03441
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Conjectured Bounds for 2-Local Hamiltonians via Token Graphs Anuj Apte, Ojas Parekh, James Sud Abstract We explain how the maximum energy of the Quantum MaxCut, XY, and EPR Hamiltonians on a graph G G are related to the spectral radii of the token graphs of G G . From numerical study, we conjecture new bounds for these spectral radii based on properties of G 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. 1 Introduction Finding ground states of local Hamiltonians is a central problem in quantum computing [ KSV02 ] . Certain well-studied Hamiltonians have been shown to connect to combinatorial graph-theoretic objects [ Rud02 , Osb06 ] , enabling the study of of these Hamiltonians via techniques from graph theory. In this work, we continue this study by investigating certain 2 -local Hamiltonians via their connection to token graphs [ Fab+12 ] . As our results concern both quantum computing and spectral graph theory, we provide two introductions. The graph theoretic introduction presents our conjectures on the eigenspectra of token graphs. The quantum computational introduction presents the implications of these conjectures for 2 -Local Hamiltonians and approximation algorithms. Each introduction is largely self-contained, and the reader can choose whichever sections they prefer. A third perspective, which we do not discuss here, arises from the representation theory of the symmetric group (see e.g. [ Wat+24 , Tak+23 ] ). A graph theory perspective: Let G(V,E,w) be a simple graph with vertex set V=\left\{1,2,\ldots,n\right\} , edge set E and positive edge weights w:E\rightarrow\mathbb{R}_{+} . For an integer 1\leq k\leq n , the k -th token graph F_{k}(G) of G is defined as the simple graph whose vertex set is the \binom{n}{k} k -tuples of V , where vertices A , B are adjacent if and only if their symmetric difference is a pair (a,b) such that a\in A , b\in B , and (a,b)\in E , with corresponding edge weight w_{AB}=w_{e} . Token graphs were introduced under the names k-tuple vertex graphs [ Joh88 ] , symmetric k-th power graphs [ Aud+07 ] , and k-tuple vertex graphs [ ALL02 ] . Token graphs are also special cases of Kikuchi graphs ( [ Man24 , Tre24 ] ), defined with respect to uniform hypergraphs. Kikuchi graphs were originally introduced by [ WAM19 ] under the name symmetric difference matrices . Token graphs were introduced under their current name in [ Fab+12 ] . The phrase “token graph” corresponds to the intuition of placing k indistinguishable tokens on distinct vertices of the graph — yielding \binom{n}{k} token configurations — with configurations being adjacent if they can be obtained from each other by moving a single token along an edge in the graph. Note that F_{k}(G)\cong F_{n-k}(G) , so it suffices to consider 1\leq k\leq{\left\lfloor n/2\right\rfloor} . Let A(G) and D(G) denote the adjacency and degree matrix of a weighted graph G . Then, let L(G)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}D(G)-A(G) and Q(G)\stackrel{{\scriptstyle\mathrm{\scriptscriptstyle def}}}{{=}}D(G)+A(G) denote the Laplacian and signless Laplacian matrix of G . Let \lambda_{max}\left(\cdot\right) , \lambda_{min}\left(\cdot\right) , and \mathrm{eigs}\left(\cdot\right) denote the maximum, minimum, and set of unique eigenvalues of a matrix, respectively. We are interested in studying the eigenspectra of A(F_{k}(G)) , L(F_{k}(G)) and Q(F_{k}(G)) . These spectra have been the object of much study [ Ala+91 , Rud02 , Aud+07 , JGL07 , BP09 , AIP10 , Fab+12 , Dal+21 , Rey+23 , RDF24 , BV24 , Lew24 , Son+24 ] . However, these studies are limited to the case of unweighted graphs, and we are not aware of current results for the spectra of the signless Laplacian. For an unweighted graph G , let m denote the number of edges. For all unweighted graphs G and for all 1\leq k\leq{\left\lfloor n/2\right\rfloor} , we conjecture Conjecture 1 . \lambda_{max}\left(L\left(F_{k}\left(G\right)\right)\right)\leq m+k . Conjecture 2 . \lambda_{max}\left(Q\left(F_{k}\left(G\right)\right)\right)\leq m+k . Conjecture 3 . \lambda_{max}\left(A\left(F_{k}\left(G\right)\right)\right)\leq\frac{1}{2}\left(m+k\right) . Conjecture 4 . \lambda_{min}\left(A\left(F_{k}\left(G\right)\right)\right)\geq-\frac{1}{2}\left(m+k\right) . For an arbitrary graph G , let W(G) be the sum over edge weights \sum_{e\in E}w_{e} . Let M_{k}(G) be the weight of the maximum weight matching of G that consists of at most k edges. We show that the above conjectures imply bounds for all weighted graphs: Lemma 1 . For all weighted graphs G and all 1\leq k\leq{\left\lfloor n/2\right\rfloor} 1 \displaystyle\implies\lambda_{max}\left(L\left(F_{k}\left(G\right)\right)\right)\leq W(G)+M_{k}(G)\,, (1) 2 \displaystyle\implies\lambda_{max}\left(Q\left(F_{k}\left(G\right)\right)\right)\leq W(G)+M_{k}(G)\,, (2) 3 \displaystyle\implies\lambda_{max}\left(A\left(F_{k}\left(G\right)\right)\right)\leq\frac{1}{2}\left(W(G)+M_{k}(G)\right)\,, (3) 4 \displaystyle\implies\lambda_{min}\left(A\left(F_{k}\left(G\right)\right)\right)\geq-\frac{1}{2}\left(W(G)+M_{k}(G)\right)\,. (4) We also analyze the relationship between the spectra of token graphs for different k . It is shown in [ Dal+21 ] that the spectrum of L(F_{k}(G)) is contained in the spectrum of L(F_{k+1}(G)) , i.e. \mathrm{eigs}\left(L(F_{k}(G))\right)\subseteq\mathrm{eigs}\left(L(F_{k+1}(G))\right) . However, this is not true for the signless Laplacian and adjacency matrix. This fact was known for the adjacency matrix, and we provide a counterexample for the signless Laplacian. In contrast, we do observe containment of maximum eigenvalues, and for all G and 1\leq k<{\left\lfloor n/2\right\rfloor} we conjecture Conjecture 5 . \lambda_{max}\left(Q\left(F_{k}\left(G\right)\right)\right)\leq\lambda_{max}\left(Q\left(F_{k+1}\left(G\right)\right)\right) . Conjecture 6 . \lambda_{max}\left(A\left(F_{k}\left(G\right)\right)\right)\leq\lambda_{max}\left(A\left(F_{k+1}\left(G\right)\right)\right) . 6 also appears in [ RDF24 , Conjecture 3.3] . We disprove a corresponding conjecture for the minimum eigenvalue of the adjacency matrix by finding a counterexample where \lambda_{min}\left(A\left(F_{k-1}\left(G\right)\right)\right)\ngeq\lambda_{min}\left(A\left(F_{k}\left(G\right)\right)\right) . All the presented conjectures were verified by checking all non-isomorphic unweighted graphs and a suite of weighted graphs, both up to order ten. Our code is available at [ AS25 ] . A quantum perspective: A central task in quantum computation is to compute the maximum energy of local Hamiltonians. This is not an easy task: even for 2 -local Hamiltonians, deciding if the maximum energy is above some threshold is {\mathsf{QMA}} -hard [ KKR05 , PM15 ] . In this work, we study three specific families of 2 -local Hamiltonians defined on arbitrary weighted graphs. The first two were introduced as Quantum MaxCut (QMC) and the XY Hamiltonian (XY) in [ GP19 ] . The minimization versions of these problems have been studied as the antiferromagnetic quantum Heisenberg X\!X\!X_{1/2} and XY_{1/2} model in statistical mechanics. The third problem is the EPR Hamiltonian (EPR), recently introduced in [ Kin23 ] . The minimization version of EPR is the ferromagnetic quantum Heisenberg X\!X\!Z_{1/2} model in statistical mechanics. While QMC and XY are {\mathsf{QMA}} -complete, EPR is in {\mathsf{StoqMA}} [ PM15 ] . For these Hamiltonians, a key measure of algorithm performance is the approximation ratio \alpha , defined as the minimum ratio between the energy achieved by the algorithm and the maximum possible energy over all graphs \alpha=\min_{G}\,\frac{ALG(G)}{\lambda_{max}(H(G))}\;. (5) Importantly, this ratio depends both on the algorithm’s performance and our knowledge of the maximum energy. There are two approaches to improving approximation ratios: developing better algorithms that achieve higher energies, and establishing tighter upper bounds on the maximum energy. In this work, we focus primarily on the latter approach, showing how improved upper bounds on maximum energies directly yield better approximation ratios even without changing the underlying algorithms. There has been a recent surge in research aimed at finding efficient approximation algorithms for QMC, XY, and EPR [ GP19 , AGM20 , Ans+21 , PT22 , Lee22 , Kin23 , LP24