In the science press, Big News often turns out to be hyped trivia, but the current Big News in quantum computing is something else — a self-hyping mutant of genuine big news, the discovery of an algorithm that promises exponential speedup in a class of problems where the result depends on the solution to a large system of linear equations. Contrary to the mutant news, however, the algorithm does not provide solutions to systems of linear equations: It outputs scalars, not vectors, and this is not at all the same thing.
The paper, published in Phys. Rev. Letters, reports work done at University of Bristol and MIT (Seth Lloyd is a coauthor). The mutation appears in the press release from the MIT News Office, which headlines “A quantum algorithm that solves systems of linear equation”, and says that
The quantum algorithm…can solve systems with a trillion equations and a trillion variables.
Well, no, it can’t — the output is a trillion times smaller. [In the comments, Larry notes that the MIT News Office article later quotes Lloyd directly, explaining the key caveat: that the algorithm delivers a scalar measurement on a solution vector, which can be a function of the entire vector or, as a special case, any one of the trillion vector components.]
Science News, reasonably enough, follows the not-quite-right formulation in the MIT lead, speaking of the algorithm “quickly solving monster linear equations”, while a brief news item in Science reports that “Solving a set of linear equations is a generic and important problem…[and the authors have developed] a quantum algorithm that will solve the problem much more rapidly”.
The synopsis of the paper provided by the journal’s publisher, the APS, says that it describes “a quantum algorithm for solving a set of linear equations”, and then, to clarify, notes that the algorithm “does not find the solution to the linear equations”. (It actually does clarify, though it’s written a bit sideways.)
The paper, “Quantum algorithm for linear systems of equations” is available as a preprint [pdf]. Here’s the abstract, highlighting the part that tends to drop out of the press reports:
Quantum algorithm for linear systems of equations
Solving linear systems of equations is a common problem that arises
both on its own and as a subroutine in more complex problems: given a
matrix A and a vector b, and a vector x such that Ax = b. 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 and well-conditioned, with largest dimension N, the best classical algorithms can find x and estimate x†Mx in O(N poly log(N)) time. Here, we exhibit a quantum algorithm for this task that runs in poly(log N) time, an exponential improvement over the best classical algorithm.
If providing an input vector of size N were itself a problem of size N, of course, then an algorithm that included the input operations wouldn’t scale so well.
This observation highlights an important difference between quantum algorithms of the present kind and algorithms in the other two known classes that enable exponential speedup on interesting problems, Shor’s factoring algorithm (and its relatives) and quantum simulations of of quantum systems themselves: Those algorithms provide speedups that could bring problems down from otherwise inaccessible exponential realms (or thereabout); this one would push a tractable problem down into log-land.
Afterthought, 11 November: I suppose the reason I’m intrigued by this sort of process (subtle-but-enormous distortions creeping into descriptions) is that I’ve seen it happen in second-, third-, and fourth-hand descriptions of studies of prospective advanced nanotechnologies.
A vivid example is the simplistic equation of atomically precise fabrication (for example, by using positional constraints to localize familiar kinds of chemical reactions) with grabbing and placing individual atoms (which would typically require something more like magic). Unfortunately, in this case, subsequent discussions centered on the impossibility of magic, rather than the implementation of technology.