Quantum Eigensolver for General Matrices
- URL: http://arxiv.org/abs/2401.12091v1
- Date: Mon, 22 Jan 2024 16:29:08 GMT
- Title: Quantum Eigensolver for General Matrices
- Authors: Xiao-Ming Zhang, Yunkun Zhang, Wenhao He and Xiao Yuan
- Abstract summary: We present a novel family of quantum algorithms tailored for solving the eigenvalue problem for general matrices.
Our algorithms find applications in diverse domains, including estimating the relaxation time of Markov chains.
These applications underscore the significance of our quantum eigensolvers for problems across various disciplines.
- Score: 5.811990276393904
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The eigenvalue problem, a cornerstone in linear algebra, provides profound
insights into studying matrix properties. Quantum algorithms addressing this
problem have hitherto been constrained to special normal matrices assuming
spectral decomposition, leaving the extension to general matrices an open
challenge. In this work, we present a novel family of quantum algorithms
tailored for solving the eigenvalue problem for general matrices, encompassing
scenarios with complex eigenvalues or even defective matrices. Our approach
begins by tackling the task of searching for an eigenvalue without additional
constraints. For diagonalizable matrices, our algorithm has $\tilde
O(\varepsilon^{-1})$ complexity with an error $\varepsilon$, achieving the
nearly Heisenberg scaling. Subsequently, we study the identification of
eigenvalues closest to a specified point or line, extending the results for
ground energy and energy gap problems in Hermitian matrices. We achieve an
accuracy scaling of $\tilde O(\varepsilon^{-2})$ for general diagonalizable
matrices, further refining to $\tilde O(\varepsilon^{-1})$ under the condition
of real eigenvalues or constant distance from the reference point. The
algorithm's foundation lies in the synergy of three techniques: the
relationship between eigenvalues of matrix $A$ and the minimum singular value
of $A-\mu I$, quantum singular value threshold subroutine extended from quantum
singular-value estimation, and problem-specific searching algorithms. Our
algorithms find applications in diverse domains, including estimating the
relaxation time of Markov chains, solving Liouvillian gaps in open quantum
systems, and verifying PT-symmetry broken/unbroken phases. These applications
underscore the significance of our quantum eigensolvers for problems across
various disciplines.
Related papers
- Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition.
A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues.
We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
arXiv Detail & Related papers (2024-05-23T12:26:25Z) - Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
We propose an algorithm for calculating the determinant of a square matrix, and construct a quantum circuit realizing it.
Each row of the matrix is encoded as a pure state of some quantum system.
The admitted matrix is therefore arbitrary up to the normalization of quantum states of those systems.
arXiv Detail & Related papers (2024-01-29T23:23:27Z) - Quantum eigenvalue processing [0.0]
Problems in linear algebra can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices.
We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary transformations on eigenvalues of block-encoded non-normal operators.
We also present a Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra.
arXiv Detail & Related papers (2024-01-11T19:49:31Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson
Brownian Motion [28.431572772564518]
Given a symmetric matrix $M$ and a vector $lambda$, we present new bounds on the Frobenius-distance utility of the Gaussian mechanism for approximating $M$ by a matrix.
Our bounds depend on both $lambda$ and the gaps in the eigenvalues of $M$, and hold whenever the top $k+1$ eigenvalues of $M$ have sufficiently large gaps.
arXiv Detail & Related papers (2022-11-11T18:54:01Z) - 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) - Quantum algorithms for the generalized eigenvalue problem [6.111964049119244]
generalized eigenvalue (GE) problems are of particular importance in various areas of science engineering and machine learning.
We present a variational quantum algorithm for finding the desired generalized eigenvalue of the GE problem, $mathcalA|psirangle=lambdamathcalB|psirangle$, by choosing suitable loss functions.
We numerically implement our algorithms to conduct a 2-qubit simulation and successfully find the generalized eigenvalues of the matrix pencil $(mathcalA,,mathcalB)$
arXiv Detail & Related papers (2021-12-05T12:12:49Z) - A theory of quantum subspace diagonalization [3.248953303528541]
We show that a quantum subspace diagonalization algorithm can accurately compute the smallest eigenvalue of a large Hermitian matrix.
Our results can be of independent interest to solving eigenvalue problems outside the context of quantum computation.
arXiv Detail & Related papers (2021-10-14T16:09:07Z) - 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) - Solving generalized eigenvalue problems by ordinary differential
equations on a quantum computer [0.0]
We propose a new quantum algorithm for symmetric generalized eigenvalue problems using ordinary differential equations.
The algorithm has lower complexity than the standard one based on quantum phase estimation.
arXiv Detail & Related papers (2020-10-28T15:04:33Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
We show that learning $ktimes k$, rank-$r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ samples.
We propose an algorithm that uses $cal O(frackrepsilon2log2fracepsilon)$ samples, a number linear in the high dimension, and nearly linear in the matrices, typically low, rank proofs.
arXiv Detail & Related papers (2020-09-30T19:10:32Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.