A Quantum Algorithm for Dynamic Mode Decomposition Integrated with a Quantum Differential Equation Solver
arXiv:2310.17783 · doi:10.1103/PhysRevResearch.6.043031
Abstract
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 the dynamic mode decomposition algorithm used in diverse fields such as fluid 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, in particular those with complex eigenvalues. The complexity of our quantum algorithm is for an -dimensional system. This is an exponential speedup over known classical algorithms with at least complexity. Thus, our quantum algorithm is expected to enable high-dimensional dynamical systems analysis and large matrix eigenvalue decomposition, intractable for classical computers.
References in corpus (25)
- Quantum algorithm for solving linear systems of equations
- On Dynamic Mode Decomposition: Theory and Applications
- Simulated Quantum Computation of Molecular Energies
- Quantum principal component analysis
- Quantum state tomography via compressed sensing
- Quantum random access memory
- A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Polynomial-time quantum algorithm for the simulation of chemical dynamics
- Prediction by linear regression on a quantum computer
- Data-driven model reduction and transfer operator approximation
- High-order quantum algorithm for solving linear differential equations
- Efficient quantum algorithm for dissipative nonlinear differential equations
- Quantum algorithm for linear differential equations with exponentially improved dependence on precision
- Quantum singular value decomposition of non-sparse low-rank matrices
- Quantum spectral methods for differential equations
- Improved quantum algorithms for linear and nonlinear differential equations
- Quantum Analog-Digital Conversion
- Hamiltonian Simulation with Optimal Sample Complexity
- Creation of superposition of unknown quantum states
- Measurement-based quantum phase estimation algorithm for finding eigenvalues of non-unitary matrices
- A Universal Quantum Circuit Scheme For Finding Complex Eigenvalues
- Quantum advantage for differential equation analysis
- An efficient quantum algorithm for spectral estimation
- Pure state tomography with parallel unentangled measurements