Quantum relaxed row and column iteration methods based on block-encoding
- URL: http://arxiv.org/abs/2206.13730v1
- Date: Tue, 28 Jun 2022 03:33:32 GMT
- Title: Quantum relaxed row and column iteration methods based on block-encoding
- Authors: Xiao-Qi Liu, Jing Wang, Ming Li, Shu-Qian Shen, Weiguo Li, Shao-Ming
Fei
- Abstract summary: We present quantum algorithms for the relaxed row and column iteration methods.
We generalize row and column iteration methods to solve linear systems on a quantum computer.
- Score: 7.489991375172152
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Iteration method is commonly used in solving linear systems of equations. We
present quantum algorithms for the relaxed row and column iteration methods by
constructing unitary matrices in the iterative processes, which generalize row
and column iteration methods to solve linear systems on a quantum computer.
Comparing with the conventional row and column iteration methods, the
convergence accelerates when appropriate parameters are chosen. Once the
quantum states are efficiently prepared, the complexity of our relaxed row and
column methods is improved exponentially and is linear with the number of the
iteration steps. In addition, phase estimations and Hamiltonian simulations are
not required in these algorithms.
Related papers
- Quantum Iterative Methods for Solving Differential Equations with Application to Computational Fluid Dynamics [14.379311972506791]
We propose quantum methods for solving differential equations based on a gradual improvement of the solution via an iterative process.
We benchmark the approach on paradigmatic fluid dynamics problems.
arXiv Detail & Related papers (2024-04-12T17:08:27Z) - An Efficient Quantum Algorithm for Linear System Problem in Tensor Format [4.264200809234798]
We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA.
We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension.
arXiv Detail & Related papers (2024-03-28T20:37:32Z) - Quantum algorithms for linear and non-linear fractional
reaction-diffusion equations [3.409316136755434]
We investigate efficient quantum algorithms for nonlinear fractional reaction-diffusion equations with periodic boundary conditions.
We present a novel algorithm that combines the linear combination of Hamiltonian simulation technique with the interaction picture formalism.
arXiv Detail & Related papers (2023-10-29T04:48:20Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks.
The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions.
We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
arXiv Detail & Related papers (2023-09-30T15:57:14Z) - Hybrid quantum-classical and quantum-inspired classical algorithms for
solving banded circulant linear systems [0.8192907805418583]
We present an efficient algorithm based on convex optimization of combinations of quantum states to solve for banded circulant linear systems.
By decomposing banded circulant matrices into cyclic permutations, our approach produces approximate solutions to such systems with a combination of quantum states linear to $K$.
We validate our methods with classical simulations and actual IBM quantum computer implementation, showcasing their applicability for solving physical problems such as heat transfer.
arXiv Detail & Related papers (2023-09-20T16:27:16Z) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
We introduce a new inference scheme that avoids explicit construction of the covariance matrix.
Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm.
On several simulations, our method scales better than existing approaches in computation time and memory.
arXiv Detail & Related papers (2022-02-25T16:35:26Z) - 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-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression.
We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
arXiv Detail & Related papers (2020-11-09T01:13:07Z) - Combinatorial optimization through variational quantum power method [0.0]
We present a variational quantum circuit method for the power iteration.
It can be used to find the eigenpairs of unitary matrices and so their associated Hamiltonians.
The circuit can be simulated on the near term quantum computers with ease.
arXiv Detail & Related papers (2020-07-02T10:34:16Z) - Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data.
Based upon our row sampling algorithm, we give the fastest known algorithm for quantile regression and a graph sparsification algorithm for balanced directed graphs.
arXiv Detail & Related papers (2020-06-15T13:40:07Z) - Accelerating Feedforward Computation via Parallel Nonlinear Equation
Solving [106.63673243937492]
Feedforward computation, such as evaluating a neural network or sampling from an autoregressive model, is ubiquitous in machine learning.
We frame the task of feedforward computation as solving a system of nonlinear equations. We then propose to find the solution using a Jacobi or Gauss-Seidel fixed-point method, as well as hybrid methods of both.
Our method is guaranteed to give exactly the same values as the original feedforward computation with a reduced (or equal) number of parallelizable iterations, and hence reduced time given sufficient parallel computing power.
arXiv Detail & Related papers (2020-02-10T10:11:31Z)
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.