Modern computers still lack the capability to find the best solution for the classic “traveling salesman” problem. Even finding approximate solutions is challenging. But finding the shortest traveling salesman route among many different cities is more than just an academic exercise. This class of problems lies at the heart of many real-world business challenges such as scheduling delivery truck routes or discovering new pharmaceutical drugs.
Today’s computers handle combinatorial optimization problems by skipping some of the weaker solutions instead of considering all possibilities to find the very best solution. But U.S. and Japanese researchers have unveiled a new specialized computer that could someday solve the traveling salesman scenario and similar problems more efficiently. Their hybrid machine combines digital electronic circuits with
optical devices similar to lasers.
“The simplest way to solve the traveling salesman problem is to consider all possible paths, but that is not the way that a conventional computer solves it,” says Peter McMahon, a physicist at the Quantum Information Science group of Stanford University. “If you try to solve that problem on your laptop, it’s not going to naively evaluate all paths because it’s not possible for larger problem sizes.”
McMahon is part of a research group based out of Stanford University and various Japanese research institutions. The group, led by Yoshihisa Yamamoto at the National Institute of Informatics in Tokyo, Japan, published two separate but complementary papers showing the possibilities of their new computer in the 21 October 2016 online release of the journal Science.
The new computer aims to solve optimization problems through a mathematical approach known as an Ising model. The Ising model is a mathematical model that describes how magnetic materials have atomic spins that exist in either up or down states.
By mimicking an arrangement of such tiny magnets, the specialized “Ising machine” computer can represent an optimization problem as a unique configuration of up or down spin states that each interact with one another through couplings, McMahon says. The Ising machine’s solution consists of the “ground state” configuration that minimizes the system’s overall energy given that set of couplings.
‘The coupling encodes the problem you want to solve,” McMahon says. “When you specify an Ising problem, the input to the computer is the couplings between the spins. The output is ideally the ground state, the configuration of spins that minimizes the energy given that set of couplings.”
Engineers and physicists have spent years experimenting with different “Ising machine” computers to solve such optimization problems. One approach has tried brain-inspired neural networks built with electronic circuits. Another based on adiabatic quantum computing involves the D-Wave quantum annealing machines being tested by Google, NASA and Lockheed Martin. A third approach has even experimented with encoding optimization problems within biological DNA molecules as a form of molecular computing.
The combined U.S.-Japan research group took a very different approach to building Ising machines. They used pulses of light from a device similar to a laser—called an optical parametric oscillator—to represent the magnetic spins. Those light pulses were measured individually and combined with one another to form larger systems simulating arrangements of tiny magnets.
Those light pulses run through about 300 meters of optical fiber. Most of the hardware used to build the Ising machines involved off-the-shelf equipment that is standard in the telecommunications industry.
“Picture a plastic spool with a lot of optical fiber wound around it,” McMahon says. “One of nice things about this experiment is that we’re running at telecom wavelength, so all the components are standard telecom fiber, connectors, detectors, etc.”
The research group, led by Yamamoto, first developed a small working prototype of this unusual Ising machine two years ago. But they soon realized that the expensive equipment and engineering challenges necessary to make an Ising machine completely based on light pulses would be very difficult to scale, McMahon explains.
For example, a 100-spin machine would have required 99 optical delay lines and 99 modulators to control and combine the light pulses. Each of the modulators would have cost anywhere between $5,000 and $10,000.
The engineering challenge comes from the need to keep the light wavelength stabilized within 100 nanometers across the 300-meter length of optical fiber over a long period of time. That challenge would have been multiplied by 99 times if the Ising machine had 99 optical delay lines.
McMahon and his Stanford-based colleagues did succeed in creating a 100-spin machine as described in their paper published in Science. But they accomplished this by replacing the optical delay lines with digital electronic circuits. That digital component of the machine simulates the light pulse interactions that would have occurred and then translates the information back into the optical portion of the system.
“Instead of having all optical machine, now we have a hybrid that is part digital and part optical,” McMahon says.”
The Stanford group performed exhaustive testing with their 100-spin machine. They ran the machine through 4000 versions of optimizationproblems to show that the machine’s solutions are not limited to specific optimization problems. They also tested the machine’s capabilities from just a few artificial spins up to 100 spins so that they could see its performance at different system sizes.
By comparison, the Japanese researchers focused on building a much larger Ising machine that can simulate 2048 artificial spins. Their research paper showed that this Ising machine can still work at fairly large configurations. They pushed the machine’s upper limits by focusing on just three optimization problems involving all 2048 artificial spins.
But unlike the Stanford group’s 100-spin machine, the Japanese group’s larger machine had less fine-grained resolution in terms of the coupling interactions between each artificial spin. (Imagine trying to solve the traveling salesman problem with a computer that could only figure out solutions within 100-mile segments instead of within much smaller distances.)
Still, the two papers published by the U.S. and Japanese research groups complement one another by highlighting different aspects of the new Ising machine. The Stanford group’s exhaustive testing proved the Ising machine’s principles seemed solid. The Japanese group showed that the Ising machine can be scaled up to larger sizes that could someday make it a commercially viable technology. Pushing the upper boundaries of the technology was of particular interest to the researchers affiliated with NTT Corporation, a Japanese telecommunications company.
The big question with this version of an Ising machine is whether it can beat the best software algorithms running on classical computers. Both the U.S. and Japanese research groups will be carrying out such “speedup” benchmark testing over the next several years.
But the early results from their papers seem promising. The Stanford group’s 100-spin machine was able to solve certain optimization problems with about 99 percent success in about 100 milliseconds (thousandths of a second). That performance is “very comparable” to a classical digital computer, McMahon says.
The Japanese group’s 2048-spin machine actually proved 50 times faster than a “simulated annealing” classical computing algorithm on a test run involving a dense graph problem. But Hiroki Takesue, a senior research scientist at the NTT Basic Research Laboratories in Japan, cautioned that such performance on one test does not prove the Ising machine beats classical computers in general.
“This is in fact our first serious computation experiment, but surprisingly, the coherent Ising machine is already much faster than a modern computer,” Takesue says. “But note that this is confirmed only with a particular problem, so we need more research to clarify the advantages and disadvantages of the [Ising machine] over the conventional computers.”
Takesue and his Japanese colleagues plan to confirm whether or not the 2048-spin Ising machine does indeed have an advantage over classical computers in solving such dense graph problems. They also aim to boost the number of artificial spins within the Ising machine by at least 10 times over the next three years. And they hope to develop a Web interface that enables outside Internet users to test their Ising machine online.
The Japanese researchers will also begin seeing how the Ising machines could tackle real-world commercial applications. For example, NTT Corporation is interested in using the new computer for optimizing its mobile network communications. Shoko Utsunomiya, an associate professor at the National Institutes of Informatics in Japan and coauthor on one of the Science papers, is studying whether the Ising machine could help uncover new molecule configurations to discover new pharmaceutical drugs.
Meanwhile, the Stanford University group plans to continue investigating the fundamental workings of the Ising machine and to see whether it can truly outperform classical computers in general on optimization problems.
“Ultimately, you need to build a machine of a particular size and carefully benchmark it against classical solvers,” McMahon says. “There will be a lot of work in that direction in the next one to five years.”
[Source:-Spectrum]