sparse condition number measurement P algorithm
Provided the linear system is a 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(N\kappa )}

 (or 



O
(
N


κ


)


{\displaystyle O(N{\sqrt {\kappa }})}

 for positive semidefinite matrices).
