Suppose you want to build a special machine, one that can plot a traveling salesperson’s route or schedule all the flights at an international airport. That is, the sorts of problems that are incredibly complex, with a staggering number of variables. For now, the best way to crunch the numbers for these optimization problems remains a powerful computer.
But research into developing analog optimizers—machines that manipulate physical components to determine the optimized solution—is providing insight into what is required to make them competitive with traditional computers.
To that end, a paper published today in Science Advances provides the first experimental evidence that high connectivity, or the ability for each physical component to directly interact with the others, is a vital component for these novel optimization machines. “Connectivity is very, very important, it’s not something one should ignore,” says Peter McMahon, a postdoctoral researcher at Stanford, who participated in the research.
To better grasp the concept of connectivity, imagine the famous traveling salesperson problem, in which the salesperson in question is trying to plot the most efficient route between cities. The variation of the problem with the highest connectivity is a world in which every city is connected directly to every other city by a highway. In the real world, that’s not the case—you would use the same highway for much of the route to travel from New York City to Seattle as you would to Los Angeles, for example.
What the authors of the paper found is that the higher connectivity an analog optimizer has between its components, the better its performance. To that end, the researchers compared their machine, a coherent Ising machine, to a quantum annealer built by quantum computing company D-Wave.
“The main difference between the two is the connectivity difference,” says McMahon, who also wrote for IEEE Spectrum on Ising machines. D-Wave’s quantum annealer uses qubits to model the problem being optimized, which as a general rule, makes it possible to only directly connect neighboring qubits and limits the overall connectivity. The coherent Ising machine, however, uses pulses of light that can be shuttled around, making it possible for any two pulses of interest to directly interact.
By testing the two systems on two types of optimization problems (the Sherrington-Kirkpatrick model and MAX-CUT), the researchers showed that for scenarios with high connectivity, the coherent Ising machine outperformed the quantum annealer. For example, the Ising machine solved one of the more complex problems faster than the quantum annealer by a factor of 10 million (1.2 milliseconds compared to about 167 minutes).
McMahon says the takeaway isn’t that Ising machines are better than quantum annealers, however. “The coherent Ising machine was not faster than the D-Wave machine on every problem,” McMahon points out. “It was in fact slower when you were solving problems that were sparsely connected.” That was largely a consequence of how the two machines each worked to solve problems (and both machines still solved these problems within 4 milliseconds).
Still, McMahon believes the important takeaway is that more connectivity is a boon to specialized optimizers. He says it’s less about choosing between a coherent Ising machine or a quantum annealer, and more about examining how many connections are within those machines. “No one’s going to complain about more connectivity,” he says.