Related papers: A Quantum Algorithm for Dynamic Mode Decomposition Integrated with a Quantum Differential Equation Solver

A Quantum Algorithm for Dynamic Mode Decomposition Integrated with a Quantum Differential Equation Solver

URL: http://arxiv.org/abs/2310.17783v3
Date: Sun, 21 Apr 2024 20:41:26 GMT
Title: A Quantum Algorithm for Dynamic Mode Decomposition Integrated with a Quantum Differential Equation Solver
Abstract summary: We present a quantum algorithm that analyzes time series data simulated by a quantum differential equation solver. Our quantum algorithm can also compute matrix eigenvalues and eigenvectors by analyzing the corresponding linear dynamical system.
Score: 0.34530027457862006
License: http://creativecommons.org/licenses/by/4.0/
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 $O(\operatorname{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.

Related papers

Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems [0.007807026251125201]
We present an efficient, nearly optimal quantum algorithm for solving linear matrix differential equations.<n>For unitary or dissipative dynamics, the algorithm computes an entry of the solution matrix with query $widetildemathcalO(mathcalL t/)$.<n>We demonstrate the utility of the algorithm through an end-to-end application, namely the simulation of dissipative dynamics for non-interacting fermions.
arXiv Detail & Related papers (2026-05-15T17:11:07Z)
Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
arXiv Detail & Related papers (2026-02-11T07:24:33Z)
Design nearly optimal quantum algorithm for linear differential equations via Lindbladians [11.53984890996377]
We propose a new quantum algorithm for ODEs by harnessing open quantum systems. We use the natural non-unitary dynamics of Lindbladians with the aid of a new technique called the non-diagonal density matrix encoding. Our algorithm can outperform all existing quantum ODE algorithms and achieve near-optimal dependence on all parameters.
arXiv Detail & Related papers (2024-10-25T15:27:41Z)
Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
We propose a quantum algorithm inspired by the classical multi-row iteration method. Our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems.
arXiv Detail & Related papers (2024-09-06T03:32:02Z)
Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z)
Fast quantum algorithm for differential equations [0.5895819801677125]
We present a quantum algorithm with numerical complexity that is polylogarithmic in $N$ but is independent of $kappa$ for a large class of PDEs. Our algorithm generates a quantum state that enables extracting features of the solution.
arXiv Detail & Related papers (2023-06-20T18:01:07Z)
Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations. We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix. A quantum algorithm to simulate the dynamics of the density matrix is proposed.
arXiv Detail & Related papers (2023-06-14T23:08:51Z)
A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
arXiv Detail & Related papers (2023-04-12T18:10:47Z)
Quantum Algorithm For Estimating Eigenvalue [0.0]
We provide a quantum algorithm for estimating the largest eigenvalue in magnitude of a given Hermitian matrix. Our quantum procedure can also yield exponential speedup compared to classical algorithms that solve the same problem.
arXiv Detail & Related papers (2022-11-11T13:02:07Z)
Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
We propose quantum algorithms for matrix operations using the "Sender-Receiver" model. These quantum protocols can be used as subroutines in other quantum schemes.
arXiv Detail & Related papers (2022-02-10T08:12:20Z)
A Quantum Computer Amenable Sparse Matrix Equation Solver [0.0]
We study problems involving the solution of matrix equations, for which there currently exists no efficient, general quantum procedure. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware.
arXiv Detail & Related papers (2021-12-05T15:42:32Z)
Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
arXiv Detail & Related papers (2021-04-01T19:06:00Z)
Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z)
High-precision quantum algorithms for partial differential equations [1.4050836886292872]
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm. We develop quantum algorithms based on adaptive-order finite difference methods and spectral methods. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound.
arXiv Detail & Related papers (2020-02-18T20:32:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.