A Quantum Algorithm for Solving Linear Differential Equations: Theory and Experiment

Abstract

We present and experimentally realize a quantum algorithm for efficiently solving the following problem: given an $N\times N$ matrix $\mathcal{M}$, an $N$-dimensional vector $\text{b}$, and an initial vector $\text{x}(0)$, obtain a target vector $\text{x}(t)$ as a function of time $t$ according to the constraint $d\text{x}(t)/dt=\mathcal{M}\text{x}(t)+\text{b}$. We show that our algorithm exhibits an exponential speedup over its classical counterpart in certain circumstances. In addition, we demonstrate our quantum algorithm for a $4\times 4$ linear differential equation using a 4-qubit nuclear magnetic resonance quantum information processor. Our algorithm provides a key technique for solving many important problems which rely on the solutions to linear differential equations.