Stanford researchers develop the Ising Machine to solve “combinatorial optimization problems” and optimizing shipping and flying routes in real-time

Digital computers are about to reach their maximum

processing power within the next 10 or 25 years, leaving a certain class of

problem completely unsolved. Now, an entirely new type of computer called the

Ising Machine blends optical and electrical processing power to resolve “combinatorial

optimization problems” and find the optimal object in a set of finite objects.

If successfully scaled up, the resulting calculation could,

in real-time, determine which taxi in a fleet to route toward a fare or the optimal way to deliver packages,

reports a paper published in the journal *Science**.*

“This is a machine that’s in a sense the first in its

class, and the idea is that it opens up a sub-field of research in the area of

non-traditional computing machines,” said Peter McMahon, a postdoctoral scholar in applied physics at

Stanford University and co-author of the paper.

Combinatorial optimization problems, the specific type of

problems solved by the Ising Machine, are impossible to solve with traditional computers.

Calculating the optimal trajectory becomes increasingly complex with each additional

layer of variables introduced, requiring a recalculation and comparison of every

available combination—just like cracking a 256-bit encryption key one variable

at time.

One of the most comprehensive examples of the “combinatorial

optimization problem” is called the “traveling salesman” problem, wherein a salesperson

has to determine the most effective travel route for visiting a specific number

of cities once, before returning to the destination. With each extra city

added, the number of accountable routes quickly becomes unmanageable.

“Those problems are challenging for standard computers,

even supercomputers, because as the size grows, at some point, it takes the age

of the universe to search for all the

possible solutions,” said Alireza Marandi, a former postdoctoral scholar

at Stanford and co-author of the study. “This is true even with a

supercomputer because the growth in possibilities is so fast.”

Solving problems like the traveling salesman may have a critical

impact in a wide-range of areas, providing optimal travel paths for delivery

trucks, minimizing interference in wireless networks, and even determining how

proteins fold. With scalable potential, the team’s Ising Machine is the

precursor to the machines that’ll someday solve these challenges.

Named after a mathematical

model of ferromagnetism in statistical mechanics, the Ising machine acts

like a reprogrammable network of artificial magnets that operate at low energy,

and may only point up or down. If the connections among a network of magnets

are programmed to represent specific problems, then the final low-energy state

in which they settle yields the solution.

But instead of using magnets on a grid, the Ising Machine applies a special

laser called the degenerate optical parametric oscillator to represent the

upward- or downward-pointing “spin.” Regarding

the salesman problem, pulses of the laser represent a city’s position in a path

the salesman could take.

What’s significant here is that the Stanford Ising Machine

could be scaled-up into a practical and affordable version by replacing the

controllable optical delays with a digital electronic circuit. This enables the optical connection among the

pulses to be emulated and programmed

while the laser system solves it.

What’s significant here is that almost all the materials

used to construct the Stanford Ising Machine are

off-the-shelf elements already used for telecommunications. As a result,

scaling up the device into a practical, yet affordable version is simple. Designers

need only replace the controllable delays with digital electronic circuits that

emulate the optical connection among the pulses. Programming problems remain just as easy as before, while the laser

continues to solve them.

Stanford’s machine currently resolves problems at up to 100

variables with any arbitrary set of connections between variables. Such

capability does not surpass the processing power of traditional digital

computers even when solving combinatorial optimization problems. But as the

variables increase, computers built like the Ising Machine will gain the edge.

Source: **Stanford.edu**