Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
It sounds like a problem that was tailor-made for computers to solve, but it turns out that this classic “traveling salesman problem” is a lot more difficult than it appears on the surface. The brute-force approach of simply trying every possible route and selecting the shortest one quickly runs into the problem of exponents: Ten cities offer more than 300,000 different round-trips, but 15 cities increases the possibilities to more than 87 billion, according to Wired.
Computers based on the Ising model are believed to hold the greatest promise for solving difficult route-optimization problems such as the traveling salesman problem, as well as optimizing designs for wireless networks and identifying the best path for delivery trucks. Now researchers at Hewlett Packard Enterprise Co. say they’ve built a microprocessor that combines conventional electronics with photonics to overcome one of the greatest barriers to building Ising machines. HPE’s demonstration chip integrates 1,052 optical components, making it “the biggest and most complex in which all the photonic components work together to perform a computation,” according to IEEE Spectrum.
Photonic computers are nothing new, but building them at scale has been a problem. Route optimization solutions rely upon combining atomic elements in one of two magnetic states known as “spin up” and “spin down.” When each computational element settles into one of these two states, a beam of light can traverse them to determine the ideal route.
The problem with previous Ising model computers is that very low levels of interference, vibration or temperature variation could disrupt the delay line, which is used to ensure that spins interact properly with each other. The solution devised by HPE doesn’t use delay lines. Rather, it uses light refraction and electric heaters to adjust the optical path length of the light beams used to traverse the magnets.
“The light cycles over and over through the interferometer and the nodes, flipping spins between phases of 0 degrees and 180 degrees until the system equilibrates to a single answer,” writes IEEE Spectrum. Using light instead of electronics significantly reduces the interference problem. You can read a (somewhat) simplified description of the approach on Physics World.
The development is the latest feather in the cap of HPE, which made waves last month by showing off the first prototypes of its next-generation architecture called The Machine. With its acquisition of Silicon Graphics Inc. this past summer, HPE has begun to reestablish itself as a leader in the $11 billion high-performance computing market for applications that target some of the thorniest computing problems.