It is known that classical spin-glass problems are NP-hard, just like their quantum counterparts. Does this truly mean that finding their Ground-State is equally hard in both cases?

The most straightforward idea of solving the classical XY-model of $N$ sites exactly, for example, would be discretizing the angle $\theta_j$ at each site $j$ into $M_\theta$ possible values for example; try out all the possible combinations and take the many-body state with the lowest energy. This leads to $M_\theta^N$ states to be considered. Such a discretization approach is proposed, e.g. here for time-evolution, but I think that's easier than the ground state. Or is doing imaginary time-evolution a reliable approach that avoids metastabilities?

Taking the quantum limit on the other hand, leads to a Hilbert space spanned by 'only' $2^N$ basisvectors, in contrast. Or am I missing something?

EDIT added: it seems that my premise that the classical XY model can straightforwardly be studied as a quantum XY model seems wrong because the latter features entanglement while the former shouldn't. So the classical case rather matches some kind of Gutzwiller approch

  • $\begingroup$ No answer in 22 days? Seems rough, maybe try here where there's specific tags for ising-model, spin-models, heisenberg-model, model-hamiltonians, and condensed-matter: mattermodeling.stackexchange.com $\endgroup$ Apr 8, 2021 at 3:34
  • $\begingroup$ Doesn't the quantum version add one more (infinite imaginary time for the quantum GS) dimension to the lattice? A 2d spin glass is in P thanks to the FKT algorithm, but it's NP-hard in the quantum case because it's equivalent to a 3d spin glass. $\endgroup$
    – PeaBrane
    Apr 16, 2021 at 16:14
  • $\begingroup$ @PeaBrane I'm aware of such an equivalence between quantum spin models in D dimensions and classical spin models in D+1 dimensions, but does it go beyond statistical properties in the thermodynamic limit? I've never heard about FKT, so it surprises me that you say 2D spin glasses are only P. Here they claim for exemple that 2D XY simulators are useful for solving NP-hard tasks nature.com/articles/nmat4971 $\endgroup$
    – Wouter
    Apr 17, 2021 at 4:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.