1
$\begingroup$

Consider a classical spin glass in zero field, with degrees of freedom $\{s_i = \pm 1\}$ and the energy $H = \sum_{i \neq j} J_{ij} s_i s_j$, where the $J_{ij}$ are arbitrary real coupling constants. It's well-known that this problem is difficult to solve in general - in fact, it's NP-complete.

The energy spectrum is clearly unchanged if we simultaneously change the sign of all couplings $J_{ij}$ for any single fixed $i$ and all $j \neq i$; this simply corresponds to flipping the spin $i$ while leaving all other spins unchanged (the active transformation version), or equivalently to simply redefining which direction is positive for spin $i$ (the passive transformation version).

I would naively expect that in general, spins glasses with more ferromagnetic bonds are easier to solve than spin glass with more antiferromagnetic bonds. This intuition comes from considering the extreme cases: a system with all ferromagnetic bonds is trivial to solve - all spins point in the same direction - while a system with all antiferromagnetic bonds can still be strongly frustrated, depending on the connectivity pattern. (I don't expect this difficultly to necessarily increase monotonically with the fraction of antiferromagnetic bonds, though.)

If this pattern is indeed true, then that suggests that before we deploy whatever heuristic spin-glass solver we're using to find an approximate ground state, it may help to change variables for certain spins that happen to have an unusually large number of antiferromagnetic bonds, thereby biasing the system toward ferromagnetic bonds before we start trying to solve it. If we keep track of which spins we flipped at the beginning, then it's trivial to reverse that step at the end and solve the original problem encoding.

But I could also imagine several reasons why this wouldn't help, e.g.:

  1. Spin glasses with more ferromagnetic bounds aren't actually significantly easier to solve than those with more antiferromagnetic bonds, so there isn't much or any advantage to doing so.
  2. It's provably unlikely to be able to significantly change the proportion of ferromagnetic bounds from a generic initial bond configuration.
  3. Figuring out which spins need to be flipped in order to significantly increase the number of ferromagnetic bonds turns out to be just as difficult as the original spin glass problem, so that just shifts the original problem to the new problem of figuring out which spins to flip at the beginning and the end.

Is the strategy of flipping spins at the beginning and the end of the optimization in order to maximize the proportion of ferromagnetic bonds actually useful? If not, which of the reasons above (or some other reason) explains why not?

$\endgroup$

2 Answers 2

2
$\begingroup$

As far as I can see, maximization of ferromagnetic bonds and minimization of energy are equivalent, so they require same computational time, which makes them in the same class of complexity, NP-complete.

Let us reformulate a model based on maximization of ferromagnetic bonds. Given a lattice of $N$ spins with each spin $s_i=1$, and coupling constants $J_{ij}$'s which are randomly generated, the "number" of ferromagnetic bonds $F$ is $$F=-\sum_{i \neq j}{J_{ij}}=-\sum_{i \neq j}{J_{ij}s_is_j}$$ Here we flip the signs of $J_{ij}$'s with some fixed $i$ as mentioned in your post. We do so until we find a set of couplings $\{\tilde{J}_{ij}\}$ which maximizes $F$. In comparison with the usual spin model, we can start from the configuration with all spins equal to $1$, and flip the spins to minimize the energy.

However, as you said, the flipping of the signs of $J_{ij}$'s for fixed $i$ is equivalent to the flipping of $s_i$. Therefore, for any path of updates on the spin configuration $\{s_i\}$ in the usual spin glass model, there is one path in the updates of $\{J_{ij}\}$ isomorphic to it. Therefore, both methods are equivalent and require same computational time.

This also gives the physical meaning of $\{\tilde{J}_{ij}\}$: The ground state of $\{\tilde{J}_{ij}\}$ is ferromagnetic with all spins equal to $+1$ or $-1$ since if any update on $s_i$'s given the fixed $\{\tilde{J}_{ij}\}$ reduces the energy, it implies there is some update on $\{\tilde{J}_{ij}\}$ with the fixed spin configuration that increases $F$. The above explanation shall be enough to answer the reasons you give, and knowing how to increase the ferromagnetic bonds $F$ to its maximum is as hard as knowing how to decrease the energy of the spin glass to its minimum. This is also true for the case when we use some hybrid method which flips the couplings and spins alternatively.

$\endgroup$
2
$\begingroup$

I think Andy already gave a perfect answer, but I can also add a bit more information here.

Your idea actually is known and is called a gauge transformation of spin glasses. It can be further developed to a whole line in the phase diagram where you can get exact solutions for finite-dimensional spin glass models, known as the Nishimori line.

For example, in the two dimensional square lattice Ising model, when you put $J_{ij}=\pm 1$ with probability $p$ and $1-p$, is known to have a ferromagnetic ground state when $p$ is above a certain threshold value $p_c$. Below that the ground state is a spin glass, and when you go to even smaller $p$, eventually when you have $p<1-p_c$, the ground state will simply become the checkerboard type antiferromagnetic state (with finite distortions).

The point here is that precisely because your transformation does not change the spectrum of the Hamiltonian, it should not change the physics of the model, and when your starting $\{J_{ij}\}$ configuration passes through that $p_c$ value, something must change in the resulting "seemingly ferromagnetic" model too. That turns out to be that it becomes hard to find the right gauge transformation, just like it is hard to find the ground state.

$\endgroup$
4
  • $\begingroup$ I certainly understand why people loosely refer to this as a gauge transformation - it's (in a looses sense) a local symmetry operation that leaves the Hamiltonian invariant - but it this actually a gauge transformation in the strict sense of the word? I always thought that a true gauge transformation is a relabeling of individual dynamical degrees of freedom (i.e. the spins) while leaving the Hamiltonian invariant. E.g. in the quantum case, this could be achieved by conjugating the Hamiltonian with a compactly supported unitary operator... $\endgroup$
    – tparker
    Commented Sep 29, 2022 at 3:49
  • 1
    $\begingroup$ ... But in this case, you're simultaneously changing the couplings in the Hamiltonian, which are just scalars. So it can't be represented by a local unitary conjugation, and the form of the Hamiltonian itself changes (although not its spectrum). This seems like a very different "flavor" of gauge transformation, but maybe it just comes down to semantics. $\endgroup$
    – tparker
    Commented Sep 29, 2022 at 3:51
  • 1
    $\begingroup$ Yes, I agree that it has quite a different flavor from what people usually call "Gauge transformation" in condensed matter physics. The fact of the matter is that you can google "gauge transformation spin glass" etc and get tons of papers, so that's just how people call it in this field. I personally think that you can see both "gauge transformations" as exploiting some redundancy in how you represent the hamiltonian+state. $\endgroup$
    – Gitef
    Commented Sep 30, 2022 at 3:52
  • $\begingroup$ (Just for the record for future readers: in the first sentence of my first comment above, I meant to say “leaves ‘the physics’ - in this case, the energy spectrum - invariant”. The whole point of my comment is that this transformation doesn’t leave the Hamiltonian invariant.) $\endgroup$
    – tparker
    Commented Sep 30, 2022 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.