Efficient quantum algorithms for solving quantum linear system problems
- URL: http://arxiv.org/abs/2208.06763v3
- Date: Thu, 19 Jan 2023 14:14:04 GMT
- Title: Efficient quantum algorithms for solving quantum linear system problems
- Authors: Hefeng Wang and Hua Xiang
- Abstract summary: We present two quantum algorithms for solving the problem of finding the right singular vector with singular value zero of an augmented matrix $C$.
Both algorithms meet the optimal query complexity in $kappa $, and are simpler than previous algorithms.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We transform the problem of solving linear system of equations
$A\mathbf{x}=\mathbf{b}$ to a problem of finding the right singular vector with
singular value zero of an augmented matrix $C$, and present two quantum
algorithms for solving this problem. The first algorithm solves the problem
directly by applying the quantum eigenstate filtering algorithm with query
complexity of $O\left( s\kappa \log \left( 1/\epsilon \right) \right) $ for a
$s$-sparse matrix $C$, where $\kappa $ is the condition number of the matrix
$A$, and $\epsilon $ is the desired precision. The second algorithm uses the
quantum resonant transition approach, the query complexity scales as
$O\left[s\kappa + \log\left( 1/\epsilon \right)/\log \log \left( 1/\epsilon
\right) \right] $. Both algorithms meet the optimal query complexity in $\kappa
$, and are simpler than previous algorithms.
Related papers
- Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
Quantum algorithms for linear systems produce the solution state $A-1|brangle$ by querying two oracles.
We present a quantum linear system algorithm making $mathbfThetaleft (1/sqrtpright)$ queries to $O_b$, which is optimal in the success probability.
In various applications such as solving differential equations, we can further improve the dependence on $p$ using a block preconditioning scheme.
arXiv Detail & Related papers (2024-10-23T18:00:01Z) - Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
Gradient descent is one of the most basic algorithms for solving continuous optimization problems.
We propose a quantum algorithm that returns an $varepsilon$-approximation of its gradient with query complexity $widetildeO (1/varepsilon)$.
We also propose two quantum algorithms for Hessian estimation, aiming to improve quantum analogs of Newton's method.
arXiv Detail & Related papers (2024-07-04T11:03:48Z) - Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
We propose quantum algorithms for calculating the determinant and inverse of an $(N-1)times (N-1)$ matrix.
The basic idea is to encode each row of the matrix into a pure state of some quantum system.
arXiv Detail & Related papers (2024-01-29T23:23:27Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$.
Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
arXiv Detail & Related papers (2023-07-13T18:59:28Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
We propose fast and practical quantum-inspired classical algorithms for solving linear systems.
Our main contribution is the application of the heavy ball momentum method to quantum-inspired classical algorithms for solving linear systems.
arXiv Detail & Related papers (2023-07-13T08:46:19Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
We introduce a quantum linear solver algorithm combining ideasdiabatic quantum computing with filtering techniques based on quantum signal processing.
Our protocol reduces the cost of quantum linear solvers over state-of-the-art close to an order of magnitude for early implementations.
arXiv Detail & Related papers (2023-05-19T00:07:32Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
We study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems.
The reason for this is that these algorithms require performing a complex binary procedure, which makes them neither optimal nor practical.
We fix this fundamental issue by providing the first algorithm with $mathcalOleft(epsilon-2/(p+1)right) $pth order oracle complexity.
arXiv Detail & Related papers (2022-05-19T16:04:40Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem.
We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
arXiv Detail & Related papers (2022-04-13T22:18:47Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model.
We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm.
The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations.
It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
arXiv Detail & Related papers (2020-02-20T17:52:18Z)
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.