Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Intelligent Computing

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

Cheng Xue, Zhaoyun Chen, Tai‐Ping Sun, Xiao‐Fan Xu, Siming Chen, Huanyu Liu, Xi‐Ning Zhuang, Yu-Chun Wu, Guo‐Ping Guo

Published Jan 1, 2023• 5 citations
Publisher

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 O ~ M m polylog n / ϵ , where M = O ~ m 3 / ϵ 2 denotes the number of samples. Compared with the classical DMD algorithm, which has complexity O ~ n m 2 log 1 / ϵ , 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.

DOI
10.34133/icomputing.0045

Related papers

Quantum algorithm for dynamic mode decomposition integrated with a quantum differential equation solver

Yuta Mizuno, Tamiki Komatsuzaki

We present a quantum algorithm that analyzes time series data simulated by a quantum differential equation solver. The proposed algorithm is a quantum version of a dynamic mode decomposition algorithm used in diverse fields such as fluid dynamics, molecular dynamics, and epidemiology. Our quantum algorithm can also compute matrix eigenvalues and eigenvectors by analyzing the corresponding linear dynamical system. Our algorithm handles a broad range of matrices, particularly those with complex eigenvalues. The complexity of our quantum algorithm is O ( poly log N ) for an N -dimensional system. This is an exponential speedup over known classical algorithms with at least O ( N ) complexity. Thus, our quantum algorithm is expected to enable high-dimensional dynamical systems analysis and large matrix eigenvalue decomposition, intractable for classical computers. Published by the American Physical Society 2024

arXiv:2310.17783•Physical Review Research•Oct 11, 2024•5 citations

Predicting rate kernels via dynamic mode decomposition

Wei Liu, Zi‐Hao Chen, Yu Su +2 more

Simulating dynamics of open quantum systems is sometimes a significant challenge, despite the availability of various exact or approximate methods. Particularly when dealing with complex systems, the huge computational cost will largely limit the applicability of these methods. In this work, we investigate the usage of dynamic mode decomposition (DMD) to evaluate the rate kernels in quantum rate processes. DMD is a data-driven model reduction technique that characterizes the rate kernels using snapshots collected from a small time window, allowing us to predict the long-term behaviors with only a limited number of samples. Our investigations show that whether the external field is involved or not, the DMD can give accurate prediction of the result compared with the traditional propagations, and simultaneously reduce the required computational cost.

arXiv:2308.01635•The Journal of Chemical Physics•Oct 12, 2023•11 citations

Dynamical Mode Decomposition for Infinite-Dimensional Open Quantum Systems; Liouvillian Spectral Analysis and Parameter Estimation

Yuzuru Kato, Hiroya Nakao

Dynamic mode decomposition (DMD) is a data-driven method for the estimation, prediction, and control of complex dynamical systems, which has gained much attention in the fields of nonlinear dynamics and fluid mechanics. A DMD method for quantum spin systems, described by a linear dynamical system of a finite-dimensional set of observables, has been proposed recently. In this study, we propose two DMD methods applicable to infinite-dimensional open quantum systems, which use time-series data obtained by quantum state tomography. First, we propose a kernel DMD method for a data-driven spectral analysis of the Liouville superoperator. Second, we propose a method for the parameter estimation of the Liouville superoperator, which incorporates prior knowledge of the model structure into DMD. The proposed methods can accurately reconstruct the system dynamics and show that DMD frameworks can be applicable to infinite-dimensional open quantum systems.

IEEE Conference on Decision and Control (CDC)•Dec 13, 2023•0 citations

Hybrid quantum singular spectrum decomposition for time series analysis

J. J. Postema, Pietro Bonizzi, G. Koekoek +2 more

Classical data analysis requires computational efforts that become intractable in the age of Big Data. An essential task in time series analysis is the extraction of physically meaningful information from a noisy time series. One algorithm devised for this very purpose is singular spectrum decomposition (SSD), an adaptive method that allows for the extraction of narrow-banded components from non-stationary and non-linear time series. The main computational bottleneck of this algorithm is the singular value decomposition (SVD). Quantum computing could facilitate a speedup in this domain through superior scaling laws. We propose quantum SSD by assigning the SVD subroutine to a quantum computer. The viability for implementation and performance of this hybrid algorithm on a near term hybrid quantum computer is investigated. In this work, we show that by employing randomized SVD, we can impose a qubit limit on one of the circuits to improve scalibility. Using this, we efficiently perform quantum SSD on simulations of local field potentials recorded in brain tissue, as well as GW150914, the first detected gravitational wave event.

arXiv:2212.08831•AVS Quantum Science•May 30, 2023•2 citations

Dynamic Matrix Decomposition (DMD)

Jincheng Zhang

Abstract: This paper presents a novel dynamic matrix decomposition (DMD) algorithm leveraging quantum computing principles to efficiently decompose large matrices. We introduce a mechanism that utilizes quantum entanglement and superposition to enhance matrix computation, offering a significant acceleration and efficiency improvement compared to classical methods. The core of the algorithm lies in the manipulation of quantum states to achieve optimized matrix operations. The proposed method offers a promising pathway towards faster and more scalable matrix calculations, particularly applicable to large-scale matrix problems.

•Sep 7, 2026•0 citations

Quantum tensor singular value decomposition*

Xiaoqiang Wang, Lejia Gu, Heung-wing Lee +1 more

Abstract Tensors are increasingly ubiquitous in various areas of applied mathematics and computing, and tensor decompositions are of practical significance and benefit many applications in data completion, image processing, computer vision, collaborative filtering, etc. Recently, Kilmer and Martin propose a new tensor factorization strategy, tensor singular value decomposition (t-svd), which extends the matrix singular value decomposition to tensors. However, computing t-svd for high dimensional tensors costs much computation and thus cannot efficiently handle large scale datasets. Motivated by advantage of quantum computation, in this paper, we present a quantum algorithm of t-svd for third-order tensors and then extend it to order-p tensors. We prove that our quantum t-svd algorithm for a third-order N dimensional tensor runs in time  N polylog ( N ) if we do not recover classical information from the quantum output state. Moreover, we apply our quantum t-svd algorithm to context-aware multidimensional recommendation systems, where we just need to extract partial classical information from the quantum output state, thus achieving low time complexity.

Journal of Physics Communications•Jun 22, 2021•4 citations
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 O ~ M m polylog n / ϵ , where M = O ~ m 3 / ϵ 2 denotes the number of samples. Compared with the classical DMD algorithm, which has complexity O ~ n m 2 log 1 / ϵ , 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.
We present a quantum algorithm that analyzes time series data simulated by a quantum differential equation solver. The proposed algorithm is a quantum version of a dynamic mode decomposition algorithm used in diverse fields such as fluid dynamics, molecular dynamics, and epidemiology. Our quantum algorithm can also compute matrix eigenvalues and eigenvectors by analyzing the corresponding linear dynamical system. Our algorithm handles a broad range of matrices, particularly those with complex eigenvalues. The complexity of our quantum algorithm is O ( poly log N ) for an N -dimensional system. This is an exponential speedup over known classical algorithms with at least O ( N ) complexity. Thus, our quantum algorithm is expected to enable high-dimensional dynamical systems analysis and large matrix eigenvalue decomposition, intractable for classical computers. Published by the American Physical Society 2024
Simulating dynamics of open quantum systems is sometimes a significant challenge, despite the availability of various exact or approximate methods. Particularly when dealing with complex systems, the huge computational cost will largely limit the applicability of these methods. In this work, we investigate the usage of dynamic mode decomposition (DMD) to evaluate the rate kernels in quantum rate processes. DMD is a data-driven model reduction technique that characterizes the rate kernels using snapshots collected from a small time window, allowing us to predict the long-term behaviors with only a limited number of samples. Our investigations show that whether the external field is involved or not, the DMD can give accurate prediction of the result compared with the traditional propagations, and simultaneously reduce the required computational cost.
Dynamic mode decomposition (DMD) is a data-driven method for the estimation, prediction, and control of complex dynamical systems, which has gained much attention in the fields of nonlinear dynamics and fluid mechanics. A DMD method for quantum spin systems, described by a linear dynamical system of a finite-dimensional set of observables, has been proposed recently. In this study, we propose two DMD methods applicable to infinite-dimensional open quantum systems, which use time-series data obtained by quantum state tomography. First, we propose a kernel DMD method for a data-driven spectral analysis of the Liouville superoperator. Second, we propose a method for the parameter estimation of the Liouville superoperator, which incorporates prior knowledge of the model structure into DMD. The proposed methods can accurately reconstruct the system dynamics and show that DMD frameworks can be applicable to infinite-dimensional open quantum systems.
Classical data analysis requires computational efforts that become intractable in the age of Big Data. An essential task in time series analysis is the extraction of physically meaningful information from a noisy time series. One algorithm devised for this very purpose is singular spectrum decomposition (SSD), an adaptive method that allows for the extraction of narrow-banded components from non-stationary and non-linear time series. The main computational bottleneck of this algorithm is the singular value decomposition (SVD). Quantum computing could facilitate a speedup in this domain through superior scaling laws. We propose quantum SSD by assigning the SVD subroutine to a quantum computer. The viability for implementation and performance of this hybrid algorithm on a near term hybrid quantum computer is investigated. In this work, we show that by employing randomized SVD, we can impose a qubit limit on one of the circuits to improve scalibility. Using this, we efficiently perform quantum SSD on simulations of local field potentials recorded in brain tissue, as well as GW150914, the first detected gravitational wave event.
Abstract: This paper presents a novel dynamic matrix decomposition (DMD) algorithm leveraging quantum computing principles to efficiently decompose large matrices. We introduce a mechanism that utilizes quantum entanglement and superposition to enhance matrix computation, offering a significant acceleration and efficiency improvement compared to classical methods. The core of the algorithm lies in the manipulation of quantum states to achieve optimized matrix operations. The proposed method offers a promising pathway towards faster and more scalable matrix calculations, particularly applicable to large-scale matrix problems.
Abstract Tensors are increasingly ubiquitous in various areas of applied mathematics and computing, and tensor decompositions are of practical significance and benefit many applications in data completion, image processing, computer vision, collaborative filtering, etc. Recently, Kilmer and Martin propose a new tensor factorization strategy, tensor singular value decomposition (t-svd), which extends the matrix singular value decomposition to tensors. However, computing t-svd for high dimensional tensors costs much computation and thus cannot efficiently handle large scale datasets. Motivated by advantage of quantum computation, in this paper, we present a quantum algorithm of t-svd for third-order tensors and then extend it to order-p tensors. We prove that our quantum t-svd algorithm for a third-order N dimensional tensor runs in time  N polylog ( N ) if we do not recover classical information from the quantum output state. Moreover, we apply our quantum t-svd algorithm to context-aware multidimensional recommendation systems, where we just need to extract partial classical information from the quantum output state, thus achieving low time complexity.