The Frustration Game

Each dot is a spin, pointing up or down. Each line is a rule about two of them: some bonds want their spins to match, others want them to differ. Click a spin to flip it and satisfy as many rules as you can. The best you can do is the ground state, and on the first few boards you'll get there in a handful of clicks. Then you reach the triangle.

Energy0

Best possible0

Rules satisfied0 / 0

≠ wants opposite spins = wants matching spins satisfied bond frustrated bond

Energy landscape

Every arrangement of the board, sorted by energy. The ring is the ground state. Watch the marker fall as you flip spins.

What the board is

A Hamiltonian. Each bond contributes one small term that scores a single pair of spins, the energy is the sum of those terms, and the ground state is whichever arrangement makes that sum as small as it will go.

Frustration: Take a loop with an odd number of bonds, all of them wanting their two spins to disagree. Start anywhere, walk round the loop forcing each bond in turn, and you arrive back where you began needing the first spin to be both up and down at once. No single rule here is hard. They just cannot all hold together, so one of them loses and the energy never reaches zero.
The quantum jump: Now let the spins be quantum, so they can sit in superposition and become entangled. The question does not change, you still want the ground energy, but answering it becomes QMA complete, which is roughly the quantum analogue of NP complete.
Still open: Nobody knows whether it stays that hard when a rough estimate would do instead of the exact number. That gap is the quantum PCP conjecture, and it has been open for well over a decade.

Inside the glass phase

Turn the disorder up and cool the system down, and the low energy states stop being one connected blob. Three sliders, three things that happen to them.

Shattering

one connected basin

The same landscape from above. Cool it and peaks rise where the clusters sit.

Past the clustering transition, the set of low energy states breaks into many separate clusters, each one small and sitting a long way from the rest. A local move cannot get you out of the cluster you started in, so anything that only makes local moves stalls. Real glasses do this. So do random SAT and random graph colouring.

Trapped in a cluster

stuck

The walker only makes small local moves, so it never leaves the cluster it started in. The barriers around it are too high and the ground state is somewhere else, in the teal cluster, so it never arrives. Restarting drops it in a random cluster, which at this size is about a 1 in 6 chance. Now push the slider up. Once the number of clusters grows exponentially, restarting stops helping.

Replica symmetry breaking

replica symmetric · one state

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 q_EA into a spread of values reaching down to small q. That function is Parisi's order parameter, and it won him a Nobel prize in 2021.

Where else this turns up

Minimising a sum of pairwise terms is not a physics problem. It is just written down first in physics.

Optimisation: Routing, scheduling and MAX CUT all map straight onto spins like these. Annealers such as D-Wave are machines built to hunt for exactly these minima.
Magnets and materials: A magnet or a material at low temperature settles into the ground state of its own Hamiltonian, so if you can work out that state, you have worked out what the material will do.
Memory and learning: Hopfield networks store each memory as an energy minimum, and recalling one means rolling downhill into whichever valley you started nearest.
Quantum simulation: Ground state energies are the quantity chemistry and materials design actually want, which is why they keep showing up as a reason to build a quantum computer at all.

Quantum Anneal heats the board so spins can hop out of bad configurations, then cools it slowly so they settle somewhere low. That is simulated annealing and it is entirely classical, despite the label on the button. A real quantum annealer would tunnel through the barriers instead of climbing over them.

There is more on the main page and in the writing. Or email me.