The Traveling Salesperson Problem was Solved with the Help of Nature

This generation’s most advanced computers still tussle to solve, in a realistic time-frame, combinatorial optimization problems, or those problems that include combining via large groups of possibilities to reach the best result.

Quantum computers now hold the potential to solve these problems. However, increasing the number of quantum bits in these machines is still a struggle.

Recently, MIT Lincoln Laboratory scientists have revealed an alternative, a parallel-based method to accelerate the solving of these problems.

Jeffrey Chou, the co-lead author of the research published in Nature’s Scientific Reports, said that the team’s computer functions by calculating with physics and uses nature to help come to an outcome of these optimization problems.

The machine is made of regular electronic elements but allows the researchers to scale the computer rapidly and in an affordable manner by putting to use the existing microchip industry.

Solving Optimization Problems

Probably the most popular combinatorial optimization problem is that of the traveling salesperson. It requires to discover the shortest route a salesperson can follow through several cities, starting and ending at the same one.

It may appear to be simple when put face to face with only a few cities, but it becomes more and more difficult to solve as the number of cities increase. This kind of problem puts into an impasse even the most advanced supercomputer.

Still, optimization problems require solving in the real world day by day. The solutions are used to set shifts, reduce financial risk, identify drugs, and much more. Finding good solutions in a substantially short period of time could save industries billions of dollars. Therefore, researchers have been seeking new methods to create systems designed particularly for optimization.

Nature for the Win

Nature is usually optimizing energy or achieving goals in the most effective and dispersed way. This law can be found in the synchrony of nature, such as heart cells pulsing together. Likewise, if you set two pendulum clocks on the same surface, irrelevant on when the singular pendula are put in action, they will ultimately end up moving into a synchronized rhythm. They will also reach their peak at the exact same time, but lulling in reverse directions.

“We’ve essentially built an electronic, programmable version of this [clock setup] using coupled nonlinear oscillators,” Chou says, showing a YouTube video of metronomes displaying a similar phenomenon. “The idea is that if you set up a system that encodes your problem’s energy landscape, then the system will naturally try to minimize the energy by synchronizing, and in doing so, will settle on the best solution. We can then read out this solution.”

The prototype the researchers came up with is a type of Ising machine, a computer created after a model in physics that involves an array of magnets, each of it having a magnetic tilt orientation that cam aim upwards or downwards.

Each tilt’s final orientation is in direct dependency on its interaction with every other spin. The goal of an Ising machine is to discover, considering a particular coupling strength network, the accurate structure of each spin, which reduces the general system energy.

A Cheap Solution

How can, though, an Ising machine resolve an optimization problem?

It was proven that problems could be inserted straight into the Ising model so that a group of spins with particular coupling weights can symbolize each city and the distances between them in the above-mentioned problem.

Therefore, discovering the lowest-energy structure of spins represents the solution for the salesperson’s fastest route. Even so, solving this problem by separately verifying every possible configuration turns into a difficulty when the problems increase.

“This work from Lincoln Laboratory makes innovative use of a crossbar architecture in its construction of an analog-electronic Ising machine,” says Peter McMahon, an assistant professor of applied and engineering physics at Cornell University who was not part of the research team. “It will be interesting to see how future developments of this architecture and platform perform.”  

The team is now developing a plan which will scale the prototype to larger numbers of oscillators or ‘nodes’ and design it on a printed circuit board. The technology used in the laboratory for this invention is based on standard electronic components. Therefore, it is incredibly affordable. All the elements that constructed researchers’ prototype can be found in a regular electrical engineering lab and were bought online for only $20.

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *