A century-old theoretical model of magnetism is giving rise to a hybrid computer, part classical and part quantum, that may be capable of solving problems that overwhelm conventional computers. The so-called Ising machine, described in 100-bit and 2000-bit versions in two reports this week in Science, could tackle optimization problems that require finding the best solution among myriad possibilities, such as predicting how a protein will fold.
“This is an exciting development and something that we want to pursue,” says Alán Aspuru-Guzik, a theoretical chemist at Harvard University who has studied using Ising machines to decipher protein folding. If the technology can be scaled up just a bit further, “it’s going to start competing with classical computers,” he predicts. Others are more ambivalent about the technology’s prospects.
The machines take their name from the Ising model, which was developed in 1920 by German physicist Wilhelm Lenz and his student Ernst Ising to explain how magnetism arises. In a magnetic material, each atom acts like a little magnet. At high temperatures, the atoms point in random directions so that their magnetism cancels out. Below a certain temperature, the atoms point in the same direction, magnetizing the material. The Ising model aims to capture the transition from randomness to order by envisioning a regular array of “spins” that point up or down and randomly flip depending on the temperature. In the original model, neighboring spins interact so that they tend to point in the same direction. Lenz and Ising hoped to show how the spins would suddenly snap into the same orientation as the temperature fell—although the model turned out to be fiendishly difficult to analyze.
Curiously, many optimization problems can be mapped onto more general versions of the Ising model, in which any two spins can interact, not just neighbors, and the paired spins can be set to favor alignment or opposition. For example, the spread of two contradictory opinions on the internet might be represented as an Ising model with up and down spins standing for opposite opinions. To solve a model, researchers must find the lowest energy configuration of the spins, or “ground state,” in which the most interactions are satisfied (see graphic, right).
The challenge is finding that solution. On a conventional computer, the number of steps needed to solve the model is thought to blow up exponentially as the number of spins increases, making it among the hardest computational problems.
Now, two overlapping groups at Stanford University in Palo Alto, California, and at NTT Basic Research Laboratories in Atsugi, Japan, have developed optical machines specifically designed to solve, at least approximately, the Ising model. The method is the brainchild of Yoshihisa Yamamoto, an electrical engineer at Stanford who also founded the NTT group in 1983.
In nanoseconds you have to figure out what the feedback to the next pulse will be.
The devices rely on pulses of light generated by a widget called an optical parametric oscillator (OPO) when it is zapped with laser light. The pulses course around a single long loop of optical fiber like so many wooden horses on a carousel. Each pulse is the equivalent of an atomic spin in a traditional Ising model.
Each pulse also has a “phase,” which describes whether the light waves oscillate in or out of step with the laser that zaps the OPO. The phase can be positive or negative, mimicking the up and down of a spin. As the pulses stream past, researchers measure their phases. They then use a very fast processor, which encodes the interaction constraints for the specific Ising model being analyzed, to calculate how the phases should change in order to lower the model’s total energy. When the pulses circle back through the OPO on the next lap, scientists apply feedback to nudge their phases one way or the other. “In nanoseconds you have to figure out what the feedback to the next pulse will be,” says Peter McMahon, an applied physicist at Stanford and lead author on one of the papers. After a few dozen laps, the phases evolve toward the ground state and stabilize.
Exactly how this happens remains a bit of a mystery, McMahon says. It appears crucial that each pulse start out in a quantum mechanical “squeezed state” in which its phase is, weirdly, both positive and negative at the same time, giving the system an inherent flexibility to search for solutions, he says.
Focusing on the basic technique, the Stanford group solved Ising models with up to 100 spins, using a conventional computer to check their work and see how close they were getting to ground state. Trying to scale up, the NTT group devised a 2000-spin system that solved a more limited group of problems. The devices aren’t perfect. As the number of spins grows, they most often don’t find the exact ground state, but only a low-energy approximation of it. However, for many purposes, that’s good enough, Yamamoto says.
Ising models made easy
Ising models map real-world optimization problems in terms of particles with spins, pointing up or down, and paired interactions that favor either aligned or opposing spins, such as in this eight-particle model. For the largest models, finding the optimum, lowest energy state can overwhelm conventional computers. But hybrid quantum-classical devices called Ising machines hold the promise to solve the problems easily.
Others have built Ising machines, too. Researchers at Hitachi Ltd. in Tokyo have built a device in which each spin is represented by a transistor whose voltage can be high or low. D-Wave Systems of Burnaby, Canada, has built a chip in which each spin is a tiny ring of superconducting metal in which current can run one way or the other—or, thanks to the weirdness of quantum mechanics, both ways at once. D-Wave claims, controversially, that its machine can solve the Ising model faster than an ordinary computer thanks to quantum effects, which enable it to “tunnel” directly from one possible arrangement of spins to another.
The optical Ising machines have a key advantage over the solid-state systems, says Hiroki Takesue, a physicist with the NTT group. In the Hitachi and D-Wave devices, the spins lie in a plane and only neighboring spins can interact directly. To mimic interactions with other, farther flung spins, a single spin in certain Ising problems has to be mapped onto a group of many spins on the chips. That reduces the size of the problems that the two companies’ devices can handle, to about 150 spins for the Hitachi system and a few dozen for the D-Wave chip, Takesue says. In contrast, by allowing any spin to interact with any other, the optical machines can directly encode arbitrary Ising models. “Already with 2000 spins there may be some applications” such as optimizing the use of bandwidth in Wi-Fi and cellphone networks, Takesue says.
Some researchers say it isn’t clear the Ising machines can best their primary competitors—conventional computers. “What is the case that you’re going to do something faster this way than you could do it using just an ordinary digital computer?” says Scott Aaronson, a computer scientist at the University of Texas in Austin. “I never saw that satisfactorily addressed anywhere, and it’s certainly not addressed in the present papers.”
The researchers are working on such comparisons, which can be difficult. At least on one problem, the NTT machine seems to be 50 times faster than an ordinary computer, Takesue says. In the meantime, the teams are developing a compact version of the device that could be commercialized. They are also trying to make it accessible for other researchers to use remotely. “Sometime next year,” Yamamoto says, “we will be able to connect our device to the internet.”
[Source:-Science Magazine]