number of repetitions as it has some probability of failing. After it succeeds, we uncomputed the register and are left with a state proportional to: where is a quantum-mechanical representation of the desired solution vector x. To read out all components of x would require the procedure be repeated at least N times. However, it is often the case that one is not interested in itself, but rather some expectation value of a linear operator M acting on x. By mapping M to a quantum-mechanical operator and performing the quantum measurement corresponding to M, we obtain an estimate of the expectation value . This allows for a wide variety of features of the vector x to be extracted including normalization, weights in different parts of the state space, and moments without actually computing all the values of the solution vector x. Explanation of the algorithm Initialization Firstly, the algorithm requires that the matrix be Hermitian so that it can be converted into a unitary operator. In the case where is not Hermitian, define As is Hermitian, the algorithm can now be used to solve to obtain . Secondly, The algorithm requires an efficient procedure to prepare , the quantum representation of b. It is assumed that there exists some linear operator that can take some arbitrary quantum state to efficiently or that this algorithm is a subroutine in a larger algorithm and is given as input. Any error in the preparation of state is ignored. Finally, the algorithm assumes that the state can be prepared efficiently. Where for some large . The coefficients of are chosen to minimize a certain quadratic loss function which induces error in the subroutine described below. Hamiltonian simulation Hamiltonian simulation is used to transform the Hermitian matrix into a unitary operator, which can then be applied at will. This is possible if A is s-sparse and efficiently row computable, meaning it has at most s nonzero entries per row and given a row index these entries can be computed in time O(s). Under these assumptions, quantum Hamiltonian simulation allows to be simulated in time . subroutine The key subroutine to the algorithm, denoted , is defined as follows and incorporates a phase estimation subroutine: 1. Prepare on register C 2. Apply the conditional Hamiltonian evolution (sum) 3. Apply the Fourier transform to the register C. Denote the resulting basis states with for k = 0,