Listen to an AI podcast on this article:
New Quantum Algorithms Finally Crack Nonlinear Equations
Max G. Levy
January 5, 2021
Two teams found different ways for quantum computers to process nonlinear systems by first disguising them as linear ones.
Read Later
Olena Shmahalo/Quanta Magazine
Sometimes, it’s easy for a computer to predict the future. Simple phenomena, such as how sap flows down a tree trunk, are straightforward and can be captured in a few lines of code using what mathematicians call linear differential equations. But in nonlinear systems, interactions can affect themselves: When air streams past a jet’s wings, the air flow alters molecular interactions, which alter the air flow, and so on. This feedback loop breeds chaos, where small changes in initial conditions lead to wildly different behavior later, making predictions nearly impossible — no matter how powerful the computer.
“This is part of why it’s difficult to predict the weather or understand complicated fluid flow,” said Andrew Childs, a quantum information researcher at the University of Maryland. “There are hard computational problems that you could solve, if you could [figure out] these nonlinear dynamics.”
That may soon be possible. In separate studies posted in November, two teams — one led by Childs, the other based at the Massachusetts Institute of Technology — described powerful tools that would allow quantum computers to better model nonlinear dynamics.
Quantum computers take advantage of quantum phenomena to perform certain calculations more efficiently than their classical counterparts. Thanks to these abilities, they can already topple complex linear differential equations exponentially faster than classical machines. Researchers have long hoped they could similarly tame nonlinear problems with clever quantum algorithms.
The new approaches disguise that nonlinearity as a more digestible set of linear approximations, though their exact methods vary considerably. As a result, researchers now have two separate ways of approaching nonlinear problems with quantum computers.
“What is interesting about these two papers is that they found a regime where, given some assumptions, they have an algorithm that is efficient,” said Mária Kieferová, a quantum computing researcher at the University of Technology Sydney who is not affiliated with either study. “This is really exciting, and [both studies] use really nice techniques.”
The Cost of Chaos
Quantum information researchers have tried to use linear equations as a key to unlock nonlinear differential ones for over a decade. One breakthrough came in 2010, when Dominic Berry, now at Macquarie University in Sydney, built the first algorithm for solving linear differential equations exponentially faster on quantum, rather than on classical, computers. Soon, Berry’s own focus shifted to nonlinear differential equations as well.
“We had done some work on that before,” Berry said. “But it was very, very inefficient.”
Photo of Andrew Childs standing in front of a white board full of math
Andrew Childs, of the University of Maryland, led one of two efforts to allow quantum computers to better model nonlinear dynamics. His team’s algorithm turned these chaotic systems into an array of more understandable linear equations using a technique called Carleman linearization. John T. Consoli / University of Maryland
The problem is, the physics underlying quantum computers is itself fundamentally linear. “It’s like teaching a car to fly,” said Bobak Kiani, a co-author of the MIT study.
So the trick is finding a way to mathematically convert a nonlinear system into a linear one. “We want to have some linear system because that’s what our toolbox has in it,” Childs said. The groups did this in two different ways.
Childs’ team used Carleman linearization, an out-of-fashion mathematical technique from the 1930s, to transform nonlinear problems into an array of linear equations.
Unfortunately, that list of equations is infinite. Researchers have to figure where they can cut off the list to get a good-enough approximation. “Do I stop at equation number 10? Number 20?” said Nuno Loureiro, a plasma physicist at MIT and a co-author of the Maryland study. The team proved that for a particular range of nonlinearity, their method could truncate that infinite list and solve the equations.
The MIT-led paper took a different approach. It modeled any nonlinear problem as a Bose-Einstein condensate. This is a state of matter where interactions within an ultracold group of particles cause each individual particle to behave identically. Since the particles are all interconnected, each particle’s behavior influences the rest, feeding back to that particle in a loop characteristic of nonlinearity.
The MIT algorithm mimics this nonlinear phenomenon on a quantum computer, using Bose-Einstein math to connect nonlinearity and linearity. So by imagining a pseudo Bose-Einstein condensate tailor made for each nonlinear problem, this algorithm deduces a useful linear approximation. “Give me your favorite nonlinear differential equation, then I’ll build you a Bose-Einstein condensate that will simulate it,” said Tobias Osborne, a quantum information scientist at Leibniz University Hannover who was not involved in either study. “This is an idea I really loved.”
A colorful computer model of a Bose-Einstein condensate against a black background
The MIT-led team’s algorithm modeled any nonlinear problem as a Bose-Einstein condensate, an exotic state of matter where interconnected particles all behave identically.
NIST
Berry thinks both papers are important in different ways (he wasn’t involved with either). “But ultimately the importance of them is showing that it’s possible to take advantage of [these methods] to get the nonlinear behavior,” he said.
Knowing One’s Limits
While these are significant steps, they are still among the first in cracking nonlinear systems. More researchers will likely analyze and refine each method — even before the hardware needed to implement them becomes a reality. “With both of these algorithms, we are really looking in the future,” Kieferová said. Using them to solve practical nonlinear problems requires quantum computers with thousands of qubits to minimize error and noise — far beyond what’s possible today.
And both algorithms can realistically handle only mildly nonlinear problems. The Maryland study quantifies exactly how much nonlinearity it can handle with a new parameter, R, which represents the ratio of a problem’s nonlinearity to its linearity — its tendency toward chaos versus the friction keeping the system on the rails.
“[Childs’ study is] mathematically rigorous. He gives very clear statements of when it will work and when it won’t work,” Osborne said. “I think that’s really, really interesting. That’s the core contribution.”
The MIT-led study doesn’t rigorously prove any theorems to bound its algorithm, according to Kiani. But the team plans to learn more about the algorithm’s limitations by running small-scale tests on a quantum computer before moving to more challenging problems.
The most significant caveat for both techniques is that quantum solutions fundamentally differ from classical ones. Quantum states correspond to probabilities rather than to absolute values, so instead of visualizing air flow around every segment of a jet’s fuselage, for example, you extract average velocities or detect pockets of stagnant air. “This fact that the output is quantum mechanical means that you still have to do a lot of stuff afterwards to analyze that state,” Kiani said.
It’s vital to not overpromise what quantum computers can do, Osborne said. But researchers are bound to test many successful quantum algorithms like these on practical problems in the next five to 10 years. “We’re going to try all kinds of things,” he said. “And if we think about the limitations, that might limit our creativity.”
