To solve the most difficult optimization tasks, just add lasers

A strange device, known as the "Ising Optical Machine", is able to control air traffic and help the NFL schedule games

Last year, a failure in the distribution system of work between American Airlines employees could lead to a disruption of thousands of flights during the holiday season. The error allowed pilots to abandon flights without being replaced by another pilot, and about 15,000 flights were under threat. And although the airline was able to track down the problem and distribute employees on time , this mess became a reminder of how much we depend on computers in organizing the work schedule of a huge number of services and functions, on which our community now completely depends.

For example, all major airlines have complex graphics optimization algorithms that compare pilots and flights. And although the incident with American Airlines occurred not directly due to the fault of the algorithm, the result could be similar. Such a refusal would have led to the fact that hundreds of thousands of people would be in a difficult or very uncomfortable position while the airline was looking for a way out of the situation.

The triumph of algorithmic science and Moore's law is that we can now approach the many complex tasks of optimization, including such areas as transportation, logistics and scheduling. Most of the modern world cannot function normally without these algorithms: 50,000 cargo ships transport goods annually, 25,000 TWh of electricity is produced, and 1 Zettabyte of traffic is routed through routers. All this would have worked much less effectively. However, organizations often work with suboptimal solutions due to tight deadlines and a lack of available computer resources. Moreover, there are still plenty of opportunities to improve the methods we use to help solve most of the optimization problems.
')
Considering the importance of optimization and the fact that the era of stable and large-scale improvements in processor performance seems to be coming to an end, researchers began to study whether machines specifically designed for optimization can significantly improve our ability to solve complex problems.

One promising approach is the development of optical machines for optimization. A group of scientists from Stanford University (which includes the author of the article) under the leadership of Yoshihik Yamamoto began this research seven years ago. Now this topic is being studied by several groups of scientists, as well as researchers from HP and NTT laboratories. After years of work, there is growing confidence that at least one of these groups will someday be able to create a machine that could help us approach some of the most difficult optimization problems that modern industry requires.


The traveling salesman problem: the complexity of such tasks as finding the shortest path between several points increases with the number of points. Modeling them in the guise of Ising optimization problems can help solve them faster.

Recall the classic traveling salesman problem in which the traveling salesman moves from city to city selling goods. He does not want to waste time and money on gasoline. This optimization task, whose goal is to find the shortest path for the traveling salesman, given that he needs to get to each point once, and at the end of the journey he wants to return to where he started.

For five cities the problem is solved simply. It can be calculated by simply considering all 12 paths . However, if the hard worker-seller intends to visit 50 cities, then the brute force method, considering all possible paths, will be overwhelming - there will be more of these paths than a no- million , or 10 ⁶⁰ - one and 60 zeros.

Possible solutions to this problem can give us algorithms that use different workarounds and reasonable approximations. But even the best of them can make you think the most powerful computer. In a recent example, the University of Waterloo from Canada tried to find the shortest path between the nearly 50,000 US cities that entered the national register of historic sites and prove the correctness of their decision. For this, he used 310 powerful processors that worked without stopping for 9 months.

But much more tasks are related to optimization than the traveling salesman task. Another challenge is scheduling. For example, the National Football League in the United States must annually schedule several hundred games while trying to comply with thousands of rules that, for example, prohibit teams from playing more than three games not in their field in a row. To solve this problem in 2017, the NFL used a cluster of 400 computers .


Ising optimization : in this Ising problem, the energy of the system is lower when the spins of its electrons are directed in directions opposite to the spins of their neighbors. Systems capable of finding a state with minimal energy in the Ising model can help speed up the solution of complex optimization problems.

Manufacturing enterprises need to plan machine maintenance. Universities need to schedule classes. Postal services need to plan delivery routes. Large cities, for example, Beijing or Tokyo, would love to learn how to effectively manage the flow of millions of cars trying to drive through their streets at peak times. These tasks can include hundreds or thousands of events that need to be planned, and in many cases practical solutions are still unavailable because they require too much computer time or too many computers.

Researchers have been trying for many years to create special machines for solving optimization problems. In the mid-1980s, David Tank, then working in the AT & T Bell laboratories, and John Hopfield, who worked both at AT & T Bell and Caltech, suggested using analog electronic circuits representing neural networks to solve such optimization problems as a traveling salesman. Their work has generated decades of research in this area. Then in 1994, Leonard Adleman of the University of Southern California discovered that in DNA theory, he could be used to solve problems of this type. His idea gave rise to a similar flurry of research. However, these attempts to develop radically new and effective approaches to solving optimization problems have led to practical alternatives to conventional computers and technologies, which remain today the main tools for solving such problems.

Attempts to create special optical machines capable of solving optimization problems focused on one of these tasks, known as Ising optimization. It was named after the physicist Ernst Ising, the famous work on the model of magnetic moments and its explanation of the transitions between different magnetic states. It turns out that many common optimization problems, including scheduling and finding ways, can easily be turned into Ising optimization problems.

To understand how the Ising model is related to optimization, you need to start by using it in physics to understand magnetism. Consider a conventional magnetic bar. Using the Ising model, one can imagine a magnetic bar as a three-dimensional lattice of atoms, in which each of the atoms itself is a magnetic bar. Electrons in atoms have a property called spin. The spins of the valence electrons — located on the outer shells of an atom — are directed either up or down. The direction of the spins determines the magnetization of the material. If all the backs are pointing up, the material is magnetized. If down, the material is also magnetized - only with opposite polarity. If the backs are mixed, the material is not magnetized.

These spins also interact with each other. In a magnetic bar, the " total energy " of two neighboring electrons is lower if their spins are aligned - that is, directed in the same direction. Conversely, their total energy is higher if the backs are multidirectional.


Optical Ising machine: optical parametric oscillator (OPO) with measurement feedback can solve optimization problems expressed in the form of the Ising model - a set of electron spins and their influence on each other. The phases of the optical pulses in the OPO represent the spins, and the influence is introduced into the user-programmable gate array ( FPVM ). You need to make about a hundred passes through the system before the impulses in the OPO become powerful enough to produce a solution to the problem.

In the Ising model, we summarize the energy of interactions between the spins of each pair of electrons in a set of atoms. Since the amount of energy depends on whether the spins are aligned or not, the total energy of the set depends on the direction of all the spins of the system. Thus, the general problem of optimizing the Ising is to determine the state in which the spins should be in order to minimize the energy of the system.

In the simplest model, it is believed that only adjacent spins interact. However, in the general Ising optimization problem, any spin can interact with any other, regardless of distance, and the sign and strength of these interactions can be unique for each pair of spins. In such a generalized formulation, this problem is very difficult to solve - just like solving the traveling salesman problem visiting hundreds of thousands of potential buyers. If we can find a way to quickly solve the Ising optimization problems, and a way to talk about the traveling salesman problem and similar problems as well as about the Ising tasks, we may be able to solve them quickly, too. The minimum energy of the system in the Ising problem will be the fastest route between cities, the most effective solution for packing a cargo vessel, or any other optimization problem we need.

So how do you transform the traveling salesman's path in the back? The main task is the statement of conformity: we need to present our optimization problem in a form in which the machine designed to solve the Ising optimization problems can solve it. First you need to compare the original optimization problem - for example, finding a path for the seller of vacuum cleaners - with a set of spins, and determine how the spins affect each other. Thanks to research conducted in recent decades, both in the field of informatics and in operations research , the comparison of various optimization problems with the Ising forms is generally known .

However, it is hard to work with individual atoms and the spins of their electrons, so we concentrated on creating a machine that implements the Ising model using pulses of light instead of electron spins. The Ising task is compared with pulses and interactions between them. The result is estimated in terms of the total energy of the problem, and the state with the minimum energy is considered the optimal solution. Then this solution is translated into a language that makes sense for the original task - for example, in the shortest way the traveling salesman.

The key to our prototype's ability to match spins to pulses of light is OPO, a device resembling a laser. But OPO, in contrast to a conventional laser, produces light that is exactly in phase, or exactly in antiphase to some kind of basic light. That is what is needed to represent binary states of a spin, up and down. We can imagine an upward spin as a state in which the light of the OPO is in phase with the base one, and vice versa, the downward spin corresponds to the light in antiphase.

You can create an Ising machine using OPO in several ways. Groups of NTT, Caltech, Cornell, and Colombia, among others, are experiencing different approaches. The prototype Ising machine, first shown at Stanford in an experiment led by Alireza Marandi (who now works at Caltech) used technology that we continue to work with further: a multiplexed time-sharing and optical connection OPO.

Let's break this complicated term. We start with a pulsed laser source. The source sends simultaneous pulses of light with a duration of several picoseconds in two directions. The first impulse becomes basic; it splits, and goes along two different paths.

The second is used as an energy source for an OPO: it stimulates a crystal in an OPO, which emits photon pulses. Each impulse is transmitted to a coil of optical looped cable with a length of several hundred meters - depending on the number of pulses we need. There are hundreds or even thousands of OPO pulses in this ring, and they will chase in a circle one after another, passing through the crystal again and again.


Above: The author of the article and his former lab partner Alireza Marandi are looking at a prototype Ising optical computer.
Bottom: most of the events occur inside the optical cable coil

The phases of these pulses will play the role of the spins of the Ising model. But immediately after their creation, before they go through the loop several times, they are so weak that their phases are not well defined. The way we force them to interact will ultimately give them the final phases and will give a solution to our Ising task.

Remember the base light from the experiment description? At one point in the loop there is a splitter, which selects a small part of each pulse, which is compared with the base pulse in the homodyne detector. The output voltage of the detector contains information about the phase and amplitude of the detector. This signal is digitized and fed to the FPGA. This is the very problem of Ising.

Recall that solving the Ising problem means finding the minimum energy state for a set of spins, in which the spins interact with each other in different ways, and these interactions add extra energy to the total energy of the system. In OPO, each pulse denotes a spin. Therefore, for each pulse — and in our setup we used 100 — the CPRM performs calculations, which include the recorded measurements of all other pulses, which, according to the Ising problem, should affect the considered spin. The processor then applies the calculations to the intensity modulator and phase modulator settings that are on one of the base pulse paths. The modified base impulse is fed into the ring of the fiber optic cable, in which the POD pulses are snooping.

It is crucial to choose the right moment - we need the modified base impulse to be combined with the right impulse OPO. If done correctly, the two impulses will mix. Depending on whether they are in phase or not, the impulse entered into the system tends the impulse of the OPO to the spin representation, either upward or downward.

For each OPO pulse in the loop, we repeat this entire process, and to achieve the final phase states, the pulses can travel tens of thousands of times along the entire length of the loop. After that, a separate computer reads a set of phases, interprets them as electrons from the Ising problem with the spins directed up or down, and then turns it into a meaningful solution to the original optimization problem that you need to solve.

In our experiments, we first made a system with four spins, and then with 16 spins. The task parameters were hardware embedded in installations in the form of branching segments of an optical cable of a certain length. In these experiments, we successfully discovered the states of minimum energy, and this gave us the motivation to develop this approach. In 2016, we created a PPMM based feedback machine capable of solving Ising problems with 100 spins. Comparison of the speed of our installation with specialized systems, including the “ quantum annealing ” apparatus from NASA, gave us the confidence that the Ising OPO machines can be effective optimizers.

The results turned out to be promising, but we still have a lot to learn before we understand whether such an optical approach can outrun a conventional processor in solving practical optimization problems. It is possible that the ability of the machine to solve problems can be improved by using quantum states of light, which are very difficult to simulate. We only approach the solution of a set of similar questions, and we plan in the next few years to study the extremely interesting interaction of theory and experiment, developing this new type of computing machine.