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• 0 citations• Revised Feb 9, 2026 (v2)
v1 · Feb 4, 2026v2 · Feb 9, 2026v3 · Apr 7, 2026v4 · Oct 19, 2026v5 · Oct 21, 2026
arXivHTMLPDF

Abstract

Despite extensive study, the phase structure of the wavefunctions in frustrated Heisenberg antiferromagnets (HAF) is not yet systematically characterized. In this work, we represent the Hilbert space of an HAF as a weighted graph, which we term the Hilbert graph (HG), whose vertices are spin configurations and whose edges are generated by off-diagonal spin-flip terms of the Heisenberg Hamiltonian, with weights set by products of wavefunction amplitudes. Holding the amplitudes fixed and restricting phases to $\mathbb{Z}_2$ values, the phase-dependent variational energy can be recast as a classical Ising antiferromagnet on the HG, so that phase reconstruction of the ground state reduces to a weighted Max-Cut instance. This shows that phase reconstruction HAF is worst-case NP-hard and provides a direct link between wavefunction sign structure and combinatorial optimization.

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•39 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

Sign-optimized Quantum Monte Carlo

Julius S. Herz, Robin Schäfer, M. G. Gonzalez +1 more

The sign problem breaks the polynomial scaling of Quantum Monte Carlo methods. We alleviate it by rotation of the local basis of the Hilbert space, such that the phase of off-diagonal matrix elements of the rotated Hamiltonian is minimized. These minima coincide with optima of the average sign. We benchmark our method for frustrated Heisenberg antiferromagnets in one dimension and on the two-dimensional maple-leaf lattice. Our approach reveals more efficient bases with improved sign in a large part of the parameter space for all models considered, enabling us to reach lower temperatures, on par with state-of-the-art numerical linked cluster expansions which we directly compare to.

arXiv:2607.24679•Jul 27, 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•7 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•2 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•35 citations
Despite extensive study, the phase structure of the wavefunctions in frustrated Heisenberg antiferromagnets (HAF) is not yet systematically characterized. In this work, we represent the Hilbert space of an HAF as a weighted graph, which we term the Hilbert graph (HG), whose vertices are spin configurations and whose edges are generated by off-diagonal spin-flip terms of the Heisenberg Hamiltonian, with weights set by products of wavefunction amplitudes. Holding the amplitudes fixed and restricting phases to Z2\mathbb{Z}_2Z2​ values, the phase-dependent variational energy can be recast as a classical Ising antiferromagnet on the HG, so that phase reconstruction of the ground state reduces to a weighted Max-Cut instance. This shows that phase reconstruction HAF is worst-case NP-hard and provides a direct link between wavefunction sign structure and 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.
The sign problem breaks the polynomial scaling of Quantum Monte Carlo methods. We alleviate it by rotation of the local basis of the Hilbert space, such that the phase of off-diagonal matrix elements of the rotated Hamiltonian is minimized. These minima coincide with optima of the average sign. We benchmark our method for frustrated Heisenberg antiferromagnets in one dimension and on the two-dimensional maple-leaf lattice. Our approach reveals more efficient bases with improved sign in a large part of the parameter space for all models considered, enabling us to reach lower temperatures, on par with state-of-the-art numerical linked cluster expansions which we directly compare to.
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.
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.