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  ∈  R ^{n  × ( 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 $\tilde{O}\left(M\sqrt{m}\text{polylog}\left(n\right)/ϵ\right)$ , where $M=\tilde{O}\left(m^3/{ϵ}^2\right)$ denotes the number of samples. Compared with the classical DMD algorithm, which has complexity $\tilde{O}\left(n{m}^2\text{log}\left(1/ϵ\right)\right)$ , 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.