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.