arxiv: 2602.04943 · v3 · submitted 2026-02-04 · ❄️ cond-mat.str-el · cond-mat.dis-nn· cs.AI· cs.CC· quant-ph

Recognition: no theorem link

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

Authors on Pith no claims yet

Pith reviewed 2026-05-16 06:40 UTC · model grok-4.3

classification ❄️ cond-mat.str-el cond-mat.dis-nncs.AIcs.CCquant-ph

keywords Heisenberg antiferromagnetsvariational wave functionsphase optimizationNP-hardnessMax-CutHilbert space graphcombinatorial optimizationIsing model

0 comments

The pith

Reconstructing phases for Heisenberg antiferromagnet ground states reduces to weighted Max-Cut on the Hilbert-space graph and is NP-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that, with amplitudes fixed in advance, optimizing the signs of a variational wavefunction for a Heisenberg antiferromagnet is equivalent to solving a weighted maximum-cut problem on a graph whose vertices are the basis states of the Hilbert space. This equivalence arises because the variational energy maps onto a weighted XY model whose Z2 restriction becomes an antiferromagnetic Ising model on that same graph. A sympathetic reader would care because the result explains why exact phase reconstruction is computationally intractable in the worst case and directly ties a core task in quantum many-body physics to a classic combinatorial optimization problem.

Core claim

Representing Hilbert space as a weighted graph, the variational energy defines a weighted XY model that, for Z2 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.

What carries the argument

The reduction of fixed-amplitude Z2 phase optimization to a weighted Max-Cut instance on the Hilbert-space graph, which carries the NP-hardness proof.

If this is right

Sign reconstruction for these variational wavefunctions is NP-hard in the worst case.
The phase optimization task is computationally equivalent to solving a weighted Max-Cut instance.
Variational energy minimization with fixed amplitudes inherits the hardness of classical combinatorial problems.
The Z2 phase structure alone is sufficient to produce the hardness result.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Heuristic Max-Cut solvers could be directly adapted as practical phase optimizers inside variational Monte Carlo codes.
Similar graph reductions may apply to other frustrated spin Hamiltonians, suggesting a broader combinatorial barrier.
The separation of amplitude and phase optimization isolates the combinatorial bottleneck; joint optimization of both may not remove the hardness.

Load-bearing premise

The variational energy can be exactly recast as a weighted XY model whose Z2 restriction is an antiferromagnetic Ising model on the Hilbert-space graph, with amplitudes fixed in advance.

What would settle it

Discovery of a polynomial-time algorithm that computes the optimal signs for any fixed-amplitude variational wavefunction of a Heisenberg antiferromagnet would falsify the claim.

Figures

Figures reproduced from arXiv: 2602.04943 by Mahmud Ashraf Shamim, Md Moshiur Rahman Raj, Mohamed Hibat-Allah, Paulo T Araujo.

**Figure 2.** Figure 2: FIG. 2 [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper cleanly reduces fixed-amplitude phase optimization to weighted Max-Cut on the Hilbert-space graph, but the worst-case NP-hardness claim does not follow from the structured graphs that arise in actual Heisenberg models.

read the letter

The main takeaway is that, once amplitudes are fixed, minimizing the variational energy over Z2 phases for a Heisenberg antiferromagnet is exactly equivalent to solving a weighted Max-Cut problem whose interaction graph is the one induced by the Hamiltonian on the full Hilbert space. The steps—variational energy to XY model, Z2 restriction to antiferromagnetic Ising, then to Max-Cut—are direct and free of fitting or circularity. That explicit mapping appears new and gives a useful bridge to combinatorial optimization tools and approximation algorithms. It is the part of the work that holds up cleanly. The soft spot is the jump to “worst-case NP-hard.” The graphs in question are not arbitrary; they are rigidly determined by the lattice geometry and the fixed amplitudes, so they carry a great deal of structure. General Max-Cut is NP-hard, but that does not automatically make Max-Cut on this exponential but highly constrained family hard. No Karp-style reduction from a known NP-complete problem to the physical instances is supplied, so the complexity conclusion is not supported by the equivalence alone. In many cases of interest the signs are already fixed by theorems such as Marshall-Lieb-Mattis, which further suggests the problem may be tractable precisely where it matters. The paper is aimed at people working on variational Monte Carlo or tensor-network methods for quantum magnets who want to understand the optimization landscape. It is worth sending to peer review so the authors can either strengthen the hardness argument for the structured case or qualify the claim. The reduction itself is worth having in the literature even if the broader complexity statement needs revision.

Referee Report

1 major / 0 minor

Summary. The manuscript analyzes the computational complexity of optimizing the phase structure in variational wave functions for Heisenberg antiferromagnets. By representing the Hilbert space as a weighted graph, it shows that the variational energy minimization over Z_2 phases reduces exactly to a weighted Max-Cut problem on this graph, claiming this proves the worst-case NP-hardness of ground-state phase reconstruction.

Significance. The reduction chain from the variational energy to the XY model, then to the antiferromagnetic Ising model, and finally to Max-Cut is logically sound and parameter-free. If the NP-hardness claim can be rigorously established through an explicit reduction, this would be a significant contribution linking quantum many-body variational problems to combinatorial optimization, potentially guiding the development of approximation algorithms or heuristics for such tasks.

major comments (1)

[Abstract] The assertion in the Abstract that the equivalence 'establishes that ground state phase reconstruction for Heisenberg antiferromagnets is worst-case NP-hard' is not justified. While the mapping to a weighted Max-Cut instance on the Hilbert-space graph is correct, the graph is highly structured (with edges and weights fixed by the physical lattice and amplitudes). Max-Cut on this restricted class of graphs is not known to be NP-hard, and the manuscript does not provide a Karp reduction from a canonical NP-complete problem to the phase optimization problem.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and for recognizing the logical soundness of the reduction chain. We address the major comment below and will revise the manuscript to clarify the complexity claim.

read point-by-point responses

Referee: [Abstract] The assertion in the Abstract that the equivalence 'establishes that ground state phase reconstruction for Heisenberg antiferromagnets is worst-case NP-hard' is not justified. While the mapping to a weighted Max-Cut instance on the Hilbert-space graph is correct, the graph is highly structured (with edges and weights fixed by the physical lattice and amplitudes). Max-Cut on this restricted class of graphs is not known to be NP-hard, and the manuscript does not provide a Karp reduction from a canonical NP-complete problem to the phase optimization problem.

Authors: We agree with the referee that the current wording overstates the result. The manuscript demonstrates an exact equivalence between Z_2 phase optimization (for fixed amplitudes) and weighted Max-Cut on the Hilbert-space graph, but does not contain an explicit Karp reduction showing that this structured instance remains NP-hard. We will revise the abstract to state only that the problem is equivalent to a weighted Max-Cut instance on the graph induced by the physical system, thereby connecting it to combinatorial optimization without claiming unconditional worst-case NP-hardness. A brief discussion clarifying the distinction between general Max-Cut and the structured case will be added to the main text. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation is a direct equivalence to Max-Cut without self-referential inputs or fitted predictions

full rationale

The paper's central step equates variational phase optimization (for fixed amplitudes) to weighted Max-Cut on the Hilbert-space graph induced by Heisenberg couplings, via the explicit rewriting of the energy as an antiferromagnetic Ising model. This reduction is constructed from the model definitions and graph representation rather than by redefining any quantity in terms of itself or by smuggling an ansatz through citation. No parameters are fitted and then relabeled as predictions, no uniqueness theorems are imported from prior self-work, and no self-citation chain bears the load of the equivalence. The subsequent claim that the task is NP-hard follows from the identification with Max-Cut (a known hard problem) rather than from any internal loop; while the restriction to structured graphs may weaken the hardness conclusion, that is a question of logical implication, not circularity. The derivation chain is therefore self-contained against its stated premises.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The argument rests on the standard representation of the variational wave function in a fixed basis and the exact rewriting of the energy expectation value as a classical XY model when amplitudes are held constant.

axioms (2)

domain assumption The variational wave function can be written with fixed real amplitudes and variable signs in a chosen basis.
Invoked to isolate the sign-optimization subproblem.
domain assumption The energy functional for fixed amplitudes reduces exactly to a weighted XY model on the graph whose vertices are basis states.
Central step that enables the subsequent Ising reduction.

pith-pipeline@v0.9.0 · 5412 in / 1279 out tokens · 44631 ms · 2026-05-16T06:40:00.148662+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Parallel Scan Recurrent Neural Quantum States for Scalable Variational Monte Carlo
cond-mat.str-el 2026-05 conditional novelty 7.0

PSR-NQS makes recurrent neural quantum states scalable for variational Monte Carlo by using parallel scan recurrence, reaching accurate results on 52x52 two-dimensional lattices.

Reference graph

Works this paper leans on

58 extracted references · 58 canonical work pages · cited by 1 Pith paper · 6 internal anchors

[1]

C. K. Majumdar and D. K. Ghosh, Journal of Mathe- matical Physics10, 1388 (1969)

work page 1969
[2]

C. K. Majumdar and D. K. Ghosh, Journal of Mathe- matical Physics10, 1399 (1969)

work page 1969
[3]

B. S. Shastry and B. Sutherland, Physica B+C108, 1069 (1981). 6

work page 1981
[4]

Schollw¨ ock, Ann

U. Schollw¨ ock, Ann. Phys.326, 96 (2011)

work page 2011
[5]

Or´ us, Ann

R. Or´ us, Ann. Phys.349, 117 (2014)

work page 2014
[6]

Variational wave functions for frustrated magnetic models

F. Becca, L. Capriotti, A. Parola, and S. Sorella, arXiv e-prints , arXiv:0905.4854 (2009), arXiv:0905.4854 [cond- mat.str-el]

work page internal anchor Pith review Pith/arXiv arXiv 2009
[7]

Solving the Quantum Many-Body Problem with Artificial Neural Networks

G. Carleo and M. Troyer, Science355, 602 (2017), arXiv:1606.02318 [cond-mat.dis-nn]

work page internal anchor Pith review Pith/arXiv arXiv 2017
[9]

Hibat-Allah, M

M. Hibat-Allah, M. Ganahl, L. E. Hayward, R. G. Melko, and J. Carrasquilla, Physical Review Research2, 023358 (2020), arXiv:2002.02973 [cond-mat.dis-nn]

work page arXiv 2020
[10]

M. S. Moss, R. Wiersema, M. Hibat-Allah, J. Car- rasquilla, and R. G. Melko, Phys. Rev. B112, 134449 (2025), arXiv:2505.20406 [cond-mat.str-el]

work page arXiv 2025
[11]

Roth, arXiv e-prints , arXiv:2003.06228 (2020), arXiv:2003.06228 [physics.comp-ph]

C. Roth, arXiv e-prints , arXiv:2003.06228 (2020), arXiv:2003.06228 [physics.comp-ph]

work page arXiv 2003
[12]

K. Choo, T. Neupert, and G. Carleo, Phys. Rev. B100, 125124 (2019), arXiv:1903.06713 [cond-mat.str-el]

work page arXiv 2019
[13]

A. Chen, K. Choo, N. Astrakhantsev, and T. Ne- upert, Physical Review Research4, L022026 (2022), arXiv:2111.06411 [cond-mat.str-el]

work page arXiv 2022
[14]

Roth and A

C. Roth and A. H. MacDonald, arXiv e-prints , arXiv:2104.05085 (2021), arXiv:2104.05085 [quant-ph]

work page arXiv 2021
[15]

Solving frustrated quantum many-particle models with convolutional neural networks

X. Liang, W.-Y. Liu, P.-Z. Lin, G.-C. Guo, Y.-S. Zhang, and L. He, Phys. Rev. B98, 104426 (2018), arXiv:1807.09422 [cond-mat.str-el]

work page internal anchor Pith review Pith/arXiv arXiv 2018
[16]

M. A. Shamim, E. A. F. Reinhardt, T. A. Chowdhury, S. Gleyzer, and P. T. Araujo, Phys. Rev. B113, 045157 (2026)

work page 2026
[17]

Ferrari, F

F. Ferrari, F. Becca, and J. Carrasquilla, Physical Review B100, 125131 (2019)

work page 2019
[18]

Restricted-Boltzmann-Machine Learning for Solving Strongly Correlated Quantum Systems

Y. Nomura, A. S. Darmawan, Y. Yamaji, and M. Imada, Phys. Rev. B96, 205152 (2017), arXiv:1709.06475 [cond- mat.str-el]

work page internal anchor Pith review Pith/arXiv arXiv 2017
[19]

L. L. Viteritti, R. Rende, and F. Becca, Phys. Rev. Lett. 130, 236401 (2023), arXiv:2211.05504 [cond-mat.dis-nn]

work page arXiv 2023
[20]

Loris Viteritti, R

L. Loris Viteritti, R. Rende, A. Parola, S. Goldt, and F. Becca, arXiv e-prints , arXiv:2311.16889 (2023), arXiv:2311.16889 [cond-mat.str-el]

work page arXiv 2023
[21]

Rende, L

R. Rende, L. Loris Viteritti, L. Bardone, F. Becca, and S. Goldt, arXiv e-prints , arXiv:2310.05715 (2023), arXiv:2310.05715 [cond-mat.str-el]

work page arXiv 2023
[22]

Rende, L

R. Rende, L. Loris Viteritti, F. Becca, A. Scardicchio, A. Laio, and G. Carleo, arXiv e-prints , arXiv:2502.09488 (2025), arXiv:2502.09488 [quant-ph]

work page arXiv 2025
[23]

D.-L. Deng, X. Li, and S. Das Sarma, Physical Review X 7, 021021 (2017)

work page 2017
[24]

Gao and L

X. Gao and L. Duan, Nature Communications8, 662 (2017)

work page 2017
[25]

Cybenko, Mathematics of Control, Signals and Sys- tems2, 303 (1989)

G. Cybenko, Mathematics of Control, Signals and Sys- tems2, 303 (1989)

work page 1989
[26]

Hornik, Neural Networks4, 251 (1991)

K. Hornik, Neural Networks4, 251 (1991)

work page 1991
[27]

Becca and S

F. Becca and S. Sorella,Quantum Monte Carlo Ap- proaches for Correlated Systems(Cambridge University Press, 2017)

work page 2017
[28]

Szab´ o and C

A. Szab´ o and C. Castelnovo, Physical Review Research 2, 033075 (2020), arXiv:2002.04613 [cond-mat.str-el]

work page arXiv 2020
[29]

Bukov, M

M. Bukov, M. Schmitt, and M. Dupont, SciPost Physics 10, 147 (2021), arXiv:2011.11214 [physics.comp-ph]

work page arXiv 2021
[31]

Westerhout, N

T. Westerhout, N. Astrakhantsev, K. S. Tikhonov, M. I. Katsnelson, and A. A. Bagrov, Nature Commun.11, 1593 (2020), arXiv:1907.08186 [cond-mat.dis-nn]

work page arXiv 2020
[32]

On The Violation Of Marshall-Peierls Sign Rule In The Frustrated $J_{1}-J_{2}$ Heisenberg Antiferromagnet

J. Richter, N. B. Ivanov, and K. Retzlaff, EPL (Euro- physics Letters)25, 545 (1994), arXiv:cond-mat/9407041 [cond-mat]

work page internal anchor Pith review Pith/arXiv arXiv 1994
[34]

Schurov, A

I. Schurov, A. Kravchenko, M. I. Katsnelson, A. A. Bagrov, and T. Westerhout, arXiv preprint arXiv:2508.09870 (2025)

work page arXiv 2025
[35]

M. A. Shamim, M. Rahman, M. Hibat-Allah, and P. T. Araujo, Supplementary material for: Graph–theoretic analysis of phase optimization complexity in variational wave functions for heisenberg antiferromagnets (2026), supplementary material

work page 2026
[36]

Lieb and D

E. Lieb and D. Mattis, Journal of Mathematical Physics 3, 749 (1962)

work page 1962
[37]

Fabila-Monroy, D

R. Fabila-Monroy, D. Flores-Pe˜ naloza, C. Huemer, F. Hurtado, J. Urrutia, and D. R. Wood, Graphs and Combinatorics28, 365 (2012)

work page 2012
[38]

D. B. West,Introduction to Graph Theory, 2nd ed. (Pren- tice Hall, Upper Saddle River, NJ, 2001)

work page 2001
[39]

Karush,Minima of functions of several variables with inequalities as side conditions, Master’s thesis, Depart- ment of Mathematics, University of Chicago, Chicago, Illinois (1939)

W. Karush,Minima of functions of several variables with inequalities as side conditions, Master’s thesis, Depart- ment of Mathematics, University of Chicago, Chicago, Illinois (1939)

work page 1939
[40]

H. W. Kuhn and A. W. Tucker, inProceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability(University of California Press, 1951) pp. 481–492

work page 1951
[41]

Burer, R

S. Burer, R. D. Monteiro, and Y. Zhang, SIAM Journal on Optimization12, 503 (2002)

work page 2002
[42]

E. Lieb, T. Schultz, and D. Mattis, Annals of Physics16, 407 (1961)

work page 1961
[43]

Lucas, Frontiers in Physics2, 5 (2014)

A. Lucas, Frontiers in Physics2, 5 (2014)

work page 2014
[44]

R. M. Karp, inComplexity of Computer Computations (Plenum Press, New York, 1972) pp. 85–103

work page 1972
[45]

F. O. Hadlock, SIAM Journal on Computing4, 221 (1975)

work page 1975
[46]

Gr¨ otschel and W

M. Gr¨ otschel and W. R. Pulleyblank, Operations Re- search Letters1, 23 (1981)

work page 1981
[47]

Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations

M. Troyer and U.-J. Wiese, Phys. Rev. Lett.94, 170201 (2005), arXiv:cond-mat/0408370

work page internal anchor Pith review Pith/arXiv arXiv 2005
[49]

Boyd and L

S. Boyd and L. Vandenberghe,Convex Optimization (Cambridge University Press, 2004)

work page 2004
[50]

domain-wall

M. Shamim, M. M. R. Raj, M. Hibat-Allah, N. Okada, and P. T. Araujo (2026), manuscript in preparation. SUPPLEMENTAL MATERIAL Graph–Theoretic Analysis of Phase Optimization Complexity in Variational Wave Functions for Heisenberg Antiferromagnets Mahmud Ashraf Shamim1, Md Moshiur Rahman Raj 2, Mohamed Hibat-Allah3,4 and Paulo T Araujo 1 1 Department of Phys...

work page 2026
[51]

The HGΓ(G)is bipartite

work page
[52]

unfrustrated sign

There exists a phase assignment satisfying the globalπ–edge condition (PEC) ϕσ−ϕτ≡π(mod 2π)for all(σ,τ)∈E. Proof.(1)⇒(2): If Γ(G) is bipartite, writeV=A∪Bwith all edges connectingAtoB. Define ϕσ= { 0, σ∈A, π, σ∈B. Every edge (σ,τ) connects opposite sublattices, soϕσ−ϕτ≡π(mod 2π); hence the PEC holds on every edge. (2)⇒(1): Assume there is a phase field ob...

work page
[53]

Fazekas,Lecture Notes on Electron Correlation and Magnetism(WORLD SCIENTIFIC, 1999)

P. Fazekas,Lecture Notes on Electron Correlation and Magnetism(WORLD SCIENTIFIC, 1999)

work page 1999
[54]

Marshall, Proceedings of the Royal Society of London

W. Marshall, Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences232, 48 (1955)

work page 1955
[55]

Rao,Field Theories in Condensed Matter Physics(CRC Press, 2019)

S. Rao,Field Theories in Condensed Matter Physics(CRC Press, 2019)

work page 2019
[56]

Fabila-Monroy, D

R. Fabila-Monroy, D. Flores-Pe˜ naloza, C. Huemer, F. Hurtado, J. Urrutia, and D. R. Wood, Graphs and Combinatorics 28, 365 (2012)

work page 2012
[57]

Westerhout, M

T. Westerhout, M. I. Katsnelson, and A. A. Bagrov, Commun. Phys.6, 275 (2023), arXiv:2207.10675 [cond-mat.dis-nn]

work page arXiv 2023
[58]

Lieb and D

E. Lieb and D. Mattis, Journal of Mathematical Physics3, 749 (1962)

work page 1962
[59]

M. X. Goemans and D. P. Williamson, Journal of the ACM (JACM)42, 1115 (1995)

work page 1995
[60]

Boyd and L

S. Boyd and L. Vandenberghe,Convex Optimization(Cambridge University Press, 2004)

work page 2004
[61]

Karush,Minima of functions of several variables with inequalities as side conditions, Master’s thesis, Department of Mathematics, University of Chicago, Chicago, Illinois (1939)

W. Karush,Minima of functions of several variables with inequalities as side conditions, Master’s thesis, Department of Mathematics, University of Chicago, Chicago, Illinois (1939)

work page 1939
[62]

H. W. Kuhn and A. W. Tucker, inProceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability (University of California Press, 1951) pp. 481–492. 18

work page 1951