Not quite the same
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.
See also:
{ 15 comments… read them below or add one }
From the MIT News Office article:
Because the result of the calculation would be stored on qubits, however, “you’re not going to have the full functionality of an algorithm that just solves everything and writes it all out,” Lloyd says. To see why, consider the way in which each added qubit doubles the capacity of quantum memory. Eight qubits can represent 256 values simultaneously, nine qubits 512 values, and so on. This doubling rapidly yields astronomical numbers. The trillion solutions to a trillion-variable problem would be stored on only about 40 qubits. But extracting all trillion solutions from the qubits would take a trillion steps, eating up all the time that the quantum algorithm saved.
With qubits, however, “you can make any measurement you like,” Lloyd says. “You can figure out, for instance, their average value. You can say, okay, what fraction of them is bigger than 433?” Such measurements take little time but may still provide useful information. They could, Lloyd says, answer questions like, “In this very complicated ecosystem with, like, 10 to the 12th different species, one of which is humans, in the steady state for this particular model, do humans exist? That’s the kind of question where a classical algorithm can’t even provide anything.”
@ Larry — Yes, is important to note that the MIT article, like the APS synopsis, states the limitation after headlining the simple-but-wrong description. I’ve updated the post to state and credit your observation.
BTW, aside from adding a bit to the existing mass of confusion regarding the capabilities of quantum computing, I expect this particular distortion to be mostly harmless. The innocent origin of the distortion — progressive simplification from correct to wrong — is part of a common syndrome.
“I expect this particular distortion to be mostly harmless.”
Actually, such tactics are quite harmful, and quite premeditated. Many of the popular articles spun from this one will forget to mention this *substantial* limitation. Grants will be awarded (either subconsciously or not) based on publicity more than merit. Of course, the scientists involved can blame the MIT press office. But why didn’t they proof read the MIT press release.
Feynman on Honesty
The press release by the Univ. Of Bristol, which has been widely repeated, never mentions the limitation
Thanks for the followup. The Bristol press release is indeed a good specimen.
BTW, I agree with your assessment of harm. What leads me to see this misunderstanding as relatively harmless, however, is that it can’t add much to the vast and deep misunderstandings that are already in place.
What I have in mind is the failure to recognize that “quantum parallelism” and conventional parallelism are quite different, and that very few known quantum algorithms allow exponential speedup. Instead, there is the pervasive and grossly misleading idea that a machine using N-qubit representations would somehow deliver the power of 2N general-purpose machines.
Also, unless I am quite mistaken, algorithms of this class (continuous-variable quantum algorithms) are not digital. The internal representation of a quantity is as an analog variable, a phase and amplitude associated with one component of a vector of 2N superposed multi-qubit states. The sequence of 1s and 0s that defines a multi-qubit state should be thought of as the index — not the value — of a vector component. The value of a vector-component quantity is therefore neither a digitally encoded number nor a superposition of them. (Shor’s factorization algorithm and Grover’s search algorithm are of a different kind: Each of them designates a single value from a discrete, finite set.) [Paragraph revised for clarity, 16 Nov.]
It should also be noted that, when the output is a single-qubit quantum state variable, the result “y = 0.63937” would take the form of a 0.63937 probability that the output of a single computation will be measured as “1”, rather than “0”. Inferring the result with an expected error of 10–n would require on the order of 102n cycles of computation and measurement. This form of output should not be confused with floating point! [The phase-estimation algorithm, however, can be used to output an internal value, represented as a phase, as a binary encoding of that value (note added 17 May 10)]
Yes, “quantum parallelism” is different and “weaker” than classical parallelism.
As for the “statistical” precision errors that can sometimes arise when using a quantum computer to approximately solve a problem, note that those types of errors also arise if you use a Monte Carlo method on a classical computer. Even though Monte Carlo methods (classical and quantum) have this con, they have many pros.
As for why university press releases that fib and exaggerate are so harmful, I would like to add that: It erodes the confidence of the public in science, so that, for example, they no longer trust scientists when these tell them that vaccines are super important and quite safe. It also confuses the public, and impairs their ability to distinguish between science and pseudoscience. I recently made friends with a quite smart painter in Spain, and I was horrified to find out that she is a great believer in homeopathy (apparently their public health care system pays for homeopathic treatments!)
Re. methods with statistical outputs — Yes, and the story also loops back on itself: “Quantum Monte Carlo” methods on classical computers are among the most accurate ways evaluate static, non-statistical properties, for example, the ground-state energy of (some) quantum systems.
Re. fibs — Yes, erosion of scientific credibility is an enormous cost, and has the characteristics of a tragedy of the commons problem, paired with a public-goods problem: Exaggeration can pay, for the exaggerator, while the cumulative costs are borne by science and society. Thus, trust is a kind of commons that is consumed by exaggerators. For the same reason, the service of combating these assaults on the fabric of trust is a public good, with general benefit but concentrated costs. It parallels the classic examples of military and police protection, structurally, though the appropriate remedies would be quite different.
BTW, it is important to keep in mind that misunderstandings — even those that benefit the ultimate information source — can result simply from mistakes in understanding, or from over-simplification on the part of the people who stand between knowledge sources and knowledge receivers.
For example, assume that the researchers in this instance consistently stated a clear and correct message (as they did, for example, in the abstract of their paper). I would still expect reports to be distorted in the way that we see. When the facts are hard to explain, and are easily misunderstood, and the misunderstanding is easily understood and it makes a better story (all true here), I tend to think less in terms of guilty parties, and more in terms of evolving ideas.
@ rrtucci — I’d be interested in your comments on how the quantum Bayesian networks you’ve described (and the recent, related research that cites yours) compare to quantum simulation of the sort that’s become a hot area recently (or on other algorithms that may be relevant).
I’d also be interested in a cross-check regarding whether the statements in my earlier comment are correct regarding the nature of what I termed “continuous-variable quantum algorithms”. I sometimes write comments with the intent of writing at least a rough-draft of tutorial content for readers, and corrections or clarifications in concepts and terminology are more than welcome.
What I call quantum Bayesian networks is a simple generalization of the definition of classical Bayesian networks to quantum mechanics. I believe that quantum Bayesian networks are a rich and useful way of looking at quantum mechanics, in the same way that classical Bayesian networks are a rich and useful way of looking at classical probability theory. (By the way, Koller-Friedman have recently published their much awaited and wonderful textbook on classical Bayesian networks). Quantum computerists can think of quantum Bayesian networks as an alternative way of drawing quantum circuits.
Besides quantum Bayesian networks and independently of them, I use my blog to advocate for the use of quantum computers to do MCMC (Markov Chain Monte Carlo)
Let me call discrete problems (continuous problems, respectively) those whose set of possible answers is the natural numbers (real numbers, resp.). I believe both quantum and classical computers can produce statistical errors in their answers for both discrete and continuous problems. (Shor’s algorithm, though it solves a discrete problem, has a finite probability of failing, but there is a high probability of success after only a small number of repetitions of the experiment.) In the case of classical computers, we don’t normally worry about statistical errors (unless it’s a Monte Carlo algorithm) because current classical computers make such errors only extremely rarely. (If you operate then in a friendly environment, that is. You must, of course, worry about statistical errors if the environment is unfriendly; for instance, if your classical computer is operating at a very high temperature, or if it’s in outer space and exposed to very high levels of cosmic radiation.) Compared with classical computers, quantum computers have to contend with an additional and hard to handle source of statistical errors, namely quantum mechanical noise. One worries less about statistical errors for discrete problems (because the discreteness tends to filter out some of the noise) than for continuous problems, and less for classical computers than for quantum ones. Hence, you are right in your intuition of singling out as the worse possible scenario for statistical errors, that of solving a continuous problem on a quantum computer.
An advantage of the Bayesian-network representation is that it doesn’t imply a full, chronological order of gate operations, unless this is also implied by causality. Thinking in terms of a formal, system-wide state vector between each pair of operations (even if these are on disjoint sets of qubits) results in multiple not-obviously-equivalent representations for a single set of causal relationships.
Hey, I think you guys talked past each other. Drexler was talking about how to read out a floating-point value from a single qubit. If I understood him correctly, you have to read it lots of times (re-doing the computation each time) and average the 0′s and 1′s. In fact, 10^2n times for 10^n precision. And this is if the system is working perfectly, noise-free!
rrtucci’s last message seems to be talking about the effects of noise on the system, saying that continuous/quantum problems are the worst in terms of noise.
Although these are both true, I think they are completely different, and it sounds like you both think you were talking about the same issue.
Chris Phoenix: For a quantum computer, a floating-point number is obtained by measuring N qubits. Say $latex x_i$ is the measurement of qubit i, and you have 3 qubits, and let $latex x=0.x_1 x_2 x_3 = x_1/2 + x_2/4 + x_3/8$ be your floating point answer. If your algorithm is a good one, the x_i come out the same most of the times you repeat the experiment, but because of quantum noise, there is a probability that they won’t come out the same. This is what I am calling the statistical error, as opposed to the floating point error, which is the error produced by rounding-off.
Thank You Dr. Drexler for highlighting the rampant practice of “distorting” the results of scientific investigations while publicizing to the layman.
To be honest, i am currently a Ph.D. in Electrical Engineering. I was inspired many such “flawed” articles in popular press and decided to pursue quantum computation when i was an undergrad. Being young and naive i thought i could come up with another exponenitally faster quantum alogrithm! In the end i came up with a much simpler result which was published at WorldComp 2009 (where you were one of the keynote speakers) and infact realized the potential limitations of QC to solve a simple image processing problem and decided to move to another field.
It is then I once again came across the “fancy” news articles about Nanoelectronics and I came to USA and spent(loaned) 35,000$ to do my MS at a Top 10 school and realized that i reached a dead-end. No one knows where the research in Nanotube,nanowire or Graphene transistors is going! Looks like the industry will be still using CMOS in the near future.After my MS in so called Nanoelectronics, i did not get even a single job offer!!
Having burnt my fingers, i moved to more traditional ECE fields like Computer Architecure, Parallel Programming and Computational Intelligence during my Ph.D. studies and doing reasonably well.
A lot of people underestimate the harm caused by such frivolous reporting of scientific research.It can seriously mislead the young and naive aspiring researchers who will be the Scientists of tomorrow.
It is very unfortunate that it has become very fashionable to use the buzzwords ‘quantum’ and ‘nano’ very indiscriminately even by some of the scientific community as a means to attract funding and attention!
I always thought Science was an objective pursuit but unfortunately human beings are creatures of emotions rather than logic!
Even though the algorithm provides only an expectation value of some operator on the solution set vector, the authors prove(via complexity-theory) that you can’t have a classical algorithm as fast as this one(or a quantum algorithm faster than this one) even if you want only a summary statistic of the solution(as provided by this algorithm).
But yes, I totally agree with the point you make about misrepresentation.
I just came across this post, somewhat after the discussion has died down. One small point I want to mention is that our arxiv post has a link to my email address, and my coauthors and I would have been happy to respond to any questions or criticisms you had about our paper.
Contrary to your claims, I think the original title is accurate. Our algorithm indeed “solves” linear systems of equations, although the answer is output in the form of the amplitudes of a quantum state, not in the form of a list of numbers. This is similar to the way in which MCMC methods find stationary distributions: they don’t output a list of numbers corresponding to a probability distribution, but they output a sample. In both cases, people may find solutions of this form unsatisfactory answers, in which case, it is possible to use these samples to estimate scalar functions of the solution.
This is made totally clear in our paper, and anyone who understands that our algorithm runs in o(N) time should understand that we’re not outputting a list of numbers: how could N numbers be output in O(log(N)) time? (As you point out, our algorithm is only interesting if the input is also created in o(N) time.) But because we wanted to avoid a potentially misleading impression, we changed the title to be more vague, so that people will only know what exactly we do with linear systems of equations by reading further into the paper.
As for the popular summaries of the article, probably they should have mentioned that there are many technical restrictions on the algorithm (related not only to the output, as you mention, but also the encoding of the input), that classical linear systems solvers are getting pretty close to linear time (and so our algorithm is only interesting with large, implicitly specified inputs), and that our algorithm relies on quantum computers which don’t exist yet. Probably the scientific press should generally be less optimistic in its tone. But your pessimism goes too far in the other direction.
If you want a better model of press coverage, this article does a really good job:
http://www.nature.com/nphys/journal/v5/n12/abs/nphys1473.html
{ 2 trackbacks }