Questions tagged [spin-glasses]

For questions related to spin glasses which are disordered materials that admit particularly simple mathematical models such as the Ising model with random couplings.

Spin glasses are materials with disordered interactions that admit a simple description, e.g. using an Ising model with random coupling constants. These materials have numerous metastable states and have been studied extensively from the physics and computational complexity point of view.

4 questions
15
votes
3 answers

Are spin-glass problems NP (-complete)?

It is well known that finding ground states for spin-glass systems (Ising, XY...) is NP-hard (at least as hard as the hardest NP-problems) so that they can be efficiently used to solve other NP problems like the Traveling Salesman Problem. My…
Wouter
  • 311
  • 2
  • 9
12
votes
2 answers

Is there a general method of expressing optimization problem as a Hamiltonian?

Let's say, that we have an optimization problem in the form: $$ \min_x f(x) \\ g_i(x) \leq 0, i = 1, ..., m \\ h_j(x) = 0, j = 1, ..., p, $$ where $f(x)$ is an objective function, $g_i(x)$ are inequality constraints and $h_j(x)$ are equality…
brzepkowski
  • 1,069
  • 7
  • 19
6
votes
1 answer

How to show mathematically the equivalency between Ising Model and QUBO?

It is said that the Ising Model using spin variables $s ∈ \{−1, 1\}$ $$H(s)=\sum_{i}h_is_i+\sum_{i
26118in
  • 508
  • 5
  • 15
4
votes
1 answer

Does the D-Wave hardware show any advantage for academic use-cases, for example in condensed matter physics?

The D-Wave team put out a few papers (like this one and this one) in the last few years describing how their methods can find ground states of certain spin-glass Hamiltonians faster than classical methods for an equivalent accuracy (more or less).…