Nature can help solve optimization problems

[Jim__]

From TechXplore:

Today's best digital computers still struggle to solve, in a practical time frame, a certain class of problem: combinatorial optimization problems, or those that involve combing through large sets of possibilities to find the best solution. Quantum computers hold potential to take on these problems, but scaling up the number of quantum bits in these systems remains a hurdle.

Now, MIT Lincoln Laboratory researchers have demonstrated an alternative, analog-based way to accelerate the computing of these problems. "Our computer works by 'computing with physics' and uses nature itself to help solve these tough optimization problems," says Jeffrey Chou, co-lead author of a paper about this work published in Nature's Scientific Reports. "It's made of standard electronic components, allowing us to scale our computer quickly and cheaply by leveraging the existing microchip industry."

Perhaps the most well-known combinatorial optimization problem is that of the traveling salesperson. The problem asks to find the shortest route a salesperson can take through a number of cities, starting and ending at the same one. It may seem simple with only a few cities, but the problem becomes exponentially difficult to solve as the number of cities grows, bogging down even the best supercomputers. Yet optimization problems need to be solved in the real world daily; the solutions are used to schedule shifts, minimize financial risk, discover drugs, plan shipments, reduce interference on wireless networks, and much more.

"It has been known for a very long time that digital computers are fundamentally bad at solving these types of problems," says Suraj Bramhavar, also a co-lead author. "Many of the algorithms that have been devised to find solutions have to trade off solution quality for time. Finding the absolute optimum solution winds up taking an unreasonably long time when the problem sizes grow." Finding better solutions and doing so in dramatically less time could save industries billions of dollars. Thus, researchers have been searching for new ways to build systems designed specifically for optimization.

more ...