QuICS Team Discovers New Quantum Algorithm for Nonlinear Differential Equations

September 15, 2021

Powerful new quantum algorithms can be hard to come by—doubly so if an algorithm is meant to tackle problems of great practical interest.

Take differential equations, which form the core mathematical language of nature. Differential equations describe everything from a swinging pendulum and an arcing football to the booms and busts of ecological populations and the dynamics of global climate.

It’s only natural that quantum information researchers—who seek to exploit the quirks of quantum physics to conjure entirely new methods for solving computational problems—would search for quantum algorithms that can make quick work of differential equations.

“It was a longstanding open problem to understand whether quantum computers could be used to efficiently tackle nonlinear differential equations,” says Jin-Peng Liu (in photo), a graduate student at the Joint Center for Quantum Information and Computer Science (QuICS) and in the Applied Mathematics & Statistics, and Scientific Computation Program at the University of Maryland. “This challenge brought together a team from diverse backgrounds, including quantum information science, applied mathematics, and fluid and plasma dynamics.”

Liu led a team of researchers in discovering a new quantum algorithm for a certain family of nonlinear differential equations. The result was described in a paper published recently in the Proceedings of the National Academy of Sciences. The work was also covered as a preprint by Quanta Magazine.

The new algorithm comes on the heels of years of research into quantum algorithms for linear differential equations. It also builds directly atop those ideas, as the core technique used in the new algorithm is a procedure for “linearization”—a way of converting nonlinear differential equations, which are generally more complex and harder to solve, into linear differential equations, for which there already exist speedy quantum algorithms.

The team proved that their method is exponentially faster than the best-known non-quantum algorithm, at least for differential equations that aren’t too nonlinear. They also proved that this limitation to weakly nonlinear equations is necessary by showing that no quantum algorithm could ever gain an exponential speedup for a family of strongly nonlinear differential equations.

Liu contributed several detailed proofs to the paper. In particular, he confirmed that the linearization method, initially suggested by a coauthor, could indeed enable a fast quantum algorithm.

“Jin-Peng’s research is at the forefront of the emerging area of quantum scientific computation,” says Andrew Childs, a professor of computer science at the University of Maryland and a co-director of QuICS. “His results suggest that quantum computers might provide powerful tools for tackling scientific challenges, even in areas not directly connected to quantum mechanics.”

—Story by Chris Cesare