..., T − 1. Define . 4. Adjoin a three-dimensional register S in the state 5. Reverse steps 1–3, uncomputing any garbage produced along the way. The phase estimation procedure in steps 1-3 allows for the estimation of eigenvalues of A up to error . The ancilla register in step 4 is necessary to construct a final state with inverted eigenvalues corresponding to the diagonalized inverse of A. In this register, the functions f, g, are called filter functions. The states 'nothing', 'well' and 'ill' are used to instruct the loop body on how to proceed; 'nothing' indicates that the desired matrix inversion has not yet taken place, 'well' indicates that the inversion has taken place and the loop should halt, and 'ill' indicates that part of is in the ill-conditioned subspace of A and the algorithm will not be able to produce the desired inversion. Producing a state proportional to the inverse of A requires 'well' to be measured, after which the overall state of the system collapses to the desired state by the extended Born rule. Main loop The body of the algorithm follows the amplitude amplification procedure: starting with , the following operation is repeatedly applied: where and After each repetition, is measured and will produce a value of 'nothing', 'well', or 'ill' as described above. This loop is repeated until is measured, which occurs with a probability . Rather than repeating times to minimize error, amplitude amplification is used to achieve the same error resilience using only repetitions. Scalar measurement After successfully measuring 'well' on the system will be in a state proportional to: Finally, we perform the quantum-mechanical operator corresponding to M and obtain an estimate of the value of . Run time analysis Classical efficiency The best classical algorithm which produces the actual solution vector is Gaussian elimination, which runs in time. If A is s-sparse and positive semi-definite, then the Conjugate Gradient method can be used to find the solution vector , which can be found in time by minimizing the quadratic function . When only a summary statistic of the solution vector is needed, as is the case for the quantum algorithm for linear systems of equations, a classical computer can find an estimate of in . Quantum efficiency The runtime of the quantum algorithm for solving systems of linear equations originally proposed by Harrow et al. was shown to be ,