Two research teams found different ways to calculate nonlinear systems on quantum computers by disguising them as linear
Sometimes computers are easy to predict the future. A simple process, such as the sap of a plant flowing down a tree trunk, is fairly easy to implement in a few lines of code using what mathematicians call linear differential equations . However, in nonlinear systems, interactions affect themselves: the air flowing around the wings of an airplane affects the interaction of molecules, which affects the air flow, and so on. The feedback loop creates chaos in which a small change in the initial conditions leads to a radical change in behavior afterwards, which makes it almost impossible to predict the behavior of the system - no matter how powerful the computer you use.
"Particularly, this makes it difficult to predict the weather or study complex fluid flows," said Andrew Childs , a quantum information researcher at the University of Maryland. "It would be possible to solve very complex computational problems if it was possible to understand this nonlinear dynamics."
Perhaps it will work out soon. In November 2020, two teams independently published their research ( one led by Childs, the other from MIT) describing powerful tools that should improve the quality of simulation of nonlinear dynamic processes on quantum computers.
Quantum computers take advantage of quantum phenomena to perform some types of computation more efficiently than classical computers. Because of this, they have already learned to solve complex linear differential equations exponentially faster. And researchers have long hoped that they can tame nonlinear problems in a similar way using clever quantum algorithms.
New approaches hide the nonlinearity of equations behind the mask of a more digestible set of linear approximations. At the same time, the approaches differ significantly among themselves. As a result, researchers now have two different ways to approach nonlinear problems using quantum computers.
“Interestingly, these two papers found an approach that, given some assumptions, could come up with an efficient algorithm,” said Maria Kiferova , a quantum computing researcher at the University of Technology of Sydney who is not associated with the work. "It's very interesting and both teams use very cool techniques."
The cost of chaos
Researchers in quantum information have been trying to use linear equations to solve NDEs for over a decade. One of the breakthroughs came in 2010, when Dominic Berry, now at Macquarie University of Sydney, created the first algorithm for solving linear differential equations that works exponentially faster on quantum computers than on classical computers. Bury soon switched to nonlinear differential equations.
“We've worked with this before,” Berry said. "But it was a very, very ineffective approach."
Andrew Childs
The problem is that the physical underpinnings of quantum computers themselves are fundamentally linear. “It's like teaching a car to fly,” said Bobak Kiani, co-author of the study at MIT.
The trick is to figure out how to mathematically turn a nonlinear system into a linear one. “We need some sort of linear system because the tools at our disposal can work with it,” Childs said. Teams of scientists have approached this issue in two different ways.
Childs' team used Carleman's linearization , an old-fashioned mathematical technique invented in the 1930s, to turn nonlinear problems into an array of linear equations.
Unfortunately, this list of equations is endless. Researchers need to figure out where it can be cut to get a good enough approximation. “Stop at the 10th equation? 20th? " - said Nuno Loureiro, plasma physicist at MIT, co-author of the study at the University of Maryland. The team proved that for a certain range of nonlinearity, this method allows you to truncate an infinite list and solve equations.
The MIT team took a different approach. She modeled nonlinear problems as a Bose-Einstein condensate . This is a special state of matter in which interactions in a group of extremely cooled particles cause all particles to behave the same. Since all particles are connected, the behavior of each of them affects all the others, which contributes to the feedback loop characteristic of nonlinear processes.
An algorithm from MIT mimics this nonlinear phenomenon on a quantum computer using mathematics designed for Bose-Einstein condensates to relate nonlinearity to linearity. By presenting each nonlinear problem as a specially tailored condensate calculation, the algorithm outputs a useful linear approximation. “Give me your favorite nonlinear differential equation, and I’ll build a Bose-Einstein condensate to simulate it,” said Tobias Osborne , a quantum information scientist at the Institute. Leibniz in Hanover, who did not participate in the above-mentioned works. "I really liked this idea."
The MIT team's algorithm modeled each nonlinear problem as a Bose-Einstein condensate
Berry believes that both works are important, and each in its own way (he did not participate in either). “But most importantly, they showed that these methods can be used to get non-linear behavior,” he said.
Know your limits
Although these steps are important, they are still only the first stages of attempts to break nonlinear systems. Researchers will most likely analyze and improve each of the methods, even before there are real quantum computers that can implement these algorithms. “Both algorithms are aimed at the future,” said Kiferova. To use them to solve practical nonlinear problems would require quantum computers with thousands of qubits that minimize errors and noise. Such computers are far beyond our current capabilities.
And, frankly, both algorithms are capable of working only with not very complex nonlinear problems. The Maryland study quantifies the maximum nonlinearity using the parameter R. This is the ratio of the problem's nonlinearity to its linearity, that is, the degree to which it tends to be random.
“Mathematically, Childs' research is quite rigorous. He makes it clear when his approach will work and when it won't, ”Osborne said. - I think it's very, very interesting. This is one of the important contributions to the topic. "
The study from MIT does not provide rigorous theorem proofs, Kiani says. However, the team plans to identify the limitations of the algorithm by performing simple tests on quantum computers before moving on to more complex problems.
The biggest drawback of both techniques is that quantum solutions are fundamentally different from classical solutions . Quantum states correspond to probabilities, not absolute values, so, for example, instead of visualizing the air flow next to each segment of an airplane fuselage, you get average speeds, or find areas of still air. “Because of the quantum yield of the algorithms, there are still a lot of things to do before the state of the system can be analyzed,” Kiani said.
Osborne says it's important not to exaggerate the capabilities of quantum computers. However, in the next 5-10 years, researchers are bound to test many of these successful quantum algorithms. “We’ll try everything,” he said. “And thinking about limitations all the time can limit our creativity.”