Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations

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 κis the condition number of the system of equations.

17 pages, no figures, v2: various small corrections

References in corpus (2)

• Quantum algorithm for solving linear systems of equations
• A quantum algorithm to solve nonlinear differential equations

Cited by in corpus (25)

• Quantum algorithms: an overview
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Variational Quantum Linear Solver
• Quantum algorithms and the finite element method
• High-precision quantum algorithms for partial differential equations
• Quantum Algorithm for Simulating the Wave Equation
• On the impact of quantum computing technology on future developments in high-performance scientific computing
• Universal discriminative quantum neural networks
• Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target
• Quantum linear systems algorithms: a primer
• Quantum Computing for Fusion Energy Science Applications
• An Application of Quantum Annealing Computing to Seismic Inversion
• Quantum rejection sampling
• Scalable Benchmarks for Gate-Based Quantum Computers
• Quantum Circuit Design Methodology for Multiple Linear Regression
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Quantum exploration algorithms for multi-armed bandits
• Span-program-based quantum algorithm for the rank problem
• Improved amplitude amplification strategies for the quantum simulation of classical transport problems
• New Developments in Quantum Algorithms
• Quantum Finite Volume Method for Computational Fluid Dynamics with Classical Input and Output
• Review of Quantum Algorithms for Systems of Linear Equations
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Quantum Chebyshev's Inequality and Applications
• Quantum simulation and circuit design for solving multidimensional Poisson equations