Solving Complex Optimization Equations with the Analog Floquet Solver
ECE Associate Professor Cristian Cassella and his team developed the Analog Floquet Solver, a groundbreaking method that prevents physics-based Ising machines from getting stuck in partial solutions, allowing computers to successfully solve highly complex real-world optimization problems across fields like logistics, finance, and drug discovery.
This article originally appeared on Northeastern Global News. It was published by Katya Poltorak. Main photo: Solving real-world optimization problems requires finding the best combination among countless possibilities. Photo by Matthew Modoono/Northeastern University
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.
Gernot Füchsel, Stefano Melchionna, Alejandro Gómez Cadavid and Pranav Chandarana solve QUBO problems at Kipu Quantum, a company that applies quantum research to real-world solutions in Berlin, Germany. They work with customers in domains ranging from finance to logistics and chemistry. In every problem, “there is a large number of variables, but only one configuration that is most optimal,” Füchsel said.
So 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.
Northeastern professor Cristian Cassella has developed a better way to solve optimization problems. The discovery has potential to impact many industries, from finance to medicine. Photo by Matthew Modoono/Northeastern University
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.
Read full story at Northeastern Global News