Quantum Ordinary Differential Equation Algorithms: Block-Matrix Algorithms

Osama M. Raisuddin, Suvranu De

Alok Shukla, Prakash Vedula

Dekuan Dong, Yingzhou Li, Jungong Xue

We propose a novel quantum algorithm for solving linear autonomous ordinary differential equations (ODEs) using the Padé approximation. For linear autonomous ODEs, the discretized solution can be represented by a product of matrix exponentials. The proposed algorithm approximates the matrix exponential by the diagonal Padé approximation, which is then encoded into a large, block-sparse linear system and solved via quantum linear system algorithms (QLSA). The detailed quantum circuit is given based on quantum oracle access to the matrix, the inhomogeneous term, and the initial state. The complexity of the proposed algorithm is analyzed. Compared to the method based on Taylor approximation, which approximates the matrix exponential using a k -th order Taylor series, the proposed algorithm improves the approximation order k from two perspectives: 1) the explicit complexity dependency on k is improved, and 2) a smaller k suffices for the same precision. Numerical experiments demonstrate the advantages of the proposed algorithm comparing to other related algorithms.

Zhong-Xia Shang, Naixu Guo, Dong An +1 more

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.

Dominic William Berry

Osama M. Raisuddin, Suvranu De