A possible general algorithm for quantum computers?

Exciting news comes from MIT via Next Big Future: a general algorithm for quantum computers which solves linear systems of equations. This is big news, since recent years have shown significant progress in overcoming technical challenges of quantum computing, but the lack of a general linear algorithm that was demonstrably faster than digital computers threatened to confine QC to a small set of somewhat esoteric problems like code-breaking and database search. Digital algorithms for linear systems take on the order of N steps to solve N equations, where this algorithm takes on the order of log(N). Not a big difference for small matrices, but enormously better as the matrices grow in size. A general linear algorithm that is faster than digital algorithms for the same thing is promising, because linear systems underlay virtually everything modern computers do well.

MIT researchers present a new algorithm that could bring the same type of efficiency to systems of linear equations — whose solution is crucial to image processing, video processing, signal processing, robot control, weather modeling, genetic analysis and population analysis, to name just a few applications.

A gotcha, of course, does exist. Namely, once the result is determined it is in a quantum superposition, so it takes order-N steps to read it out. Two possible solutions present themselves to my uneducated mind: the read-out step may be something that can be done massively in parallel; i.e. by entangling the "result" qubits and sending them to N readers which can be purpose-built cheaply to just be able to query a set number of qubits in a set way. The second way is working with the problem rather than around it. Many or most matrices a digital computer sees are either highly sparse (consisting overwhelmingly of zeros), and/or most of the answers are trivial. This can be exploited using digital computers in parallel. For instance, a finite element analysis might be run on a digital computer with a few million nodes, and simultaneously on a quantum computer with trillions of nodes. Then the digital computer could direct the quantum computer to only query the nodes with high stress concentrations to bring them to the higher quantum resolution. Similarly, systems can be set up so that the pertinent variables are in a known location. A market forecast, for instance, might take into account trillions of variables to forecast a stock price in the last row of the results vector.