Is it harder to find the ground state of a classical spin glass with equal or unequal bond stengths? Consider two different models for a classical spin glass in zero applied field, where the degrees of freedom are $\{ s_i = \pm 1\}$. The first model is
$$H = \sum_{i < j} J_{ij} s_j s_j,$$
where the $J_{ij}$ are arbitrary real constants. The second model is
$$H = J \sum_{i < j} (\pm)_i s_j s_j,$$
i.e. all bonds have the same magnitude, but their signs are arbitrary.
For which model is it harder to find an exact or approximate ground state for a fixed number of spins $N$?
I could imagine arguing it either way. On the one hard, the former case of arbitrary couplings has a much larger problem state space of $\mathbb{R}^N$, vs. ${\pm 1}^N$ for the latter problem. There could also be some clever way to exploit the fact that all bonds have the same magnitude in the latter model to solve the problem more efficiently. This would suggest that the former model is harder to solve.
On the other hand, for variable bond strengths, it's more important to satisfy the strongest bonds than the weakest bonds. This suggests a heuristic strategy of satisfying the strongest bonds first and then sequentially trying to satisfy weaker and weaker bonds without de-satisfying the stronger ones. This would suggest that the latter model is harder to solve, because that heuristic strategy doesn't work.
 A: I think it really depends on what kind of comparison you would like to have.

*

*If you want to think about the worst-case analysis, then they both are NP-hard as optimization problems, and NP-complete as decision problems. This would be the answer if I interpret your phrase "arbitrary real constants" as an adversarial setup, where we want to think about the worst possible cases.
Actually, if I want to be very precise, the real-valued version must have some kind of a precision promise, because otherwise we can have a "trivially hard" situation where you have two bonds with $J_{ij}=1.000.....0001$ vs $J_{ik}=1.000.....0002$ and you may need to look through arbitrarily many decimals to really decide the ground state. In computer science, people usually avoid this boring type of hardness by just asking an inverse-polynomial precision. You can look for local hamiltonian problems etc to see the inverse-polynomial "promise gap". I assume from the fact that you write "approximate ground state", you would be OK with this kind of modifications.


*The two models are basically the Sherrington-Kirkpatrick model and the $\pm J$ model if you are drawing the real coefficients from a Gaussian distribution and from a fair coin for the $\pm 1$ case. But in this case, the problem has a natural probability distribution over instances and it would be less meaningful to think about the worst-case. In both cases, we know that the model goes through a Full replica symmetry breaking (full-RSB) phase transition at some temperature. Basically this means that we don't know an efficient algorithm to sample approximate solutions with a finite ratio tolerance level corresponding to that temperature or below.


*If you further go into the second direction, there are folklores like "full-RSB phases are somewhat easier than the 1-step RSB phase" etc, which I personally am not fully convinced. There are other folklores like "the more continuous the model is, the relatively easier it becomes", which does make sense, because you always have at least some epsilon move that doesn't change the energy that much.
I don't know much about the heuristics. It is likely that the performance of heuristics also depends a lot on the details of the setup.
