Quantum algorithm for solving linear differential equations: Theory and experiment

Abstract

Solving linear differential equations (LDEs) is a hard problem for classical computers, while quantum algorithms have been proposed to be capable of speeding up the calculation. However, they are yet to be realized in experiment as it cannot be easily converted into an implementable quantum circuit. Here, we present and experimentally realize an implementable gate-based quantum algorithm for efficiently solving the LDE problem: given an $N\ifmmode\times\else\texttimes\fi{}N$ matrix $\mathcal{M}$, an $N$-dimensional vector $\mathbf{b}$, and an initial vector $\mathbf{x}(0)$, we obtain a target vector $\mathbf{x}(t)$ as a function of time $t$ according to the constraint $d\mathbf{x}(t)/dt=\mathcal{M}\mathbf{x}(t)+\mathbf{b}$. We show that our algorithm exhibits an exponential speedup over its classical counterpart in certain circumstances, and a gate-based quantum circuit is produced which is friendly to the experimentalists and implementable in current quantum techniques. In addition, we experimentally solve a $4\ifmmode\times\else\texttimes\fi{}4$ linear differential equation using our quantum algorithm in a four-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.