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

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 <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"><a:mrow><a:mi>O</a:mi><a:mo>(</a:mo><a:mo form="prefix">poly</a:mo><a:mo form="prefix">log</a:mo><a:mi>N</a:mi><a:mo>)</a:mo></a:mrow></a:math> for an <d:math xmlns:d="http://www.w3.org/1998/Math/MathML"><d:mi>N</d:mi></d:math>-dimensional system. This is an exponential speedup over known classical algorithms with at least <e:math xmlns:e="http://www.w3.org/1998/Math/MathML"><e:mrow><e:mi>O</e:mi><e:mo>(</e:mo><e:mi>N</e:mi><e:mo>)</e:mo></e:mrow></e:math> 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