The processing power of standard computers is likely to reach its maximum in the next 10 to 25 years. Even at this maximum power, traditional computers won't be able to handle a particular class of problem that involves combining variables to come up with many possible answers, and looking for the best solution.
Now, an entirely new type of computer that blends optical and electrical processing, reported Oct. 20 in the journal Science, could get around this impending processing constraint and solve those problems. If it can be scaled up, this non-traditional computer could save costs by finding more optimal solutions to problems that have an incredibly high number of possible solutions.
"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."
The traveling salesman problem
There is a special type of problem - called a combinatorial optimization problem - that traditional computers find difficult to solve, even approximately. 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. This problem 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 and co-author of the study. "This is true even with a supercomputer because the growth in possibilities is so fast."
It may be tempting to simply give up on the traveling salesman, but solving such hard optimization problems could have enormous impact in a wide range of areas. Examples include 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, which is why some scientists have spent their careers creating algorithms that produce very good approximate solutions to this type of problem.
An Ising machine
The Stanford team has built what's called an Ising machine, named for a mathematical model of magnetism. The machine acts like a reprogrammable network of artificial magnets where each magnet only points up or down and, like a real magnetic system, it 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, the Stanford 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 (published two years ago), 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 Ising machine shows that a drastically more affordable and practical version could be made by replacing the controllable optical delays with a digital electronic circuit. The circuit 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. Stanford's machine is currently able to solve 100-variable problems with any arbitrary set of connections between variables, and it has been tested on thousands of scenarios.
A group at NTT in Japan that consulted with Stanford's team has also created an independent version of the machine; its study has been published alongside Stanford's by Science. For now, the Ising machine still falls short of beating the processing power of traditional digital computers when it comes to combinatorial optimization. But it is gaining ground fast and the researchers are looking forward to seeing what other work will be possible based on this breakthrough.
"I think it's an exciting avenue of exploration for finding alternative computers. It can get us closer to more efficient ways of tackling some of the most daunting computational problems we have," said Marandi. "So far, we've made a laser-based computer that can target some of these problems, and we have already shown some promising results."
Additional authors are Ryan Hamerly, Carsten Langrock, Robert L. Byer, M. M. Fejer, Hideo Mabuchi, and Yoshihisa Yamamoto of Stanford University. Researchers from the National Institute of Informatics (Japan), University of Tokyo, NTT Basic Research Laboratories, and the ImPACT Program were also co-authors.
This research was funded by the Impulsing Paradigm Change through Disruptive Technologies (ImPACT) Program of the Council of Science, Technology and In-novation (Cabinet Office, Government of Japan). McMahon was partially supported by a Stanford Nano- and Quantum Science and Engineering Postdoctoral Fellowship.
Taylor Kubota | EurekAlert!
Next Generation Cryptography
20.03.2018 | Fraunhofer-Institut für Sichere Informationstechnologie SIT
TIB’s Visual Analytics Research Group to develop methods for person detection and visualisation
19.03.2018 | Technische Informationsbibliothek (TIB)
Satellites in near-Earth orbit are at risk due to the steady increase in space debris. But their mission in the areas of telecommunications, navigation or weather forecasts is essential for society. Fraunhofer FHR therefore develops radar-based systems which allow the detection, tracking and cataloging of even the smallest particles of debris. Satellite operators who have access to our data are in a better position to plan evasive maneuvers and prevent destructive collisions. From April, 25-29 2018, Fraunhofer FHR and its partners will exhibit the complementary radar systems TIRA and GESTRA as well as the latest radar techniques for space observation across three stands at the ILA Berlin.
The "traffic situation" in space is very tense: the Earth is currently being orbited not only by countless satellites but also by a large volume of space...
An international team of researchers has discovered a new anti-cancer protein. The protein, called LHPP, prevents the uncontrolled proliferation of cancer cells in the liver. The researchers led by Prof. Michael N. Hall from the Biozentrum, University of Basel, report in “Nature” that LHPP can also serve as a biomarker for the diagnosis and prognosis of liver cancer.
The incidence of liver cancer, also known as hepatocellular carcinoma, is steadily increasing. In the last twenty years, the number of cases has almost doubled...
In just a few weeks from now, the Chinese space station Tiangong-1 will re-enter the Earth's atmosphere where it will to a large extent burn up. It is possible that some debris will reach the Earth's surface. Tiangong-1 is orbiting the Earth uncontrolled at a speed of approx. 29,000 km/h.Currently the prognosis relating to the time of impact currently lies within a window of several days. The scientists at Fraunhofer FHR have already been monitoring Tiangong-1 for a number of weeks with their TIRA system, one of the most powerful space observation radars in the world, with a view to supporting the German Space Situational Awareness Center and the ESA with their re-entry forecasts.
Following the loss of radio contact with Tiangong-1 in 2016 and due to the low orbital height, it is now inevitable that the Chinese space station will...
Fraunhofer Institute for Organic Electronics, Electron Beam and Plasma Technology FEP, provider of research and development services for OLED lighting solutions, announces the founding of the “OLED Licht Forum” and presents latest OLED design and lighting solutions during light+building, from March 18th – 23rd, 2018 in Frankfurt a.M./Germany, at booth no. F91 in Hall 4.0.
They are united in their passion for OLED (organic light emitting diodes) lighting with all of its unique facets and application possibilities. Thus experts in...
A new scenario seeking to explain how Mars' putative oceans came and went over the last 4 billion years implies that the oceans formed several hundred million...
23.03.2018 | Event News
19.03.2018 | Event News
16.03.2018 | Event News
23.03.2018 | Materials Sciences
23.03.2018 | Agricultural and Forestry Science
23.03.2018 | Physics and Astronomy