Years and Authors of Summarized Original Work
-
2009; Harrow, Hassidim, Lloyd
-
2012; Ambainis
Problem Definition
The problem is to find a vector \(x \in \mathbb{C}^{N}\) such that Ax = b, for some given inputs \(A \in \mathbb{C}^{N\times N}\) and \(b \in \mathbb{C}^{N}\). Several variants are also possible, such as rectangular matrices A, including overdetermined and underdetermined systems of equations.
Unlike in the classical case, the output of this algorithm is a quantum state on \(\log (N)\) qubits whose amplitudes are proportional to the entries of x, along with a classical estimate of \(\|x\| := \sqrt{\sum \nolimits_{i } \vert x_{i } \vert ^{2}}\). Similarly, the input b is given as a quantum state. The matrix A is specified implicitly as a row-computable matrix. Specifying the input and output in this way makes it possible to find x in time sublinear, or even polylogarithmic, in N. The next section has more discussion of the relation of this algorithm to classical linear systems...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Ambainis A (2012) Variable time amplitude amplification and quantum algorithms for linear algebra problems. In: STACS, Paris, vol 14, pp 636 647
Berry DW (2014) High-order quantum algorithm for solving linear differential equations. J Phys A 47(10):105301
Berry DW, Childs AM, Cleve R, Kothari R, Somma RD (2014) Exponential improvement in precision for simulating sparse hamiltonians. In: Proceedings of STOC 2014, New York, pp 283–292
Clader BD, Jacobs BC, Sprouse CR (2013) Preconditioned quantum linear system algorithm. Phys Rev Lett 110:250504
Harrow AW, Hassidim A, Lloyd S (2009) Quantum algorithm for solving linear systems of equations. Phys Rev Lett 15(103):150502
Wiebe N, Braun D, Lloyd S (2012) Quantum algorithm for data fitting. Phys Rev Lett 109:050505
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer Science+Business Media New York
About this entry
Cite this entry
Harrow, A.W. (2016). Quantum Algorithms for Systems of Linear Equations. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_771
Download citation
DOI: https://doi.org/10.1007/978-1-4939-2864-4_771
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4939-2863-7
Online ISBN: 978-1-4939-2864-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering