Quantum eigenvalue processing
- URL: http://arxiv.org/abs/2401.06240v1
- Date: Thu, 11 Jan 2024 19:49:31 GMT
- Title: Quantum eigenvalue processing
- Authors: Guang Hao Low and Yuan Su
- Abstract summary: 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.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many problems in linear algebra -- such as those arising from non-Hermitian
physics and differential equations -- can be solved on a quantum computer by
processing eigenvalues of the non-normal input matrices. However, the existing
Quantum Singular Value Transformation (QSVT) framework is ill-suited to this
task, as eigenvalues and singular values are different in general. We present a
Quantum EigenValue Transformation (QEVT) framework for applying arbitrary
polynomial transformations on eigenvalues of block-encoded non-normal
operators, and a related Quantum EigenValue Estimation (QEVE) algorithm for
operators with real spectra. QEVT has query complexity to the block encoding
nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the
Heisenberg-limited scaling for diagonalizable input matrices. As applications,
we develop a linear differential equation solver with strictly linear time
query complexity for average-case diagonalizable operators, as well as a ground
state preparation algorithm that upgrades previous nearly optimal results for
Hermitian Hamiltonians to diagonalizable matrices with real spectra.
Underpinning our algorithms is an efficient method to prepare a quantum
superposition of Faber polynomials, which generalize the nearly-best uniform
approximation properties of Chebyshev polynomials to the complex plane. Of
independent interest, we also develop techniques to generate $n$ Fourier
coefficients with $\mathbf{O}(\mathrm{polylog}(n))$ gates compared to prior
approaches with linear cost.
Related papers
- Quantum Eigensolver for General Matrices [5.811990276393904]
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.
arXiv Detail & Related papers (2024-01-22T16:29:08Z) - Using Variational Eigensolvers on Low-End Hardware to Find the Ground
State Energy of Simple Molecules [0.0]
Key properties of physical systems can be described by the eigenvalues of matrices that represent the system.
Computational algorithms that determine the eigenvalues of these matrices exist, but they generally suffer from a loss of performance as the matrix grows in size.
This process can be expanded to quantum computation to find the eigenvalues with better performance than the classical algorithms.
arXiv Detail & Related papers (2023-10-29T18:36:18Z) - Randomized semi-quantum matrix processing [0.0]
We present a hybrid quantum-classical framework for Monte-Carlo simulation of generic matrix functions.
Our framework provides a pathway towards early fault-tolerant quantum linear algebra applications.
arXiv Detail & Related papers (2023-07-21T18:00:28Z) - 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) - Softmax-free Linear Transformers [90.83157268265654]
Vision transformers (ViTs) have pushed the state-of-the-art for visual perception tasks.
Existing methods are either theoretically flawed or empirically ineffective for visual recognition.
We propose a family of Softmax-Free Transformers (SOFT)
arXiv Detail & Related papers (2022-07-05T03:08:27Z) - 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) - Contour Integral-based Quantum Algorithm for Estimating Matrix
Eigenvalue Density [5.962184741057505]
We propose a quantum algorithm for computing the eigenvalue density in a given interval.
The eigenvalue count in a given interval is derived as the probability of observing a bit pattern in a fraction of the qubits of the output state.
arXiv Detail & Related papers (2021-12-10T08:58:44Z) - 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) - Variational Adiabatic Gauge Transformation on real quantum hardware for
effective low-energy Hamiltonians and accurate diagonalization [68.8204255655161]
We introduce the Variational Adiabatic Gauge Transformation (VAGT)
VAGT is a non-perturbative hybrid quantum algorithm that can use nowadays quantum computers to learn the variational parameters of the unitary circuit.
The accuracy of VAGT is tested trough numerical simulations, as well as simulations on Rigetti and IonQ quantum computers.
arXiv Detail & Related papers (2021-11-16T20:50:08Z) - 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)
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.