Solving systems of linear equations with quantum mechanics
phys.org
phys.org
But I guess it all depends on what kind of Ns you are looking at.
I sometimes find myself working with ten thousand 'things', but very rarely with thirty billion.
> We consider the case where one doesn't need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x, e.g., x'Mx for some matrix M. In this case, when A is sparse, N by N and has condition number kappa, classical algorithms can find x and estimate x'Mx in O(N sqrt(kappa)) time. Here, we exhibit a quantum algorithm for this task that runs in poly(log N, kappa) time, an exponential improvement over the best classical algorithm.