Quantum Dynamic Mode Decomposition Algorithm for High-Dimensional Time Series Analysis

Abstract

The dynamic mode decomposition (DMD) algorithm is a widely used factorization and dimensionality reduction technique in time series analysis. When analyzing high-dimensional time series, the DMD algorithm requires extremely large amounts of computational power. To accelerate the DMD algorithm, we propose a quantum-classical hybrid algorithm that we call the quantum dynamic mode decomposition (QDMD) algorithm. Given a time series X ∈ Rn × (m + 1) with n ≫ m, the QDMD algorithm first executes quantum singular value decomposition on a matrix related to X and obtains a quantum state containing the main singular values and singular vectors of the decomposed matrix, then performs a low-sampling-frequency process on the obtained quantum state and computes the low-dimensional projection of the DMD operator through the sampling results. Finally, the algorithm computes the DMD eigenvalues and prepares the amplitude-encoding states of the DMD modes using the obtained classical information and X. Considering the main variables, the complexity of the QDMD algorithm is [Formula: see text], where [Formula: see text] denotes the number of samples. Compared with the classical DMD algorithm, which has complexity [Formula: see text], the QDMD algorithm provides an exponential acceleration of n, at the cost of greater dependence on M and ϵ. We test the effects of M on the QDMD algorithm in the specific application scenarios of data denoising, scene background extraction, and fluid dynamics analysis. We determined that the QDMD algorithm requires only a small number of samples M in specific applications, further demonstrating the quantum advantage of the QDMD algorithm in high-dimensional data analysis.