Can quantum computers model nature’s most turbulent systems?

Quantum computers have the potential to accelerate applications spanning from machine learning to drug development. Among the most exciting recent algorithmic advances are those that offer new promise for tackling one of computing’s most grueling challenges: solving differential equations.

Differential equations describe the dynamics of quantities that change over time, and they find their way into nearly every field. Tracking the stock market, monitoring the flow of fluids, controlling plasmas in a fusion reactor, and simply predicting the weather all rely on differential equations. Solving one differential equation can be hard enough, but realistic problems require an unthinkable number of interconnected equations to describe. Classical algorithms hoping to simulate these scenarios ultimately rely on costly methods or approximations resulting in a loss of accuracy. However, for certain data structures or specific problems, quantum algorithms offer a significant, potentially exponential speedup.

At this year’s Quantum Information Processing (QIP) conference, researchers at IBM presented a host of papers exploring the foundations of quantum information science, quantum error correction, and quantum algorithms. Among these papers is an algorithm first published last year, designed to estimate functions that describe solutions of stochastic differential equations. This is the first such quantum algorithm capable of efficiently simulating strongly non-linear systems, or those acting chaotically.

But first, we don’t have many resources about quantum algorithms for differential equations on our blog. So, we felt it a good enough time as any to answer: what are differential equations and why does quantum provide promise solving them?

Change is hard

You know you’ve entered the world of calculus when you hear the word “differential.” However, finding differentials is simply a process that, given some changing situation, tells you how the situation changes. You encounter differentiation every day: if you plot a chart of your position changing over time as you drive to work—let’s call that chart a “function” of your position over time—then differentiating results in a new function that charts your velocity over time. A differential equation is an equation where the variables are unknown functions and their derivatives related via algebraic expressions, and where the aim is to find those unknown functions. A simple differential equation might ask you to find the function describing the position of a moving car over time, given information about the car’s starting position and its velocity.

In practice, problems requiring differential equations are far more challenging. Instead of a car on a road, try to find a function describing how the position of a toy boat sailing over river rapids changes over time, where each location, each water molecule, has its own function describing its movement.

Today, the only way we know how to exactly simulate such a situation is to overlay a mesh or grid of points onto it and solve differential equations at each point. A smooth flowing river may only require solving equations at a few widely-spaced points. However, the turbulent river—one where the water may be flowing completely differently just a few inches away—requires many more points. Not only are you solving a multi-dimensional differential equation at each point, but the more turbulent the flow, the more equations required at each point and the more complex those equations are.

Unfortunately, it’s the turbulent river that best describes most of the scenarios we seek to simulate in the real world. We call these systems nonlinear, and the ability to efficiently solve scenarios that are highly nonlinear could provide value far beyond describing fluids. Any situation with variables that change over time—modeling the spread of disease, the relationship between predators and prey in an ecosystem, the stock market, and the weather, would all extract lots of benefit from more efficient differential equation solvers. Of course, solving nonlinear systems of differential equations is really hard.

A first breakthrough: HHL

Quantum computing has offered promise solving problems beyond the ability of classical alone since the first quantum algorithms emerged decades ago. However, researchers far beyond quantum noticed when researchers Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd devised their “HHL” algorithm in 2008. The three researchers were researching linear equations—those that can be simplified to some $N*N$ spreadsheet of numbers, let’s call it $A$, a column of known numbers with $N$ entries called $\vec{b}$, and a column of unknown numbers with $N$ entries called $x$ such that $A*\vec{x} = b$. These equations are hard to solve classically, with their compute time scaling quickly with the size of the input data. But often researchers don’t need exact answers—rather, they want to extract specific properties that allow them to summarize the system. For appropriately-structured linear equations, HHL provides a method to find certain properties exponentially faster.

HHL is about as intuitive as a quantum algorithm can get. Quantum computers are machines that perform certain linear algebra operations innately. $N$ qubits can store a column of $2^N$ entries, while a quantum operation is equivalent to multiplying that column by a $2^N*2^N$ spreadsheet—though quantum has restrictions on what kind of data can be stored in those columns and spreadsheets, as well as restrictions on how much information you can extract at the end of the computation.

Without getting into too many details, HHL takes advantage of this linear algebra innate to quantum computers by representing our column of known numbers $\vec{b}$ as a quantum state, then using $A$ to create a series of quantum operations that act on $\vec{b}$, specifically employing a tool called quantum phase estimation in order to create the mathematical pieces we need to extract information about $\vec{x}$. Other researchers have since improved and built on the original HHL algorithm to create algorithms that are faster and applicable to more general types of linear systems, like those encountered when solving systems of differential equations.

HHL in its original form has limitations that prevent it from being used on today’s quantum hardware. However, it inspired an entire field of algorithmic research, serving as the underpinning to many novel quantum algorithms, including differential equation solvers. Researchers are also searching for what kinds of practical problems have a structure appropriate for exponential speedups with HHL and other related algorithms—while striving to build a quantum computer large enough to run them.

A new kind of solver

Earlier this year, researchers at IBM uncovered a new algorithm that approached the problem differently—and in doing so, found a promising potentially exponential speedup that might be employed for practical problems.

Returning to our turbulent fluid, previous work showed that instead of assigning a differential equation to each point on a grid, you can perform a mathematical transformation on the data describing your turbulent fluid to create a new, infinite list of differential equations for turbulence-free fluids, then using mathematical methods to truncate this system into finite dimensional systems and extract an approximate answer. However, these algorithms only work if the systems incorporate dissipation—that is, if the fluid loses the ability to do work over time, say, through heat loss or friction. Also, they only work for systems that are sort of nonlinear—i.e., turbulent, but not that turbulent. Meanwhile, existing extensions to HHL can be used to study very turbulent systems, but scale exponentially.

New work from the IBM team—Sergey Bravyi, Robert Manson-Sawko, Mykhaylo Zayats, and Sergiy Zhuk—now explores whether an efficient quantum algorithm exists for simulating stochastic quadratic differential equations, a fundamental model that appears in turbulent fluid dynamics. The key question they sought to answer was whether such an algorithm could scale efficiently (e.g., polynomially) with system size and time. The team discovered that when the system is both dissipative and noisy—meaning there is also some random drive or pulse, like giving a hose a random shake—they can efficiently simulate highly nonlinear dynamics, in stark contrast to previous results.

Why does noise help? Roughly speaking, noise induces “mixing,” which smooths out small-scale details of the system’s dynamics. This makes the system easier to model on a quantum computer, even when the underlying behavior is highly complex.

In addition to the algorithmic breakthrough, the team proved that their algorithm is BQP-complete, a key benchmark for quantum advantage. In complexity theory terms, this essentially means that if someone could design an efficient classical algorithm to solve this problem, then they’d also be able to simulate a quantum computer classically. Therefore, if quantum computers do have an innate computational advantage over classical computers, then a BQP-complete algorithm would be something a classical computer couldn’t handle efficiently.

The team continues to study the problem. For example, are there instances where their method will work for lower noise rates? But further, they’re excited to begin studying real-world problems, such as the Navier-Stokes equation in three spatial dimensions, a cornerstone of computational fluid dynamics and magneto-hydrodynamics (a.k.a., nuclear fusion) to name just a few. A solid theoretical justification of the existence and uniqueness of “physically relevant” solutions of this equation in three dimensions is one of the Millennium Prize Problems in mathematics, which poses major challenges in design of quantum algorithms with provable quantum advantage.

Differential equations remains a core area of study for IBM Research, and one where new algorithms have immense potential to provide advantages for real-world use cases. This work continues to demonstrate the critical importance for teams to study quantum algorithms, and to seek cases where their problems could efficiently map to today’s existing algorithms.