SAN FRANCISCO, Oct. 20 -- A team of researchers has combined optical and electronic technology to build a special-purpose computer capable of handling a particular class of problem that involves combining variables to come up with many possible answers, and looking for the best solution.
Traditional computers, even at its current maximum power, find it difficult to solve the special type of problem, called a combinatorial optimization problem. An example is what's known as the "traveling salesman" problem, wherein a salesman has to visit a specific set of cities, each only once, and return to the first city, and the salesman wants to take the most efficient route possible.
It may seem simple, but the number of possible routes increases extremely rapidly as cities are added, and this underlies why the problem is difficult to solve.
"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 through all the possible solutions," said Alireza Marandi, a former postdoctoral scholar at Stanford University on the U.S. west coast and co-author of a study published on Thursday in the journal Science. "This is true even with a supercomputer because the growth in possibilities is so fast."
Solving such hard optimization problems could have enormous impact in a wide range of areas, for instance finding the optimal path for delivery trucks, minimizing interference in wireless networks, and determining how proteins fold. Even small improvements in some of these areas could result in massive monetary savings.
For that end, the Stanford team has built what's called an Ising machine, named for a mathematical model of magnetism. It acts like a reprogrammable network of artificial magnets where each magnet only points up or down and, like a real magnetic system, and is expected to tend toward operating at low energy. The theory is that, if the connections among a network of magnets can be programmed to represent the problem at hand, once they settle on the optimal, low-energy directions they should face, the solution can be derived from their final state.
In the case of the traveling salesman, each artificial magnet in the Ising machine represents the position of a city in a particular path.
Rather than using magnets on a grid, according to a news release from Stanford, the team used a special kind of laser system, known as a degenerate optical parametric oscillator, that, when turned on, will represent an upward- or downward-pointing "spin." Pulses of the laser represent a city's position in a path the salesman could take.
In an earlier version of this machine, the team members extracted a small portion of each pulse, delayed it and added a controlled amount of that portion to the subsequent pulses. In traveling salesman terms, this is how they program the machine with the connections and distances between the cities. The pulse-to-pulse couplings constitute the programming of the problem. Then the machine is turned on to try to find a solution, which can be obtained by measuring the final output phases of the pulses.
The problem in this previous approach was connecting large numbers of pulses in arbitrarily complex ways. It was doable but required an added controllable optical delay for each pulse, which was costly and difficult to implement.
The latest Stanford machine shows that a drastically more affordable and practical version could be made by replacing the controllable optical delays with a digital electronic circuit, which emulates the optical connections among the pulses in order to program the problem and the laser system still solves it. Nearly all of the materials used to make this machine are off-the-shelf elements that are already used for telecommunications. That, in combination with the simplicity of the programming, makes it easy to scale up.
Currently able to solve 100-variable problems with any arbitrary set of connections between variables, the machine has been tested on thousands of scenarios.
"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, postdoctoral scholar in applied physics and co-author of the paper. "There are many, many questions that this development raises and we expect that over the next few years, several groups are going to be investigating this class of machine and looking into how this approach will pan out."
