Preconditioned quantum linear system algorithm

Abstract

We describe a quantum algorithm that generalizes the quantum linear system algorithm [Harrow et al., Phys. Rev. Lett. 103, 150502 (2009)] to arbitrary problem specifications. We develop a state preparation routine that can initialize generic states, show how simple ancilla measurements can be used to calculate many quantities of interest, and integrate a quantum-compatible preconditioner that greatly expands the number of problems that can achieve exponential speedup over classical linear systems solvers. To demonstrate the algorithm's applicability, we show how it can be used to compute the electromagnetic scattering cross section of an arbitrary target exponentially faster than the best classical algorithm.

5 pages; Substantial revisions, including addition of preconditioner

References in corpus (3)

• Quantum algorithm for solving linear systems of equations
• Quantum Data Fitting
• Preparation of many-body states for quantum simulation

Cited by in corpus (132)

• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• Quantum Chemistry in the Age of Quantum Computing
• Quantum algorithms: an overview
• Quantum machine learning: a classical perspective
• Prediction by linear regression on a quantum computer
• An Artificial Neuron Implemented on an Actual Quantum Processor
• Efficient quantum algorithm for dissipative nonlinear differential equations
• Variational quantum simulation of general processes
• A quantum linear system algorithm for dense matrices
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum algorithms and the finite element method
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Variational algorithms for linear algebra
• 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
• qHiPSTER: The Quantum High Performance Software Testing Environment
• Black-box quantum state preparation without arithmetic
• Quantum assisted Gaussian process regression
• Quantum algorithm for non-homogeneous linear partial differential equations
• Biology and medicine in the landscape of quantum advantages
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Minimizing estimation runtime on noisy quantum computers
• Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target
• Quantum computing of fluid dynamics using the hydrodynamic Schrödinger equation
• Variational Quantum Singular Value Decomposition
• Asymptotic Quantum Algorithm for the Toeplitz Systems
• On applications of quantum computing to plasma simulations
• Exponential quantum speedup in simulating coupled classical oscillators
• Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
• Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Quantum computation of molecular response properties
• Resonant Quantum Principal Component Analysis
• QASMBench: A Low-level QASM Benchmark Suite for NISQ Evaluation and Simulation
• Variational Quantum Algorithms for Dimensionality Reduction and Classification
• Machine learning \& artificial intelligence in the quantum domain
• Efficient quantum amplitude encoding of polynomial functions
• Quantum algorithms for approximate function loading
• Quantum Variational Solving of Nonlinear and Multi-Dimensional Partial Differential Equations
• Box algorithm for the solution of differential equations on a quantum annealer
• Quantum Circulant Preconditioner for Linear System of Equations
• Exact gate decompositions for photonic quantum computing
• An Application of Quantum Annealing Computing to Seismic Inversion
• Analog quantum simulation of partial differential equations
• Quantum Algorithm for Solving the Advection Equation using Hamiltonian Simulation
• Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines
• Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
• Quantum algorithm for time-dependent differential equations using Dyson series
• Analyzing the impact of time-correlated noise on zero-noise extrapolation
• Variational Quantum-Based Simulation of Waveguide Modes
• Quantum Computing and Preconditioners for Hydrological Linear Systems
• Quantum Algorithms to Matrix Multiplication
• Quantum computing of reacting flows via Hamiltonian simulation
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Incompressible Navier-Stokes solve on noisy quantum hardware via a hybrid quantum-classical scheme
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• A hybrid classical-quantum approach to solve the heat equation using quantum annealers
• Realizing quantum linear regression with auxiliary qumodes
• Logic Synthesis for Quantum Computing
• Quantum algorithms for computing observables of nonlinear partial differential equations
• A Quantum Interior-Point Predictor-Corrector Algorithm for Linear Programming
• Logic Synthesis for Fault-Tolerant Quantum Computers
• Quantum-Inspired Classical Algorithms for Singular Value Transformation
• Harrow-Hassidim-Lloyd algorithm without ancilla postselection
• Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems
• Experimental Quantum Learning of a Spectral Decomposition
• Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling
• Quantum algorithms for matrix operations and linear systems of equations
• Analytical Error Analysis of Clifford Gates by the Fault-Path Tracer Method
• Distillation protocols for Fourier states in quantum computing
• Quantum Quantitative Trading: High-Frequency Statistical Arbitrage Algorithm
• Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations
• Quantum Carleman linearisation efficiency in nonlinear fluid dynamics
• Simulation of linear non-Hermitian boundary-value problems with quantum singular value transformation
• Quantum vs. classical algorithms for solving the heat equation
• An Improved Method for Quantum Matrix Multiplication
• Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
• Quantum Algorithms for Geologic Fracture Networks
• Solving the Hele-Shaw flow using the Harrow-Hassidim-Lloyd algorithm on superconducting devices: A study of efficiency and challenges
• Quantum Splines for Non-Linear Approximations
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method
• Coherence dynamics in quantum algorithm for linear systems of equations
• Quantum Algorithm For Estimating Eigenvalue
• Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
• An HHL-Based Algorithm for Computing Hitting Probabilities of Quantum Random Walks
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Simulations of Future Particle Accelerators: Issues and Mitigations
• Quantum Approximate Optimization Algorithm for Maximum Likelihood Detection in Massive MIMO
• From linear combination of quantum states to Grover's searching algorithm
• An Early Investigation of the HHL Quantum Linear Solver for Scientific Applications
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Hybrid algorithms to solve linear systems of equations with limited qubit resources
• Quantum Newton's method for solving system of nonlinear algebraic equations
• Pricing multi-asset derivatives by finite difference method on a quantum computer
• Identifying Bottlenecks of NISQ-friendly HHL algorithms
• Review of Quantum Algorithms for Systems of Linear Equations
• Inverse iteration quantum eigensolvers assisted with a continuous variable
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
• Efficient Light Propagation Algorithm using Quantum Computers
• Computing scalar products via a two-terminal quantum transmission line
• Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
• Alternatives to a nonhomogeneous partial differential equation quantum algorithm
• Calculating response functions of coupled oscillators using quantum phase estimation
• qlbm -- A Quantum Lattice Boltzmann Software Framework
• A quantum-inspired algorithm for approximating statistical leverage scores
• Adaptive Circuit Learning of Born Machine: Towards Realization of Amplitude Embedding and Quantum Data Loading
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• Quantum Realization of the Finite Element Method
• Variational quantum algorithm based on Lagrange polynomial encoding to solve differential equations
• A Quantum-Inspired Algorithm for Wave Simulation Using Tensor Networks
• Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations
• Blockwise Optimization for Projective Variational Quantum Dynamics (BLOP-VQD): Algorithm and Implementation for Lattice Systems
• Quantum linear system algorithm with optimal queries to initial state preparation
• Quantum Machine Learning For Classical Data
• Refined Criteria for QRAM Error Suppression via Efficient Large-Scale QRAM Simulator
• End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
• Quantum Arnoldi and conjugate gradient iteration algorithm
• Quantum approximated cloning-assisted density matrix exponentiation
• Resource-efficient quantum algorithm for linear systems of equations
• Optimisation of Quantum Hamiltonian Evolution: From Two Projection Operators to Local Hamiltonians
• Quantum oracles for the finite element method
• Quantum Algorithm to Cubic Spline Interpolation
• Preconditioned Block Encodings for Quantum Linear Systems
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms
• Quantum Radon Transform and Its Application
• Fundamental Machine Learning Routines as Quantum Algorithms on a Superconducting Quantum Computer
• Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers
• Quantum Algorithm for a Convergent Series of Approximations towards the Exact Solution of the Lowest Eigenstates of a Hamiltonian