Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision

DOI10.1137/16M1087072zbMath1383.68034arXiv1511.02306MaRDI QIDQ4602374

Andrew M. Childs, Rolando Somma, Robin Kothari

Publication date: 10 January 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.02306

zbMATH Keywords

linear systems quantum algorithms quantum complexity

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (45)

Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems ⋮ Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Graph isomorphism and Gaussian boson sampling ⋮ FEqa: Finite element computations on quantum annealers ⋮ Quantum algorithm for the Navier–Stokes equations by using the streamfunction-vorticity formulation and the lattice Boltzmann method ⋮ Quantum spectral methods for differential equations ⋮ Quantum radial basis function method for the Poisson equation ⋮ Quantum algorithm for linear differential equations with exponentially improved dependence on precision ⋮ Quantum vs. classical algorithms for solving the heat equation ⋮ Quantum fast Poisson solver: the algorithm and complete and modular circuit design ⋮ Quantum regularized least squares solver with parameter estimate ⋮ Qubit lattice algorithm simulations of Maxwell's equations for scattering from anisotropic Dielectric objects ⋮ Quantum algorithm for estimating largest eigenvalues ⋮ Time Complexity Analysis of Quantum Difference Methods for Multiscale Transport Equations ⋮ Fast black-box quantum state preparation based on linear combination of unitaries ⋮ Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation ⋮ Solving Large‐Scale Linear Systems of Equations by a Quantum Hybrid Algorithm ⋮ Extracting a function encoded in amplitudes of a quantum state by tensor network and orthogonal function expansion ⋮ Highly optimized quantum circuits synthesized via data-flow engines ⋮ Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices ⋮ Quantum simulation for partial differential equations with physical boundary or interface conditions ⋮ Quantum algorithm for matrix logarithm by integral formula ⋮ Quantum radial basis function method for scattered data interpolation ⋮ Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations ⋮ Configurable sublinear circuits for quantum state preparation ⋮ An improved method for quantum matrix multiplication ⋮ A polynomial system for bit-based division property solving by quantum algorithm ⋮ An improved quantum algorithm for support matrix machines ⋮ A survey on HHL algorithm: from theory to application in quantum machine learning ⋮ Faster ground state preparation and high-precision ground energy estimation with fewer qubits ⋮ Quantum algorithm design: techniques and applications ⋮ Efficient decoding scheme of non-uniform concatenation quantum code with deep neural network ⋮ An extended row and column method for solving linear systems on a quantum computer ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast quantum subroutines for the simplex method ⋮ Time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations ⋮ Quantum relaxed row and column iteration methods based on block-encoding ⋮ Quantum linear system algorithm applied to communication systems ⋮ Variational quantum solutions to the advection-diffusion equation for applications in fluid dynamics ⋮ Discontinuous Galerkin method with Voronoi partitioning for quantum simulation of chemistry ⋮ Quantum approach to accelerate finite volume method on steady computational fluid dynamics problems ⋮ A quantum interior-point predictor–corrector algorithm for linear programming ⋮ An improved algorithm for computing hitting probabilities of quantum walks

Cites Work

This page was built for publication: Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision