# Does it help to find the ground state of a spin glass to maximize the number of ferromagnetic bonds?

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?

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.

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.