Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
read the original abstract
Harrow, Hassidim, and Lloyd showed that for a suitably specified $N \times N$ matrix $A$ and $N$-dimensional vector $\vec{b}$, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations $A\vec{x}=\vec{b}$. If $A$ is sparse and well-conditioned, their algorithm runs in time $\mathrm{poly}(\log N, 1/\epsilon)$, where $\epsilon$ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in $\log(1/\epsilon)$, exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on $\epsilon$ is prohibitive.
This paper has not been read by Pith yet.
Forward citations
Cited by 16 Pith papers
-
Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems
Develops a quantum algorithm for linear matrix differential equations with query complexity O~(ν L t / ε) that is nearly optimal and yields polynomial to exponential speedups for open quantum system simulation.
-
Analytical Angle-Finding and Series Expansions for Quantum Signal Processing via Orthogonal Polynomial Theory
Quantum signal processing angles admit closed-form expressions via orthogonal polynomial theory, allowing O(log(1/ε)) gate block-encodings of smooth functions through Hermite expansions and full characterization of SU...
-
Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm
A classical polynomial-time algorithm for optimized sampling of lottery tickets in neural networks removes the exponential dependence on data dimension from prior classical approaches.
-
Quantum Multi-Level Estimation of Functionals of Discrete Distributions
A quantum multi-level framework achieves near-optimal query complexity for q-Tsallis entropy estimation for q>1 and a speedup for q<1 over classical methods.
-
Quantum Data Loading for Carleman Linearized Systems: Application to the Lattice-Boltzmann Equation
A new LCNU-to-LCU decomposition yields a quantum framework for Carleman-linearized lattice Boltzmann equations whose term count scales as O(α² Q²) and is independent of spatial or temporal grid points.
-
Quantum Data Loading for Carleman Linearized Systems: Application to the Lattice-Boltzmann Equation
A new LCNU-to-LCU decomposition enables a generalized quantum framework for Carleman-linearized polynomial systems like the lattice Boltzmann equation, with Ns scaling as O(α² Q²) independent of spatial and temporal d...
-
Quantum algorithm for solving high-dimensional linear stochastic differential equations via amplitude encoding of the noise term
Quantum algorithms achieve polylog(N) complexity for high-dimensional linear SDEs by amplitude-encoding the solution and noise via Dyson series or Euler-Maruyama approximations plus quantum linear systems solvers.
-
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...
-
A Unified Poisson Summation Framework for Generalized Quantum Matrix Transformations
A dual Fourier-PSF and contour-PSF framework resolves the smoothness-sparsity trade-off for efficient quantum simulation of singular and holomorphic matrix functions.
-
Cobble: Compiling Block Encodings for Quantum Computational Linear Algebra
Cobble is a domain-specific language for quantum block encodings that compiles high-level matrix expressions to optimized circuits using analyses and quantum singular value transformation, achieving 2.6x-25.4x speedup...
-
Quantum Data Loading for Carleman Linearized Systems: Application to the Lattice-Boltzmann Equation
A matrix decomposition into linear combinations of non-unitaries produces an LCU for any Carleman-linearized polynomial system and yields an O(α² Q²) term count for the 3D lattice Boltzmann equation independent of spa...
-
Block-encodings as programming abstractions: The Eclipse Qrisp BlockEncoding Interface
The Eclipse Qrisp BlockEncoding interface provides high-level programming abstractions for block-encodings, enabling easier implementation of quantum algorithms such as QSVT, matrix inversion, and Hamiltonian simulation.
-
Quantum Simulation of Non-Hermitian Special Functions and Dynamics via Contour-based Matrix Decomposition
CBMD decomposes non-Hermitian operators via contour residues to enable optimal-query quantum simulation of first-order dynamics and special functions such as Bessel and Airy evolutions without requiring diagonalizability.
-
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 ...
-
Optimizing Quantum Chemistry Simulations with a Hybrid Quantization Scheme
A hybrid quantization scheme enables efficient switching between first- and second-quantization in quantum circuits for molecular systems, claiming up to three orders of magnitude fewer ground-state preparations for 2...
-
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...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.