Quantum algorithm for linear systems of equations

The quantum algorithm for linear systems of equations, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd, is a quantum algorithm formulated in 2009 for solving linear systems. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations. The quantum algorithm for linear systems of equations, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd, is a quantum algorithm formulated in 2009 for solving linear systems. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations. The algorithm is one of the main fundamental algorithms expected to provide a speedup over their classical counterparts, along with Shor's factoring algorithm, Grover's search algorithm and quantum simulation. Provided the linear system is sparse and has a low condition number κ {displaystyle kappa } , and that the user is interested in the result of a scalar measurement on the solution vector, instead of the values of the solution vector itself, then the algorithm has a runtime of O ( log ⁡ ( N ) κ 2 ) {displaystyle O(log(N)kappa ^{2})} , where N {displaystyle N} is the number of variables in the linear system. This offers an exponential speedup over the fastest classical algorithm, which runs in O ( N κ ) {displaystyle O(Nkappa )} (or O ( N κ ) {displaystyle O(N{sqrt {kappa }})} for positive semidefinite matrices). An implementation of the quantum algorithm for linear systems of equations was first demonstrated in 2013 by Cai et al., Barz et al. and Pan et al. in parallel. The demonstrations consisted of simple linear equations on specially designed quantum devices. The first demonstration of a general-purpose version of the algorithm appeared in 2018 in the work of Zhao et al. Due to the prevalence of linear systems in virtually all areas of science and engineering, the quantum algorithm for linear systems of equations has the potential for widespread applicability. The problem we are trying to solve is: given a N × N {displaystyle N imes N} Hermitian matrix A {displaystyle A} and a unit vector b → {displaystyle {overrightarrow {b}}} , find the solution vector x → {displaystyle {overrightarrow {x}}} satisfying A x → = b → {displaystyle A{overrightarrow {x}}={overrightarrow {b}}} . This algorithm assumes that the user is not interested in the values of x → {displaystyle {overrightarrow {x}}} itself, but rather the result of applying some operator M {displaystyle M} onto x, ⟨ x | M | x ⟩ {displaystyle langle x|M|x angle } . First, the algorithm represents the vector b → {displaystyle {overrightarrow {b}}} as a quantum state of the form: Next, Hamiltonian simulation techniques are used to apply the unitary operator e i A t {displaystyle e^{iAt}} to | b ⟩ {displaystyle |b angle } for a superposition of different times t {displaystyle t} . The ability to decompose | b ⟩ {displaystyle |b angle } into the eigenbasis of A {displaystyle A} and to find the corresponding eigenvalues λ j {displaystyle lambda _{j}} is facilitated by the use of quantum phase estimation.