Quantum algorithm for solving linear systems of equations
read the original abstract
Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and a vector b, find a vector x such that Ax=b. We consider the case where one doesn't need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x, e.g., x'Mx for some matrix M. In this case, when A is sparse, N by N and has condition number kappa, classical algorithms can find x and estimate x'Mx in O(N sqrt(kappa)) time. Here, we exhibit a quantum algorithm for this task that runs in poly(log N, kappa) time, an exponential improvement over the best classical algorithm.
This paper has not been read by Pith yet.
Forward citations
Cited by 6 Pith papers
-
Constrained Optimal Polynomials for Quantum Linear System Solvers
Constrained Uniform Polynomial (CUP) and Constrained Adaptive Polynomial (CAP) solvers achieve lower error than standard QSVT and Chebyshev methods in noise-limited regimes by optimizing accuracy versus block-encoding...
-
Probabilistic quantum algorithm for Lyapunov equations and matrix inversion
Probabilistic quantum algorithm prepares mixed states proportional to Lyapunov equation solutions and matrix inverses using oracles for input matrices and a deterministic stopping rule.
-
A shortcut to an optimal quantum linear system solver
The paper gives a QLSS with query complexity (1+O(ε))κ ln(2√2/ε) using one kernel reflection when ||x|| is known, or O(κ log(1/ε)) overall, with explicit bound 56κ + 1.05κ ln(1/ε).
-
Lower overhead fault-tolerant building blocks for noisy quantum computers
New combinatorial proofs and circuit designs for quantum error correction reduce physical qubit overhead by up to 10x and time overhead by 2-6x for codes including Steane, Golay, and surface codes.
-
Quantum algorithm for solving differential equations using SLAC derivatives
Efficient quantum block-encodings of SLAC first-order derivative and Laplacian operators are built with LCU, state preparation, wavelet multi-scale transforms, and preconditioning to solve PDEs via QLSA with analyzed ...
-
Benchmarking a machine-learning differential equations solver on a neutral-atom logical processor
Logical quantum kernels outperform physical ones when solving differential equations on a neutral-atom processor, with gains traced to noise error detection in the logical encoding.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.