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 Oct 19, 2026 (v4)
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 links sign optimization of wavefunctions directly to combinatorial optimization.

Comments
The NP-hardness claim has been corrected, and the connection to variational Monte Carlo has been revised

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

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

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

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
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 links sign optimization of wavefunctions directly 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.
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.
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.