Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2602.04943

Graph-Theoretic Analysis of Phase Optimization Complexity in Variational Wave Functions for Heisenberg Antiferromagnets

Mahmud Ashraf Shamim, Md Moshiur Rahman Raj, Mohamed Hibat-Allah, Paulo T Araujo

cond-mat.str-elcond-mat.dis-nncs.AIcs.CCquant-phSubmitted Feb 4, 2026• Announced Feb 5, 2026• 2 citations• Revised Apr 7, 2026 (v3)
v1 · Feb 4, 2026v2 · Feb 9, 2026v3 · Apr 7, 2026v4 · Oct 19, 2026v5 · Oct 21, 2026
arXivHTMLPDF

Abstract

We study the computational complexity of learning the ground state phase structure of Heisenberg antiferromagnets. Representing Hilbert space as a weighted graph, the variational energy defines a weighted XY model that, for $\mathbb{Z}_2$ phases, reduces to a classical antiferromagnetic Ising model on that graph. For fixed amplitudes, reconstructing the signs of the ground state wavefunction thus reduces to a weighted Max-Cut instance. This establishes that ground state phase reconstruction for Heisenberg antiferromagnets is worst-case NP-hard and links the task to combinatorial optimization.

Comments
A new figure is added. Texts have been revised: a discussion of the Hessian has been added, and references have been fixed

Related papers

Variational ground states of two-dimensional antiferromagnets in the valence bond basis

Jie Lou, Anders W. Sandvik

We study a variational wave function for the ground state of the two-dimensional $S=1∕2$ Heisenberg antiferromagnet in the valence bond basis. The expansion coefficients are products of amplitudes $h(x,y)$ for valence bonds connecting spins separated by $(x,y)$ lattice spacings. In contrast to previous studies, in which a functional form for $h(x,y)$ was assumed, we here optimize all the amplitudes for lattices with up to $32\ifmmode\times\else\texttimes\fi{}32$ spins. We use two different schemes for optimizing the amplitudes; a Newton conjugate-gradient method and a stochastic method which requires only the signs of the first derivatives of the energy. The latter method performs significantly better. The energy for large systems deviates by only $\ensuremath{\approx}0.06%$ from its exact value (calculated using unbiased quantum Monte Carlo simulations). The spin correlations are also well reproduced, falling $\ensuremath{\approx}2%$ below the exact ones at long distances (corresponding to an $\ensuremath{\approx}1%$ underestimation of the sublattice magnetization). The amplitudes $h(r)$ for valence bonds of long length $r$ decay as ${r}^{\ensuremath{-}3}$. We also discuss some results for small frustrated lattices.

arXiv:cond-mat/0605034•Physical Review B•Sep 25, 2007•45 citations

Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders

Stuart Wayland, Zackary Jorquera, Alexandra Kolla

Quantum Max-Cut is a well-studied local Hamiltonian problem for which the classical complexity of the bipartite case remains open. We give a polynomial-time classical randomized algorithm for the spin-$\tfrac12$ antiferromagnetic Heisenberg model, equivalently Quantum Max-Cut, on dense balanced bipartite expanders. This class includes $G(n,n,p)$ with high probability for every fixed $p>0$. The algorithm estimates the ground energy and any ground state edge correlation to additive error $\varepsilon$ in time polynomial in $n$ and $1/\varepsilon$. We construct a Markov chain on perfect matchings of the complete bipartite graph, each matching representing a product of singlets, that converges to the ground state, and use the expansion of the graph to show that polynomially many steps and samples of this chain suffice.

quant-pharXiv:2610.03670•Oct 5, 2026•0 citations

Many-body quantum sign structures as non-glassy Ising models

Tom Westerhout, Mikhail I. Katsnelson, Andrey A. Bagrov

Abstract The non-trivial phase structure of the eigenstates of many-body quantum systems severely limits the applicability of quantum Monte Carlo, variational, and machine learning methods. Here, we study real-valued signful ground-state wave functions of frustrated quantum spin systems and, assuming that the tasks of finding wave function amplitudes and signs can be separated, show that the signs can be easily bootstrapped from the amplitudes. We map the problem of finding the sign structure to an auxiliary classical Ising model defined on a subset of the Hilbert space basis. We show that the Ising model does not exhibit significant frustrations even for highly frustrated parental quantum systems, and is solvable with a fully deterministic $$O(K\log K)$$ O ( K log K ) -time combinatorial algorithm (where K is the Ising model size). Given the ground state amplitudes, we reconstruct the signs of the ground states of several frustrated quantum models, thereby revealing the hidden simplicity of many-body sign structures.

arXiv:2207.10675•Communications Physics•Sep 28, 2023•11 citations

Implications of the PXP ground-state sign structure for neural-network variational Monte Carlo

Jun Sur Richard Park, Kwangmin Yu

Positive-definite neural-network quantum states cannot directly represent the ground state of the PXP Hamiltonian, since the ground-state wavefunction carries a nontrivial relative-sign structure. Building on the chiral symmetry of the PXP Hamiltonian, we show that this sign structure is fixed exactly by the parity of the total up-spin number: a diagonal unitary transformation that assigns a sign to each spin configuration according to this parity maps the PXP Hamiltonian to its negative, rendering the transformed Hamiltonian stoquastic on the Rydberg-blockaded Hilbert space. Since the configuration graph of allowed configurations is connected, the Perron-Frobenius theorem guarantees a unique, strictly positive ground state of the transformed Hamiltonian, yielding an exact sign rule for the ground state of the original Hamiltonian in terms of the parity of the up-spin number. Variational Monte Carlo performed directly on the transformed Hamiltonian with a positive-definite ansatz therefore requires no architecture-specific modification to represent the true ground state. We evaluate the performance of this formulation using five representative neural-network quantum state architectures, SineKAN, reflection-symmetrized SineKAN, RBM, MLP, and LSTM, for different chain lengths.

quant-pharXiv:2611.00603•Nov 3, 2026•0 citations

Correlated valence bond state and its study of the spin-1/2 J1-J2 Anti-ferromagnetic Heisenberg model on a square lattice

Ling Wang

We propose a class of variational wave functions, namely the correlated valence bond states, for the frustrated Hamiltonian in the paramagnetic phase. This class of wave functions admits negative amplitude and the same sub-lattice pairing when a bipartite lattice is considered, thus suffers from the negative sign problem. However if applied to small systems, the sign problem is manageable using the standard variational Monte Carlo method. We optimize the wave functions for the J1-J2 Anti ferromagnetic Heisenberg model on a square lattice in the coupling region J2/J1 \in [0.45 : 0.56] for system sizes L = 4, 6, 8. To calculate the correlation functions and the order parameters for larger systems, we make the extensive Monte Carlo samplings using the variational parameters optimized at system size L = 8. We find that the paramagnetic phase is a gap-less spin liquid in the entire range of J2/J1 \in [0.45 : 0.56] with a gap-less singlet excitation and a gaped triplet excitation.

arXiv:1402.3564•Feb 14, 2014•4 citations

Variational calculations for the square-lattice quantum antiferromagnet

Zhiping Liu, Efstratios Manousakis

We study the spin-1/2 Heisenberg antiferromagnet on a square lattice using variational Monte Carlo calculations. We construct a variational wave function which gives accurate ground-state energy and is consistent with sum rules for the dynamical structure function. The spin-wave velocity and the spin-stiffness constant can be calculated using sum rules. We obtain ${Z}_{c}$==c/${c}_{0}$, where ${c}_{0}$ is the classical spin-wave velocity. This and other ground-state quantities are in good agreement with spin-wave theory and Monte Carlo calculations.

Physical review. B, Condensed matter•Dec 1, 1989•36 citations
We study the computational complexity of learning the ground state phase structure of Heisenberg antiferromagnets. Representing Hilbert space as a weighted graph, the variational energy defines a weighted XY model that, for Z2\mathbb{Z}_2Z2​ phases, reduces to a classical antiferromagnetic Ising model on that graph. For fixed amplitudes, reconstructing the signs of the ground state wavefunction thus reduces to a weighted Max-Cut instance. This establishes that ground state phase reconstruction for Heisenberg antiferromagnets is worst-case NP-hard and links the task to combinatorial optimization.
We study a variational wave function for the ground state of the two-dimensional S=1∕2S=1∕2S=1∕2 Heisenberg antiferromagnet in the valence bond basis. The expansion coefficients are products of amplitudes h(x,y)h(x,y)h(x,y) for valence bonds connecting spins separated by (x,y)(x,y)(x,y) lattice spacings. In contrast to previous studies, in which a functional form for h(x,y)h(x,y)h(x,y) was assumed, we here optimize all the amplitudes for lattices with up to $32\ifmmode\times\else\texttimes\fi{}32$ spins. We use two different schemes for optimizing the amplitudes; a Newton conjugate-gradient method and a stochastic method which requires only the signs of the first derivatives of the energy. The latter method performs significantly better. The energy for large systems deviates by only $\ensuremath{\approx}0.06%$ from its exact value (calculated using unbiased quantum Monte Carlo simulations). The spin correlations are also well reproduced, falling $\ensuremath{\approx}2%$ below the exact ones at long distances (corresponding to an $\ensuremath{\approx}1%$ underestimation of the sublattice magnetization). The amplitudes h(r)h(r)h(r) for valence bonds of long length rrr decay as ${r}^{\ensuremath{-}3}$. We also discuss some results for small frustrated lattices.
Quantum Max-Cut is a well-studied local Hamiltonian problem for which the classical complexity of the bipartite case remains open. We give a polynomial-time classical randomized algorithm for the spin-12\tfrac1221​ antiferromagnetic Heisenberg model, equivalently Quantum Max-Cut, on dense balanced bipartite expanders. This class includes G(n,n,p)G(n,n,p)G(n,n,p) with high probability for every fixed p>0p>0p>0. The algorithm estimates the ground energy and any ground state edge correlation to additive error ε\varepsilonε in time polynomial in nnn and 1/ε1/\varepsilon1/ε. We construct a Markov chain on perfect matchings of the complete bipartite graph, each matching representing a product of singlets, that converges to the ground state, and use the expansion of the graph to show that polynomially many steps and samples of this chain suffice.
Abstract The non-trivial phase structure of the eigenstates of many-body quantum systems severely limits the applicability of quantum Monte Carlo, variational, and machine learning methods. Here, we study real-valued signful ground-state wave functions of frustrated quantum spin systems and, assuming that the tasks of finding wave function amplitudes and signs can be separated, show that the signs can be easily bootstrapped from the amplitudes. We map the problem of finding the sign structure to an auxiliary classical Ising model defined on a subset of the Hilbert space basis. We show that the Ising model does not exhibit significant frustrations even for highly frustrated parental quantum systems, and is solvable with a fully deterministic O(Klog⁡K)O(K\log K)O(KlogK) O ( K log K ) -time combinatorial algorithm (where K is the Ising model size). Given the ground state amplitudes, we reconstruct the signs of the ground states of several frustrated quantum models, thereby revealing the hidden simplicity of many-body sign structures.
Positive-definite neural-network quantum states cannot directly represent the ground state of the PXP Hamiltonian, since the ground-state wavefunction carries a nontrivial relative-sign structure. Building on the chiral symmetry of the PXP Hamiltonian, we show that this sign structure is fixed exactly by the parity of the total up-spin number: a diagonal unitary transformation that assigns a sign to each spin configuration according to this parity maps the PXP Hamiltonian to its negative, rendering the transformed Hamiltonian stoquastic on the Rydberg-blockaded Hilbert space. Since the configuration graph of allowed configurations is connected, the Perron-Frobenius theorem guarantees a unique, strictly positive ground state of the transformed Hamiltonian, yielding an exact sign rule for the ground state of the original Hamiltonian in terms of the parity of the up-spin number. Variational Monte Carlo performed directly on the transformed Hamiltonian with a positive-definite ansatz therefore requires no architecture-specific modification to represent the true ground state. We evaluate the performance of this formulation using five representative neural-network quantum state architectures, SineKAN, reflection-symmetrized SineKAN, RBM, MLP, and LSTM, for different chain lengths.
We propose a class of variational wave functions, namely the correlated valence bond states, for the frustrated Hamiltonian in the paramagnetic phase. This class of wave functions admits negative amplitude and the same sub-lattice pairing when a bipartite lattice is considered, thus suffers from the negative sign problem. However if applied to small systems, the sign problem is manageable using the standard variational Monte Carlo method. We optimize the wave functions for the J1-J2 Anti ferromagnetic Heisenberg model on a square lattice in the coupling region J2/J1 \in [0.45 : 0.56] for system sizes L = 4, 6, 8. To calculate the correlation functions and the order parameters for larger systems, we make the extensive Monte Carlo samplings using the variational parameters optimized at system size L = 8. We find that the paramagnetic phase is a gap-less spin liquid in the entire range of J2/J1 \in [0.45 : 0.56] with a gap-less singlet excitation and a gaped triplet excitation.
We study the spin-1/2 Heisenberg antiferromagnet on a square lattice using variational Monte Carlo calculations. We construct a variational wave function which gives accurate ground-state energy and is consistent with sum rules for the dynamical structure function. The spin-wave velocity and the spin-stiffness constant can be calculated using sum rules. We obtain Zc{Z}_{c}Zc​==c/c0{c}_{0}c0​, where c0{c}_{0}c0​ is the classical spin-wave velocity. This and other ground-state quantities are in good agreement with spin-wave theory and Monte Carlo calculations.