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

Mahmud Ashraf Shamim; Md Moshiur Rahman Raj; Mohamed Hibat-Allah; Ruy Fabila-Monroy; Nobuchika Okada; Paulo T. Araujo

cond-mat.str-elFeb 4, 2026

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

Authors: Mahmud Ashraf Shamim, Md Moshiur Rahman Raj, Mohamed Hibat-Allah, Ruy Fabila-Monroy, Nobuchika Okada, Paulo T. Araujo

Organizations: Department of Physics and Astronomy, University of Alabama, Tuscaloosa, 35487, Alabama, USA. · Department of Physics, University of Rajshahi, P.O. Box 6205, Rajshahi, Bangladesh. · Department of Applied Mathematics, University of Waterloo, Ontario Canada N2L 3G1 · Vector Institute, Toronto, Ontario, M5G 0C6, Canada

Abstract

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.

Figures & tables

Figure 1: Schematic representation of the mapping from a physical lattice to its HG and the associated spectrally relaxed Max-Cut . (a)

J_{1}

–

J_{2}

HAF on a six-site chain with open boundary conditions. (b) The zero-magnetization computational basis, consisting of twenty spin configurations. (c) The corresponding HG is constructed from the off-diagonal matrix elements of the

J_{1}

–

J_{2}

Hamiltonian, with the adjacency matrix in Eq. ( 15 ). (d) The same HG with each edge carrying its coupling weight

J_{r}/2

from Eq. ( 16 ) and each vertex carrying a binary variable

s_{\sigma}=\pm 1

. A candidate weighted cut is shown as the dashed yellow curve. (e) The GS computation as the spectral relaxation of the Max-Cut in (d), in which each

s_{\sigma}

is replaced by

\psi_{\sigma}s_{\sigma}

. With the GS amplitudes

\psi_{\sigma}

held fixed, each edge carries the amplitude-dressed weight of Eq. ( 45 ) and each vertex carries a binary phase

s_{\sigma}=e^{i\phi_{\sigma}}

\phi_{\sigma}\in\{0,\pi\}

. Minimizing the energy is then equivalent to maximizing the total dressed weight of the cut edges; the black dashed curve shows a candidate cut. Fixing the amplitudes to their GS values thus turns the sign optimization into the phase reconstruction problem ( PRP ).

Lattice	Size	$\|\mathcal{V}\|$	$J_{2}/J_{1}$	$\beta$	$N_{\triangle}$	$\|\mathcal{E}\|$	$\beta$	$N_{\triangle}$	$\|\mathcal{E}\|$
				PBC			OBC
Chain	$16$	$12{,}870$	zero	$1.00$	$0$	$54{,}912$	$1.00$	$0$	$51{,}480$
Chain	$16$	$12{,}870$	non-zero	$0.51$	$54{,}912$	$109{,}824$	$0.51$	$48{,}048$	$99{,}528$
Square	$4\times 4$	$12{,}870$	zero	$1.00$	$0$	$109{,}824$	$1.00$	$0$	$82{,}368$
Square	$4\times 4$	$12{,}870$	non-zero	$0.50$	$219{,}648$	$219{,}648$	$0.50$	$123{,}552$	$144{,}144$
Triangular	$4\times 4$	$12{,}870$	zero	$0.50$	$109{,}824$	$164{,}736$	$0.50$	$61{,}776$	$113{,}256$

Table 1: Hilbert graph diagnostics under periodic (PBC) and open (OBC) boundary conditions for the

J_{1}

–

J_{2}

HAF on three lattices: the

16

-site chain, the

4\times 4

square, and the

4\times 4

triangular lattice.

N_{\triangle}(\Gamma_{N/2})

is the number of triangles in the HG, Eq. ( 37 ), and

\beta

is the Estrada bipartivity index, Eq. ( 38 ).

Figure 2: Spectral relaxation of the discrete Max-Cut problem on the one-magnon HG of a triangle. (a) A single up spin on the three-site antiferromagnetic lattice. (b) In the one-magnon sector, the HG is a triangle,

\Gamma_{1}(G)\cong G

, with edge weight

J/2

. (c) The binary signs

x_{\sigma}=\pm 1

form the eight vertices of the Boolean cube. The six red vertices give the maximum cuts of the triangle, while the two white vertices do not cut any edge. (d) Spectral relaxation replaces these eight discrete vectors by the sphere

\lVert\mathbf{x}\rVert^{2}=3

. The cube is retained in gray to show that the original sign assignments remain inside the relaxed space. The blue circle marks where the maximum is attained,

\sum_{\sigma}x_{\sigma}=0

, which no cube corner reaches.

Figure 3: Left: A

2\times 2

open boundary square lattice NN HAF. Right: The corresponding bipartite HG,

K_{2,4}

, in the zero magnetization sector; spin configurations as in Fig. 1 . The dashed line is the cut separating the two Néel configurations (orange) from the rest (green). Because the HG is bipartite, this cut contains every edge: the phase assignment

\phi_{\sigma}=\pi

on one side and

\phi_{\sigma}=0

on the other satisfies PEC on all edges simultaneously, saturating the edgewise bound and attaining

E_{\ell,q}=-\sum_{\{\sigma,\tau\}\in\mathcal{E}_{\ell}}(w_{\ell})_{\sigma\tau}

. The Max-Cut is independent of the edge weights for any bipartite HG.

Figure 4: One-magnon HG of the

4\times 4

square-lattice

J_{1}

–

J_{2}

HAF with open boundaries. (Left) The physical lattice, with NN bonds

J_{1}

shown in gray and NNN bonds

J_{2}

in orange. (Middle) The one-magnon basis states. Each state

\ket{i}

contains one up spin at site

i

, shown in red, with all remaining spins down. (Right) HFs move the up spin along the

J_{1}

and

J_{2}

bonds, reproducing the physical connectivity giving

\Gamma_{1}(G)\cong G

Figure 5: Comparison of discrete phases, Rank-2 relaxation, and the Goemans-Williamson relaxation. Center: the original discrete phase variable is restricted to the Ising values

s_{\sigma}=e^{i\phi_{\sigma}}\in\mathbb{Z}_{2}

, with

\phi_{\sigma}=0

\pi

. Left: the Rank-2 relaxation promotes the sign variable to a continuous phase

s_{\sigma}=e^{i\phi_{\sigma}}\in U(1)

, so that the discrete product

s_{\sigma}s_{\tau}

is relaxed to the continuous edge correlation

\cos\Phi_{\sigma\tau}

, where

\Phi_{\sigma\tau}=\phi_{\sigma}-\phi_{\tau}

. The shaded half disk marks phase differences

\Phi_{\sigma\tau}

(not absolute phases) satisfying

\cos\Phi_{\sigma\tau}<0

, which lower the off-diagonal energy contribution

E_{q}

defined in Eq. ( 44 ). Right: the Goemans-Williamson relaxation lifts the Ising variable to a unit vector

\mathbf{v}_{\sigma}\in S^{d-1}

and replaces

s_{\sigma}s_{\tau}

\mathbf{v}_{\sigma}\cdot\mathbf{v}_{\tau}

. The hyperplane separates the sphere into two hemispheres, corresponding to the two signs after rounding.

Lattice	Size	Method	$0.0$	$0.1$	$0.2$	$0.3$	$0.4$	$0.5$	$0.6$	$0.7$	$0.8$	$0.9$	$1.0$
			$J_{2}/J_{1}$
Chain	$16$	GW	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000
Chain	$16$	Rank-2	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000
Square	$4\times 4$	GW	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000
Square	$4\times 4$	Rank-2	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000
Triangular	$4\times 4$	GW	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000	1.000

Table 2: Quality of the GW algorithm implemented via BM factorization with

k=\lceil\sqrt{2|\mathcal{V}_{\ell}|}\rceil

and the Rank-2 relaxation method for GS PRP of

J_{1}

–

J_{2}

HAF, at different coupling values (

J_{2}/J_{1}

), in the zero magnetization sector, for periodic lattices. Entries give the fraction of signs calculated by GW or Rank-2 matching the exact GS signs (up to three decimal places), so that unity corresponds to complete recovery of the sign structure. The values imply that every sign reconstruction was at least

99.95\%

accurate. In all cases, we used the Adam [ 29 ] optimizer with a learning rate of

1

and the number of iterations being

500

. We used

32

-bit floating-point numbers to reduce memory consumption. Additionally, for GW algorithm

128

random hyperplanes and a cosine decay schedule were used. Full implementation details are publicly available, see Code Availability at the end of the paper.

Figure 6: Representative odd closed walks on the HG that contribute to the odd-to-even walk ratio

R_{\ell}(\beta)

. Filled dots are HG vertices

\ket{\sigma}

; blue arrows are hops along HG edges, each carrying one factor of

W_{\ell}

, and an orange ring marks a diagonal insertion at that vertex, carrying one factor of

D_{\ell}

. A ring is not an edge of the HG. (a) The triangle walk

\ket{\sigma}\to\ket{\tau}\to\ket{\rho}\to\ket{\sigma}

contributing to

\operatorname{Tr}(W_{\ell}^{3})

at order

\beta^{3}

. (b) – (d) The same triangle with one or two diagonal insertions, contributing at orders

\beta^{4}

and

\beta^{5}

. (e) – (g) The three five-hop structures at order

\beta^{5}

: a simple five-cycle, a triangle with one edge traversed back and forth, where

\ket{\eta}

may also be a vertex of the triangle, and the product

\operatorname{Tr}(W_{\ell}^{2})\operatorname{Tr}(W_{\ell}^{3})

that enters

r_{5}

through the elimination of the even-walk series. Each trace sums over all vertex labels, and numerical prefactors are omitted.

Quantum Many-Body Physics

Quantum many-body physics studies how interacting quantum particles produce collective behavior, phases of matter, and complex dynamics.

See all 55 papers

May 21, 2026

Comment on "Spin-1/2 Kagome Heisenberg Antiferromagnet: Machine Learning Discovery of the Spinon Pair-Density-Wave Ground State"

A recent article [Phys. Rev. X 15, 011047 (2025)] utilizes group-equivariant convolutional neural networks to study the ground state of the kagome Heisenberg antiferromagnet. On the largest finite-size cluster studied to date (

N=108

), the authors report variational energies significantly lower than other numerical methods, including state-of-the-art density matrix renormalization group (DMRG) calculations. In contrast to previous results suggesting a possible spin-liquid ground state, the authors observe a spinon pair-density-wave ground state. We find that: (i) the reported low energies are artifacts of broken ergodicity in the Metropolis--Hastings sampling, since the single-spin-flip update rule utilized by the authors effectively freezes the Markov chains; and (ii) when ergodic sampling is enforced via spin-exchange updates, the neural network converges to energies significantly higher than existing DMRG results, calling the paper's claims into question.

Helia Kamal, Dominik Kufel, DinhDuy Vu +2

Department of Physics, Harvard University, Cambridge, MA 02138, USA · Harvard Quantum Initiative, Cambridge, MA 02138, USA · Department of Physics, Boston University, Boston, MA 02215, USA

Neural Quantum States Markov Chain Monte Carlo Variational Monte Carlo Quantum Many-Body Physics

Ask PDF

Sep 7, 2026

Graph neural networks and the energetic cavity method for combinatorial optimization

We study the use of graph neural networks (GNNs) for finding approximate ground states of Ising models. Efficiently finding these ground states is of broad significance because many combinatorial optimization problems can be formulated as an Ising model with the appropriate choice of couplings and fields. Exactly solving these problems is hard but there are many good heuristic methods. A lineage of these heuristics build from mean-field approximations: one approach uses the leading eigenvector of an appropriately defined matrix, another is the min-sum algorithm, also known as the energetic cavity method. Without modification, GNNs perform worse than both of these methods. We consider small modifications to the GNN to incorporate these heuristics and find that this considerably improves performance. While the modified approach is competitive against other deep-learning approaches, we still find that simulated annealing is reliably at least as good as deep learning methods for the same computational cost.

Joe Bacchus George, George T. Cantwell

Department of Engineering, University of Cambridge, CB2 1PZ, United Kingdom

Graph Neural Networks Combinatorial Optimization Neural Combinatorial Optimization

Ask PDF

Sep 27, 2026

Apparent Compression, Real Stability: The Intrinsic Dimension of Learning a Quantum Wavefunction

How many directions in weight space does training need? The intrinsic dimension answers this with the smallest number of random directions in which training still reaches a target accuracy, and small values have motivated parameter-efficient methods such as LoRA. We measure it for variational Monte Carlo (VMC), which trains a neural network to represent the ground state of a quantum many-body system. VMC is a demanding test, because the network generates its own training samples and every gradient is noisy, and a revealing one, because the exact answer is known and every run can be scored. We train only a small latent vector that a frozen random map turns into the network's weights, with no change to the standard natural-gradient optimizer. We find that a small dimension can be misleading, while the stability it brings is real. On a magnet with a hard sign pattern, a network that cannot represent signs reaches its best energy in 8 of 28,642 directions, but only because no such network can go lower; once signs are learnable, neither the signs nor the magnitudes are cheap. The dimension rises across a quantum phase transition, so it tracks how difficult a state is at far less compute than fitting a scaling law, yet it never falls below a floor set by the random subspace itself, even where the ground state is nearly trivial. Training in the subspace, in contrast, never diverged in our experiments, whereas full-parameter training with the same settings did, and a control with matched solvers attributes the difference to the reduced dimension.

Lu Wei, Yufeng Wang, Chenfeng Cao +1

Data Science Department, Stony Brook University · Department of Computer Science, Stony Brook University · Dahlem Center for Complex Quantum Systems, Freie Universität Berlin +1

Variational Monte Carlo Intrinsic Dimensionality Neural Quantum States

Ask PDF

Abstract

Quantum Many-Body Physics

Explore similar work

Comment on "Spin-1/2 Kagome Heisenberg Antiferromagnet: Machine Learning Discovery of the Spinon Pair-Density-Wave Ground State"

Graph neural networks and the energetic cavity method for combinatorial optimization

Apparent Compression, Real Stability: The Intrinsic Dimension of Learning a Quantum Wavefunction