Designing a Nearly Optimal Quantum Algorithm for Linear Differential Equations via Lindbladians.

Abstract

Solving linear ordinary differential equations (ODEs) is one of the most promising applications for quantum computers to demonstrate exponential advantages. The challenge of designing a quantum ODE algorithm is how to embed nonunitary dynamics into intrinsically unitary quantum circuits. In this Letter, we propose a new quantum algorithm for solving ODEs by harnessing open quantum systems. Specifically, we propose a novel technique called nondiagonal density matrix encoding, which leverages the inherent nonunitary dynamics of Lindbladians to encode general linear ODEs into the nondiagonal blocks of density matrices. This framework enables us to design quantum algorithms with both theoretical simplicity and high performance. Combined with the state-of-the-art quantum Lindbladian simulation algorithms, our algorithm can outperform all existing quantum ODE algorithms and achieve near-optimal dependence on all parameters under a plausible input model. We also give applications of our algorithm including the Gibbs state preparations and the partition function estimations.