Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
read the original abstract
We present two new quantum algorithms. Our first algorithm is a generalization of amplitude amplification to the case when parts of the quantum algorithm that is being amplified stop at different times. Our second algorithm uses the first algorithm to improve the running time of Harrow et al. algorithm for solving systems of linear equations from O(kappa^2 log N) to O(kappa log^3 kappa log N) where \kappa is the condition number of the system of equations.
This paper has not been read by Pith yet.
Forward citations
Cited by 7 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...
-
Generalized quantum singular value transformation with application in quantum conjugate gradient least squares algorithm
Introduces GQSVT for non-unitary matrices by extending GQSP and applies it to a hybrid quantum CGLS solver.
-
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/ε).
-
Tensor-Programmable Quantum Circuits for Solving Differential Equations
A quantum solver for PDEs is introduced via flexible matrix product operator representations with mid-circuit measurements and state-dependent norm correction to handle non-unitary dynamics.
-
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 ...
-
Practical lower bounds for hybrid quantum interior point methods in linear programming
Hybrid quantum interior point methods for linear programming have no practical runtime advantage over classical solvers like HiGHS on realistic instances because their quantum lower bounds already exceed classical per...
-
Constant Factor Analysis of Optimal Quantum Linear Solvers in Practice
Adiabatic solver slightly outperforms shortcut when solution norm unknown; shortcut significantly better for non-Hermitian matrices when norm known.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.