Every dot is a spin, up or down. Every line is a rule: some bonds want their two spins to match, others want them to differ. Flip spins until as many rules as possible are satisfied and you've found the ground state, the lowest energy arrangement. The first few boards are easy. Somewhere around the triangle you hit a shape where no arrangement works at all. Physicists call that frustration.
The board is a Hamiltonian: a pile of small local terms, each one scoring a single pair of spins. Minimise the total and you've found the ground state.
Take an odd loop where every bond wants disagreement. Walk around it and you come back to a contradiction, so some bond has to lose. No individual rule is complicated. The difficulty is entirely in the compromise.
Let the spins be quantum, so they can superpose and entangle. Estimating the ground energy then becomes QMA complete, roughly the quantum analogue of NP complete.
Does it stay hard when a rough estimate is all you want? That's the quantum PCP conjecture, unresolved for over a decade.
Turn up the disorder and cool it down. The low energy states reorganise in two well known ways. Drag the sliders.
Below the clustering transition the set of low energy states breaks into many clusters, each one tiny and far from the others. Local moves can't get out of the cluster they start in, so simple dynamics stall. Real glasses do this, and so do random SAT and random graph colouring.
The walker only makes small local moves, so it never leaves the cluster it started in. The barriers are too high to cross and the ground state lives somewhere else (in teal), so it never arrives. A restart drops it into a random cluster, which at this size gives it roughly a 1 in 6 shot. Push the slider up. Once the cluster count grows exponentially, restarting stops being a strategy.
The Gibbs measure splits into many pure states arranged in a hierarchy, and on the left that
hierarchy is an ultrametric tree. On the right, the overlap q between two
independent replicas stops being one fixed number: P(q) widens from a single spike at
qEA into a spread of values reaching down to small q. That
function is Parisi's order parameter.
The same optimisation problem turns up well outside physics.
Routing, scheduling and MAX CUT map straight onto spins like these. Annealers such as D-Wave are built to search for exactly these minima.
A real magnet or material at low temperature sits in the ground state of its Hamiltonian. Predicting the state is predicting the material.
Hopfield networks store memories as energy minima. Recall is downhill motion into the nearest valley.
Ground state energies are what chemistry and materials design actually need, and one of the better arguments for building a quantum computer.
Anneal heats the system so spins can hop out of bad configurations, then cools it slowly until things settle low. That's simulated annealing, and it's entirely classical. A real quantum annealer tunnels through the barriers instead of climbing over them.