Pushing computers to solve ‘unsolvable’ problems
A groundbreaking method by a Northeastern researcher will help computers solve optimization problems used to minimize costs and energy.
Don’t underestimate the power of a yes-or-no question.
Some of the toughest computing problems boil down to thousands of tiny yes-or-no decisions. Finding the best combination of answers could be the key to anything from nailing a new drug to keeping a city of commuters on the move. For example, take this scenario:
It’s World Cup season, and hundreds of fans flocking to the stadium log into a ride-sharing app to get there by kickoff. At the same time, others are rushing to the airport, hitting the gym or going on a grocery run. About 10,000 active drivers are scattered across the city, with around half free to jump on the requests. There are traffic jams, flaky riders who show up late or ghost the driver altogether. How do you match everyone up so drivers cash in on the rush while riders reach their destinations without breaking the bank?
This is an example of a problem known as quadratic unconstrained binary optimization (QUBO), a mathematical equation that aims to find the best possible combination of yes-or-no choices to minimize cost or energy expenditure. By translating the situation into mathematical terms, the method makes it possible to solve for the optimal outcome in a straightforward way that yields a single answer.
As Northeastern electrical and computer engineering professor Cristian Cassella put it, QUBO problems “are of fundamental importance in many disciplines, from drug discovery to logistics, as well as wireless communications.”
The power of QUBO problems is their ability to reduce complex decision-making scenarios to a single expression that accounts for hundreds of individual choices, all of which play a role in the outcome. For example, a match between a particular driver and rider using the ride-sharing app counts as a choice, while a selection of one route over a different one counts as another. Each is represented by the score of 1 or 0 and contributes to the overall tally. The goal is to get the lowest score, which represents the combination of choices that minimizes cost or energy expenditure for everyone involved.
Useful at the macro and micro scale alike, QUBO problems can also be used to study protein shape by representing each twist and turn of the folded amino acid chain that affects the overall stability of the molecule as a yes-or-no choice.
Researchers and tech collaborations are already actively using QUBO methods to predict 3D protein structures at record speeds. And given that many diseases, such as Alzheimer’s, are marked by protein misfolding, the failure of a protein to achieve the 3D shape that allows it to function properly, a better understanding of how proteins are supposed to fold could help scientists figure out what happens when things go wrong.
But how do you solve an equation with so many variables? According to Alejandro Montanez, a quantum physics expert at the Jülich Supercomputing Centre in Jülich, Germany, who uses quantum computing methods to solve QUBO problems, the total number of possible combinations can quickly skyrocket to the point that most real-world scenarios involving 10 or more choices would have you number-crunching until the cows come home.
A popular method involves Ising machines, which use concepts from physics to tackle the task, Cassella explained. They work by translating the QUBO problem into a different language — one that describes how electron particles in a material such as iron arrange themselves. Each yes-or-no choice is now represented by a binary property of an electron known as its spin number. You can picture the chunk of iron as a giant switchboard, with electrons in each atom as individual switches that can be in the “on” or “off” position. The particular configuration of the switches — which ones are in the on vs. off setting — represents the state they will naturally be found in and matches the answer to the QUBO problem.
Why bother making this conversion at all? Scientists have spent decades figuring out how to solve spin system problems and there are lots of shortcuts and tools to help.
Unfortunately, there’s one snag — the “local minima” trap, a common problem that prevents Ising machines from giving the best answer. It represents a partial answer to the optimization problem — a configuration that minimizes cost or energy to some degree, but not as much as it potentially could.
Cassella compared the Ising machine to a person hiking through a landscape with lots of ridges and grooves in search of the deepest valley. The hiker wanders into a valley that seems promising because it appears to be the lowest possible point. But it turns out that it’s not. There’s a deeper bottom to reach, but the oblivious hiker doesn’t look any further. He’s pitching his tent and setting up a propane stove to roast marshmallows without realizing he’s gotten stuck in a “local” valley that’s not actually the deepest point in the landscape.
In QUBO terms, the rut that the hiker is stuck in corresponds to the local minima — a combination of yes-or-no choices that represents a decent solution to the problem, but doesn’t optimize cost, energy or other factors as much as possible. For example, a local minima in the context of the ride-sharing problem could be a match between riders and drivers that gets people where they need to go, but doesn’t do so efficiently. There’s another way to match everyone up that would allow more fans to arrive at the stadium on time and for more drivers to walk away with bigger checks, ensuring that both sides profit.
Cassella and his team developed the Analog Floquet Solver as a way to get around the problem of Ising machines settling for answers that don’t represent the best possible combination of choices, or the global minima.
Floquet theory is used to describe the behavior of a system hit with a periodic force that pushes, shakes or illuminates it in a repeating pattern, like a pulsing laser or a spinning washing machine.
Editor’s Picks
It gives the metaphorical hiker a much-needed shove, Cassella explained.
“We found a way to provide some degree of energy to the system that allows the machine, as it goes down, to keep jumping,” he said. As the hiker hops over the edge of that shallow dent he initially settled in, he keeps going and can finally get to the true bottom of the valley that represents “the optimum solution of the problem,” Cassella said.
With the Floquet method, Cassella said he and his colleagues were able “to solve some problems that have never been solved before” in record speed. They found accurate answers to equations with as many as 10,000 variables and saw “nine orders of magnitude of improvement in terms of energy consumption,” according to Cassella.
He said all of this bodes very well for the future. The method sets scientists on the path to finally be able to solve optimization problems that affect many disciplines, including those in the areas of economics, finance, drug discovery, biology, engineering, wireless communication and more, Cassella explained.
“In every single area there are problems that currently are unsolvable,” he added. With the new paradigm in hand, solutions may very well be within reach.
