Quantum algorithm for linear systems of equations.

By Aram Wettroth Harrow, Avinatan Hassidim, Seth Lloyd. Physical Review Letters, 2008

3,228 citations recorded by the source corpus.

Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and a vector b(-->), find a vector x(-->) such that Ax(-->) = b(-->). We consider the case where one does not need to know the solution x(-->) itself, but rather an approximation of the expectation value of some operator associated with x(-->), e.g., x(-->)(dagger) Mx(-->) for some matrix M. In this case, when A is sparse, N x N and has condition number kappa, the fastest known classical algorithms can find x(-->) and estimate x(-->)(dagger) Mx(-->) in time scaling roughly as N square root(kappa). Here, we exhibit a quantum algorithm for estimating x(-->)(dagger) Mx(-->) whose runtime is a polynomial of log(N) and kappa. Indeed, for small values of kappa [i.e., poly log(N)], we prove (using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.

View Paper: https://www.semanticscholar.org/paper/ed562f0c86c80f75a8b9ac7344567e8b44c8d643

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Quantum information processing with superconducting circuits: a review (2016, methodology): “Recently, a quantum algorithm for solving a system of linear equations Ax = b (HHL) [364, 365] has attracted great interest and been used for constructing algorithms for both supervised and unsupervised machine learning [366–368], e.g. to classify data or to identify patterns in large data sets (‘Bi”
The future of quantum computing with superconducting qubits (2022, methodology): “…speedup include simulation of quantum many-body systems 19 , number theoretic problems such as integer factoring 5 , solving certain types of linear systems 20 , estimation of Betti numbers used in topological data analysis 21–23 , and computing topological invariants of knots and links 24 .”
Hamiltonian simulation using linear combinations of unitary operations (2012, methodology): “Even before a fault-tolerant quantum computer is built, quantum simulation techniques can be used to prove equivalence between Hamiltonian-based models of quantum computing (such as adiabatic quantum computing [1] and continuous-time quantum walk [2]) and to develop novel quantum algorithms [3, 4, 5”
Option Pricing using Quantum Computers (2019, unknown): “By leveraging the laws of quantum mechanics a quantum computer [6] may provide novel ways to solve computationally intensive problems such as quantum chemistry [7–10], solving linear systems of equations [11], and machine learning [12–14].”
Quipper: a scalable quantum programming language (2013, methodology): “We have demonstrated Quipper’s viability by implementing seven non-trivial quantum algorithms from the literature [2, 4, 8, 9, 13, 17, 23], as selected by IARPA [10].”
Variational Quantum Linear Solver (2019, methodology): “It is known that linear scaling is optimal [6].”
Qudits and High-Dimensional Quantum Computing (2020, methodology): “A long list of PEA applications includes Shor’s factorization algorithm [142]; simulation of quantum systems [1]; solving linear equations [69, 128]; and quantum counting [147].”
Machine learning \& artificial intelligence in the quantum domain (2017, methodology): “by modifying the original QLS algorithm (Harrow et al., 2009) to imprint not the inverses of eigenvalues but the eigenvalues themselves.”
Quantum Generative Adversarial Networks for learning and loading random distributions (2019, methodology): “[1] A.”
Quantum technology for military applications (2021, methodology): “Such a speedup was estimated especially for the HHL (HarrowHassidim-Lloyd) [50] algorithm for sparse matrices.”
High-order quantum algorithm for solving linear differential equations (2010, methodology): “[10] is based on a worst-case scenario, that ~b scales as Λ max ~x . k k It is easily shown that ~x scales as √ N t , provided the magnitude of the solution of the diﬀerential equation does not vary greatly in time.”