A quantum algorithm for solving linear equations

Quantum algorithms are usually considered to be efficient when they present an exponentially smaller complexity than their classical counterparts. Harrow, Hassidim and Lloyd (HHL) proposed an algorithm for solving linear equations. It made use of the quantum phase estimation to efficiently decompose hermitian matrices into their eigenvalues. The first part of the talk is dedicated to presenting this algorithm. The second part is based on a recent work. To reduce the tolerated error, the quantum phase estimation requires an increasing number of qubits wich is a limiting factor on quantum computers. We analyzed the error of the HHL algorithm as a function of the number of qubits and proposed a modification that improves the convergence towards the exact solution without changing the complexity.