# How are Disordered Magnets and Wedding Seating Charts Connected?

(Inside Science) -- Earlier this month, the Royal Swedish Academy of Sciences awarded half of the Nobel Prize in physics to Giorgio Parisi, an Italian physicist. The academy highlighted his method for solving a problem connected to models of spin glasses, magnetic materials lacking the ordered structure of other magnets.

While this research may sound more niche than the climate modeling that won the other half of the Nobel, “spin glass methods have now been used successfully to understand important questions” in subjects including information theory, electrical engineering and theoretical computer science, said Aukosh Jagannath, a mathematician at the University of Waterloo in Ontario.

### What are spin glasses?

These magnetic materials are called spin “glasses” because their disorder is analogous to that of window glass. In some solid objects, the atoms are neatly and predictably organized. But in window glass, atoms are randomly arranged -- some are close together, some are far apart.

Similarly, in spin glasses, so-called magnetic moments “point” in random directions. You can

think of magnetic moments “as tiny little mini-magnets,” said Helmut Katzgraber, a statistical physicist who works at the Amazon Quantum Solutions Lab in Seattle. They have a property that can express itself in one of two ways -- the moment can “point up,” or “point down,” and the direction it points depends on which direction its neighbors are pointing. The moment either wants to point in the same or opposite direction as each neighbor, depending on the connection between them.

In regular magnets, the moments can easily orient themselves in a way that satisfies the connections to each of its neighbors -- all the connections require the moment point down, for example. But in spin glasses, some moments might want to point up based on one neighbor’s direction and point down based on another neighbor’s direction, so it’s not clear which direction the moment will point. When moments are compelled to point in two different directions, the system is “frustrated” -- a key property of spin glasses.

### Finding low-energy states

Condensed matter physicists are interested in finding stable states a system might settle into, and stable states have low energy. The energy of a system depends on the directions the moments are pointing, so describing stable states requires knowing how the moments will behave. But due to properties like frustration, it’s “extremely hard to analyze the spin system,” Jagannath said.

Katzgraber likens the problem to trying to design a seating chart for a wedding, where a low-energy state is one that makes as many people as possible happy with their seat. Even at a wedding with only 16 guests, there are over a trillion different ways to arrange them around one table. The number of states becomes, from a human perspective, infinitely large when you’re looking at a few grams of a magnet, which contain many more moments than the number of seconds the universe has existed.

Parisi’s innovation was a method for finding these low-energy states, and “this solution method that he developed for spin glasses turns out to be extremely useful across many, many disciplines,” said Katzgraber.

### Applying spin glass solutions to other problems

It turns out that this problem of finding low-energy states of spin glasses is similar to combinatorial optimization problems. Optimization problems involve minimizing, say, the cost or time it takes to do something. An optimization problem is “combinatorial” when it involves finding optimal combinations of discrete objects, like people sitting around a table. There are other optimization problems that aren’t combinatorial, like calculating the most fuel-efficient speed for driving a car, where the thing you’re optimizing can take any value within a range.

A classic example of a combinatorial optimization problem is the traveling salesperson who wants to visit a bunch of cities and take the route that minimizes their distance traveled. Making as many of the wedding guests as possible happy with the seating arrangement is an optimization problem.

As another example, Katzgraber described an airplane made from around 100,000 pieces. If some of these parts are broken (say, the pilot’s seat), the plane won’t be safe to fly. If other parts are broken -- say, a passenger’s seat -- the plane can still be flown, just with one fewer passenger. The company has to find all the combinations of broken parts for which the plane is not safe to fly.

“This problem is so difficult that it eats up about a third of the cost of the whole validation process before it flies,” said Katzgraber. So finding more efficient ways to solve this problem can save a lot of money.

At its core, this problem is similar to a spin glass problem. The plane’s parts are like moments, and whether they work or not can be thought of as a moment pointing up or down. And in this scenario, a “low-energy state” might be one where the plane can fly.

“Anything that is combinatorial optimization mathematically is just a cousin of a spin glass,” Katgraber said.

And Parisi’s work has applications beyond combinatorial optimization. “There are so many people who are card-carrying computer scientists, card-carrying statisticians, card-carrying machine learners who are using ideas that came from these insights of Parisi,” Jagannath said. “It’s not just a profound influence on physics. It’s a profound influence on science and math and engineering.”