arXiv:2506.03441

Conjectured Bounds for 2-Local Hamiltonians via Token Graphs

Anuj Apte, Ojas Parekh, James Sud

Published Jun 3, 2025• 0 citations

Abstract

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.

DOI: 10.48550/arxiv.2506.03441

Related papers

Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs

Kunal Marwaha, Adrian She, James Sud

arXiv:2412.15147Dec 19, 20240 citations

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut

Ainesh Bakshi, Arpon Basu, Pravesh Kothari +1 more

quant-pharXiv:2605.14994May 15, 20260 citations

Improved approximation algorithms for the EPR Hamiltonian

Nathan Ju, Ansh Nagda

arXiv:2504.10712Apr 14, 20250 citations

Graph-Theoretic Formulation of Hamiltonian and Ground-State Sign Structures in Heisenberg Antiferromagnets

Mahmud Ashraf Shamim, Md Moshiur Rahman Raj, Mohamed Hibat-Allah +3 more

cond-mat.str-elCross-listedarXiv:2602.04943Feb 5, 20260 citations

Beyond Product State Approximations for a Quantum Analogue of Max Cut

Anurag Anshu, Gosset, David, Karen J. Morenz

arXiv:2003.14394Leibniz international proceedings in informaticsJan 1, 202011 citations

Efficient quantum algorithm for Heisenberg spin systems

Sergey Bravyi, David Gosset, Yinchen Liu +1 more

quant-pharXiv:2607.14401Jul 17, 20260 citations

arXiv:2506.03441

Conjectured Bounds for 2-Local Hamiltonians via Token Graphs

Anuj Apte, Ojas Parekh, James Sud

Published Jun 3, 2025• 0 citations

arXiv HTML PDF

Abstract

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.

DOI: 10.48550/arxiv.2506.03441

Related papers

Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs

Kunal Marwaha, Adrian She, James Sud

We design two variational algorithms to optimize specific 2-local Hamiltonians defined on graphs. Our algorithms are inspired by the Quantum Approximate Optimization Algorithm. We develop formulae to analyze the energy achieved by these algorithms with high probability over random regular graphs in the infinite-size limit, using techniques from [arXiv:2110.14206]. The complexity of evaluating these formulae scales exponentially with the number of layers of the algorithms, so our numerical evaluation is limited to a small constant number of layers. We compare these algorithms to simple classical approaches and a state-of-the-art worst-case algorithm. We find that the symmetry inherent to these specific variational algorithms presents a major \emph{obstacle} to successfully optimizing the Quantum MaxCut (QMC) Hamiltonian on general graphs. Nonetheless, the algorithms outperform known methods to optimize the EPR Hamiltonian of [arXiv:2209.02589] on random regular graphs, and the QMC Hamiltonian when the graphs are also bipartite. As a special case, we show that with just five layers of our algorithm, we can already prepare states within 1.62% error of the ground state energy for QMC on an infinite 1D ring, corresponding to the antiferromagnetic Heisenberg spin chain.We design two variational algorithms to optimize specific 2-local Hamiltonians defined on graphs. Our algorithms are inspired by the Quantum Approximate Optimization Algorithm. We develop formulae to analyze the energy achieved by these algorithms with high probability over random regular graphs in the infinite-size limit, using techniques from [arXiv:2110.14206]. The complexity of evaluating these formulae scales exponentially with the number of layers of the algorithms, so our numerical evaluation is limited to a small constant number of layers. We compare these algorithms to simple classical approaches and a state-of-the-art worst-case algorithm. We find that the symmetry inherent to these specific variational algorithms presents a major \emph{obstacle} to successfully optimizing the Quantum MaxCut (QMC) Hamiltonian on general graphs. Nonetheless, the algorithms outperform known methods to optimize the EPR Hamiltonian of [arXiv:2209.02589] on random regular graphs, and the QMC Hamiltonian when the graphs are also bipartite. As a special case, we show that with just five layers of our algorithm, we can already prepare states within 1.62% error of the ground state energy for QMC on an infinite 1D ring, corresponding to the antiferromagnetic Heisenberg spin chain.

arXiv:2412.15147Dec 19, 20240 citations

Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut

Ainesh Bakshi, Arpon Basu, Pravesh Kothari +1 more

We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level $k$ Kikuchi graph of any graph $G$ with $m$ edges is at most $m+k$ . This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of $5/8$ for Quantum Max Cut and $5/7$ for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of $0.614$ for Quantum Max Cut and $0.674$ for the XY Hamiltonian. Finally, we also make modest progress on Brouwer's conjecture and improve Lew's bound on the sum of the top- $k$ eigenvalues of a Graph Laplacian.We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level $k$ Kikuchi graph of any graph $G$ with $m$ edges is at most $m+k$. This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of $5/8$ for Quantum Max Cut and $5/7$ for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of $0.614$ for Quantum Max Cut and $0.674$ for the XY Hamiltonian. Finally, we also make modest progress on Brouwer's conjecture and improve Lew's bound on the sum of the top-$k$ eigenvalues of a Graph Laplacian.

quant-pharXiv:2605.14994May 15, 20260 citations

Improved approximation algorithms for the EPR Hamiltonian

Nathan Ju, Ansh Nagda

The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King (arXiv:2209.02589). We introduce a polynomial time $\frac{1+\sqrt{5}}{4}\approx 0.809$ -approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian, improving upon the previous state of the art of $0.72$ (arXiv:2410.15544). As a special case, this also implies a $\frac{1+\sqrt{5}}{4}$ -approximation for Quantum Max Cut on bipartite instances, improving upon the approximation ratio of $3/4$ that one can infer in a relatively straightforward manner from the work of Lee and Parekh (arXiv:2401.03616).The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King (arXiv:2209.02589). We introduce a polynomial time $\frac{1+\sqrt{5}}{4}\approx 0.809$-approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian, improving upon the previous state of the art of $0.72$ (arXiv:2410.15544). As a special case, this also implies a $\frac{1+\sqrt{5}}{4}$-approximation for Quantum Max Cut on bipartite instances, improving upon the approximation ratio of $3/4$ that one can infer in a relatively straightforward manner from the work of Lee and Parekh (arXiv:2401.03616).

arXiv:2504.10712Apr 14, 20250 citations

Graph-Theoretic Formulation of Hamiltonian and Ground-State Sign Structures in Heisenberg Antiferromagnets

Mahmud Ashraf Shamim, Md Moshiur Rahman Raj, Mohamed Hibat-Allah +3 more

We study Heisenberg antiferromagnets through a graph-theoretic representation of their Hamiltonians. In the computational basis of a fixed-magnetization sector, the Heisenberg Hamiltonian equals a constant minus the weighted Laplacian of a graph whose vertices are spin configurations and whose edges connect configurations related by exchanging two antiparallel spins on a lattice bond. We call this graph the Hilbert graph (HG) which is isomorphic to the token graph of the lattice over which the Hamiltonian is defined. The exact ground-state energy is then determined by the largest eigenvalue of the HG Laplacian, which is the spectral relaxation of weighted Max-Cut on the HG. With the amplitudes fixed, the phase-dependent part of the variational energy defines an antiferromagnetic classical XY model on the HG, with couplings set by the amplitudes. Restricting the variational state to be real, i.e., restricting its phases to $\{0,π\}$ , reduces the fixed-amplitude energy minimization to solving an antiferromagnetic Ising model and hence a weighted Max-Cut on the HG. When the weights are generated from non-degenerate ground-state amplitudes, the optimal phases give the ground-state sign structure which can be recovered from the weights in time polynomial in the size of the HG. On the Hamiltonian side, a diagonal sign transformation removes all positive off-diagonal matrix elements if and only if the HG is bipartite, which reproduces the Marshall sign rule on bipartite lattices through the graph two-coloring problem; otherwise, the minimal remaining positive weight equals the sum of HG edge weights left uncut by the Max-Cut. This graph formulation establishes a common framework for understanding wave function sign structure, Hamiltonian stoquasticity, non-convexity of phase optimization in variational Monte Carlo, and the average sign in quantum Monte Carlo.We study Heisenberg antiferromagnets through a graph-theoretic representation of their Hamiltonians. In the computational basis of a fixed-magnetization sector, the Heisenberg Hamiltonian equals a constant minus the weighted Laplacian of a graph whose vertices are spin configurations and whose edges connect configurations related by exchanging two antiparallel spins on a lattice bond. We call this graph the Hilbert graph (HG) which is isomorphic to the token graph of the lattice over which the Hamiltonian is defined. The exact ground-state energy is then determined by the largest eigenvalue of the HG Laplacian, which is the spectral relaxation of weighted Max-Cut on the HG. With the amplitudes fixed, the phase-dependent part of the variational energy defines an antiferromagnetic classical XY model on the HG, with couplings set by the amplitudes. Restricting the variational state to be real, i.e., restricting its phases to $\{0,π\}$, reduces the fixed-amplitude energy minimization to solving an antiferromagnetic Ising model and hence a weighted Max-Cut on the HG. When the weights are generated from non-degenerate ground-state amplitudes, the optimal phases give the ground-state sign structure which can be recovered from the weights in time polynomial in the size of the HG. On the Hamiltonian side, a diagonal sign transformation removes all positive off-diagonal matrix elements if and only if the HG is bipartite, which reproduces the Marshall sign rule on bipartite lattices through the graph two-coloring problem; otherwise, the minimal remaining positive weight equals the sum of HG edge weights left uncut by the Max-Cut. This graph formulation establishes a common framework for understanding wave function sign structure, Hamiltonian stoquasticity, non-convexity of phase optimization in variational Monte Carlo, and the average sign in quantum Monte Carlo.

cond-mat.str-elCross-listedarXiv:2602.04943Feb 5, 20260 citations

Beyond Product State Approximations for a Quantum Analogue of Max Cut

Anurag Anshu, Gosset, David, Karen J. Morenz

We consider a computational problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits located at the vertices of a graph. Previous work has shed light on this problem's approximability by product states. For any instance of this problem the maximum energy attained by a product state is lower bounded by the Max Cut of the graph and upper bounded by the standard Goemans-Williamson semidefinite programming relaxation of it. Gharibian and Parekh described an efficient classical approximation algorithm for this problem which outputs a product state with energy at least 0.498 times the maximum eigenvalue in the worst case, and observe that there exist instances where the best product state has energy 1/2 of optimal. We investigate approximation algorithms with performance exceeding this limitation which are based on optimizing over tensor products of few-qubit states and shallow quantum circuits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case. We also show that for any instance defined by a 3- or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation).We consider a computational problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits located at the vertices of a graph. Previous work has shed light on this problem's approximability by product states. For any instance of this problem the maximum energy attained by a product state is lower bounded by the Max Cut of the graph and upper bounded by the standard Goemans-Williamson semidefinite programming relaxation of it. Gharibian and Parekh described an efficient classical approximation algorithm for this problem which outputs a product state with energy at least 0.498 times the maximum eigenvalue in the worst case, and observe that there exist instances where the best product state has energy 1/2 of optimal. We investigate approximation algorithms with performance exceeding this limitation which are based on optimizing over tensor products of few-qubit states and shallow quantum circuits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case. We also show that for any instance defined by a 3- or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation).

arXiv:2003.14394Leibniz international proceedings in informaticsJan 1, 202011 citations

Efficient quantum algorithm for Heisenberg spin systems

Sergey Bravyi, David Gosset, Yinchen Liu +1 more

We consider a broad family of Heisenberg-type quantum spin systems that were studied by Suzuki and Fisher in 1971. This family includes, for example, the Heisenberg antiferromagnet on any bipartite graph. The ground and Gibbs states of these models are Lee-Yang tensors with radius 1: they are associated with multilinear polynomials that possess an extraordinary zero-freeness property inside the unit polydisk in the complex plane. For each Hamiltonian in this family we show that the spectral gap between the first-excited and ground-state energies is lower bounded by $2μ$ , where $μ$ is the magnetic field along the $Z$ direction. Using this result we obtain an efficient quantum adiabatic algorithm for the ground energy of any model in this family. The proof is based on a new inequality that relates the spectral gap of a positive semidefinite operator to its Lee-Yang radius -- a quantitative strengthening of prior work of the authors that may find applications elsewhere.We consider a broad family of Heisenberg-type quantum spin systems that were studied by Suzuki and Fisher in 1971. This family includes, for example, the Heisenberg antiferromagnet on any bipartite graph. The ground and Gibbs states of these models are Lee-Yang tensors with radius 1: they are associated with multilinear polynomials that possess an extraordinary zero-freeness property inside the unit polydisk in the complex plane. For each Hamiltonian in this family we show that the spectral gap between the first-excited and ground-state energies is lower bounded by $2μ$, where $μ$ is the magnetic field along the $Z$ direction. Using this result we obtain an efficient quantum adiabatic algorithm for the ground energy of any model in this family. The proof is based on a new inequality that relates the spectral gap of a positive semidefinite operator to its Lee-Yang radius -- a quantitative strengthening of prior work of the authors that may find applications elsewhere.

quant-pharXiv:2607.14401Jul 17, 20260 citations

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 prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level

k

Kikuchi graph of any graph

G

with

m

edges is at most

m+k

. This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of

5/8

for Quantum Max Cut and

5/7

for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of

0.614

for Quantum Max Cut and

0.674

for the XY Hamiltonian. Finally, we also make modest progress on Brouwer's conjecture and improve Lew's bound on the sum of the top-

k

eigenvalues of a Graph Laplacian.

The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King (arXiv:2209.02589). We introduce a polynomial time

\frac{1+\sqrt{5}}{4}\approx 0.809

-approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian, improving upon the previous state of the art of

0.72

(arXiv:2410.15544). As a special case, this also implies a

\frac{1+\sqrt{5}}{4}

-approximation for Quantum Max Cut on bipartite instances, improving upon the approximation ratio of

3/4

that one can infer in a relatively straightforward manner from the work of Lee and Parekh (arXiv:2401.03616).

\{0,π\}

, reduces the fixed-amplitude energy minimization to solving an antiferromagnetic Ising model and hence a weighted Max-Cut on the HG. When the weights are generated from non-degenerate ground-state amplitudes, the optimal phases give the ground-state sign structure which can be recovered from the weights in time polynomial in the size of the HG. On the Hamiltonian side, a diagonal sign transformation removes all positive off-diagonal matrix elements if and only if the HG is bipartite, which reproduces the Marshall sign rule on bipartite lattices through the graph two-coloring problem; otherwise, the minimal remaining positive weight equals the sum of HG edge weights left uncut by the Max-Cut. This graph formulation establishes a common framework for understanding wave function sign structure, Hamiltonian stoquasticity, non-convexity of phase optimization in variational Monte Carlo, and the average sign in quantum Monte Carlo.

2μ

, where

μ

is the magnetic field along the

Z

direction. Using this result we obtain an efficient quantum adiabatic algorithm for the ground energy of any model in this family. The proof is based on a new inequality that relates the spectral gap of a positive semidefinite operator to its Lee-Yang radius -- a quantitative strengthening of prior work of the authors that may find applications elsewhere.