Two independent teams of physicists in the US and Japan have each built versions of a new kind of computer called an “Ising machine”. The devices use physical systems to imitate a network of interacting magnetic spins with the aim of solving very complex optimization problems. Although the full potential of these Ising machines remains to be explored, the researchers say that their initial results show that their optical-fibre-based devices work just as expected. Furthermore, the research suggests that future Ising machines could outperform conventional, digital computers when it comes to discovering new drugs or optimizing the efficiency of factory production lines.
Ising machines are designed to find the best solution to problems that involve large numbers of competing alternatives. This involves performing “combinatorial optimizations” that are “NP-hard”, which means that the number of possible solutions increases exponentially with the number of components in a system. Examples of such problems include the “travelling-salesman problem” – which involves planning the shortest route linking a number of different cities – as well as the process of finding combinations of atoms and molecules that are good candidates for potential new drugs. Even the most powerful conventional computers are simply unable to provide practical solutions to these problems.
Ising machines are named after German physicist Ernst Ising, who studied the problem of how a set of spatially distributed magnetic moments arrange themselves in their lowest-energy state, given that each moment can assume one of two values: either spin-up or spin-down. For spins strung out along a line that only interact by pointing in the opposite direction as their two nearest neighbours, the answer is trivial: it is up, down, up, down, etc. But the problem becomes extremely difficult to solve when considering more general configurations in which each spin interacts arbitrarily with every other spin. The problem then is NP-hard.
Physical systems
The idea behind an Ising machine is to “map” a difficult optimization problem on to a specific Ising problem containing spins with certain couplings, and to find a physical system that will be able to solve a wide range of such problems. As Peter McMahon of Stanford University in the US points out, an Ising machine could be made simply by arranging bar magnets at certain nodes in a 2D grid and then looking to see how the magnets end up aligning with one another. One problem, he says, is that such a device would only be able to solve one specific Ising problem, dictated by the spacing – and hence coupling – between magnets.
Scientists have already worked on a number of more sophisticated alternatives. In the 1980s, John Hopfield and David Tank carried out work on neural networks in which each artificial neuron represented a spin. The firing or not-firing states of a neuron correspond to spin-up or spin-down and the weights of neural connections represent the coupling strengths. More recently, researchers at Canadian company D-Wave and elsewhere have looked to devices known as adiabatic quantum computers. These exploit the phenomenon of quantum tunnelling to place a set of quantum bits into their lowest energy state – in analogy with the Ising model.
When we constructed our machine there was no guarantee that we would get anything useful out of it so when we turned it on we got a pleasant surprise
Peter McMahon, Stanford University
According to McMahon, both of these options suffer from the fact that each spin usually only couples to nearby neighbours. That means that although such devices can still solve arbitrary problems, they must be made much bigger to do so. Typically, he says, to solve an n-spin Ising problem they need about n2 physical spins.
Light pulses
The idea for the new Ising machines came from Stanford’s Yoshihisa Yamamoto as part of the Japan Science and Technology Agency’s ImPACT programme. Yamamoto and colleagues showed in 2014 that they could build a small Ising machine by feeding a sequence of light pulses into an optical cavity. Spins were represented by pulses’ phase and were made to interact by diverting a small part of each pulse along an optical component known as a delay line, such that the pulse fragment re-entered the cavity as the next pulse passed by. But the need for many delay lines makes the approach hard to scale up and indeed the researchers only managed to process four pulses.
Now, two separate efforts, spawned from that original research, have created very similar variations on the initial device by marrying optics and electronics. Rather than sending tapped pulses along delay lines, the researchers instead measure the pulses’ phases and send that information to an electronic circuit, which adjusts the strength of a laser beam shone into the cavity in such a way as to mimic the effect of the delay lines.
Yamamoto, McMahon and colleagues at Stanford have built an Ising machine with 100 spins, each of which couples to every other spin, and have used the device to solve or find good approximate solutions to some 4000 Ising problems. Meanwhile, a group led by Hiroki Takesue of NTT Corporation near Tokyo has managed to build a machine with 2000 spins, again with complete spin–spin coupling, but in this case testing the device against just three problems.
Wireless networks
Takesue says that he and his colleagues are now testing their machine against other Ising problems and are also investigating several candidate applications, including drug discovery and the optimization of frequency channels in wireless networks. He adds that they also plan to increase the number of spins to more than 20,000 over the next three years.
McMahon is confident, on the basis of theoretical extrapolations, that the NTT machine can, like his group’s device, solve a wide range of Ising problems. But he says it is unclear whether this machine, or an even larger version of it, will outperform classical computers. “When we constructed our machine there was no guarantee that we would get anything useful out of it so when we turned it on we got a pleasant surprise,” he says. “But it remains to be seen whether this particular approach can beat state-of-the-art classical machines in real-world applications, or whether we will need a new computing architecture.”
The Ising machines are described in separate papers in Science.
