QUANTUM ALGORITHM: Quantum computers don't exist yet but they hold promise for number crunching more sophisticated than this
Image: iStockphoto
Quantum computers can do wondrous things: too bad they do not exist yet. That has not stopped physicists from devising new algorithms for the devices, which can calculate a lot faster than ordinary computers—in fact, exponentially faster, in quite a literal sense. Once quantum computers do become available, the algorithms could become a key part of applications that require number crunching, from engineering to video games.
The latest quantum algorithm is generating excitement among physicists. It tackles linear equations: expressions such as 3x + 2y = 7 and typically written with unknowns on one side and constants on the other. Many high schoolers learn the trite mechanics of solving systems of such equations by eliminating one unknown at a time. Speed becomes crucial when systems contain billions of variables and billions of equations, which are not unusual in modern applications such as simulations of weather and other physical phenomena. Efficient algorithms can solve large, “N by N” systems (systems having N linear equations and N unknowns) by computer. Still, calculation time grows at least as fast as N does: if N gets 1,000 times larger, the problem will take at least 1,000 times longer to solve, often more.
The quantum algorithm now proposed by Aram W. Harrow of the University of Bristol in England and Avinatan Hassidim and Seth Lloyd of the Massachusetts Institute of Technology takes a clever shortcut. It can return the most relevant information about the solution without fully calculating the solution itself, thus trading off the amount of data it produces for speed. (For example, in the case of weather prediction it could return the average temperature over a town rather than the temperatures predicted city block by city block.)
Like all quantum algorithms, their method, described in the October 9 Physical Review Letters, encodes all the relevant information about the system into quantum bits. Contrary to ordinary, or “classical,” bits, quantum bits can exist both as 0 and 1 simultaneously—or, as physicists say, in a superposition of states. The algorithm transforms the bits into a state that essentially encodes a superposition of all possible solutions of the system, meaning for all possible values of the constants on the right hand sides of the equations. From this “universal solution,” one can then extract the relevant information about particular solutions without calculating them fully.
The gain in speed is enormous: the time required to produce the universal solution grows only with the number of digits in N. Thus, if N gets 1,000 times larger, the algorithm takes three times as long (because three digits are added to N), as opposed to 1,000 times as long. Even writing down the result for all the variables would involve 1,000 times more steps in the classical case. “It takes exponentially less time to solve the problem than to read the solution,” Lloyd says only half-jokingly.
“Every single quantum algorithm that shows a clear speedup when compared with its classical analogue is still a big deal,” says Artur Ekert of the National University of Singapore. Only a handful of quantum algorithms can boast that achievement—such as those invented in the 1990s for factoring large numbers into primes or for searching databases.
So far only experimental quantum computers exist, containing only a few bits. But a small demonstration of the new algorithm should be feasible in the not too distant future, says Martin Plenio of the University of Ulm in Germany. “It will be many years, though, before a quantum computer of a sufficient size can be built to solve a problem that cannot be attacked on classical devices,” he adds.
Some applications could be possible sooner, Lloyd says, if they exploit the intrinsically quantum nature of photons. He proposes, for example, that the algorithm could be embodied in a “superimaging device” that would remove optical distortions in a telescope. Each photon measured by the telescope would play the role of the constant terms of the equation, and the distortions would correspond to a linear system of equations. Finding the solutions would mean reversing the distortions, thus improving image quality.
This article was originally published with the title Warp-Speed Algebra.
Already a Digital subscriber? Sign-in Now
If your institution has site license access, enter here.
See what we're tweeting about
15 Comments
Add CommentCastelvecchi writes, "...the time required to produce the universal solution grows only with the number of digits in N. Thus, if N gets 1,000 times larger, the algorithm takes three times as long (because three digits are added to N), as opposed to 1,000 times as long."
Reply | Report Abuse | Link to thisDoesn't this imply that nature uses a base 10 system? If natural logarithms were involved the calculation should take about 6.9 times as long and if it is based on powers of 2, about 10 times as long. Why would the number of (base 10) digits matter?
I agree with you but I think they were trying to simplify their case here. I am certain that they are refering to binary digits and not decimal ones.
Reply | Report Abuse | Link to thisI agree with Cosmo...I'm still waiting for any quantum computation to occur that can be reproduced...until then it's just conjecture.
Reply | Report Abuse | Link to thisI propose a task for this mighty computer/algorithm combination. Task it to work out the quantum states for whole molecules, such as amino acids,nucleic acids, and other common molecules that make up life.
Reply | Report Abuse | Link to thisThen work out the equations for ever more complex molecules that those basic molecules combine to form, such as RNA, DNA, and proteins, lipids, sugars, and so on.
Then, by reverse engineering starting from a quantum solution as to what the first (simplest) self-reproducing cell must have been like, figure out just how the first living cell came about.
I specify a cell because I just don't see a self-replicating RNA crystal as morphing somehow to produce us--clearly an egg before the chicken approach. I specified "simplest" because if an extremely complex assemblage of molecules had to come together "just so" that is clearly into the realm of creationism.
John von Neuman proved that at a minimum something like 250,000 molecules would be necessary for self-reproduction. If those molecules (once identified) in toto generate a quantum description that is mathematically interesting in itself, then truly we would discover the formula for life inherent in the chemistry of the universe. The quantum computer may be able to tease out something like a unique harmonic that generates first life.
It is worse than that. If adding N digits makes the calculation take N times longer, why not add 1 digit 3 times. Then the 1000x more complex problem would take only 1x1x1 times longer....
Reply | Report Abuse | Link to thisSomeone has mixed up his logarithm basics here.
Rob,
Reply | Report Abuse | Link to thisNo, silly - adding one digit doesn't get you a number with the same number of digits. It gets you a number with one more digit. 1 + 1 = 2, not 1.
Algorithms for a computer that doesn't exist?
Reply | Report Abuse | Link to this"I got no car and it's breaking my heart...
But I've found a driver and that's a start"
This may be useful, or not, but for most complex systems, like weather forecasting, much if not most of the time required for processing is spent retrieving vast amounts of data rather than actually calculating, so I wouldn’t get too excited over this seemingly dubious calculation strategy.
Reply | Report Abuse | Link to thisAnyway, I’ve heard a TV weather person go to great pains to explain that a 30% chance of rain meant that 30% of viewers would get rained on. All we need is another level of uncertainty in the meaning of our results.
I imagine it's really the normal course of things to come up with a use for an invention before it's invented. Otherwise, why invent it?
Reply | Report Abuse | Link to thisI believe it is revolutionary, Though we know so much the action on the items still is very meagre. I am talking about the global warming , we we can predict temperature variations so closely we can also stop global warming right!
Reply | Report Abuse | Link to thisOk this is a silly question, but are there places that let you rent/use super computers for personal research? If not "super" computers, at least really fast ones/high memory/etc?
Reply | Report Abuse | Link to thisThe problem is not with the speed of calculation but the method of calculus in its tends to approach of approximation.Basic science require more refined calculus and we have to work on it. String theory is very promising considering each string is nothing but each gravitoethertons or god particle or ether as explained in my balloon inside balloon theory and theory of gravitoethertons in Doc.6198. Now considering six dimensions as top-bottom, left-right and forward-backward , we ma y derive string theory because I feel cartesian plus minus ideas of three dimension and time as dimension as described by Einstein is wrong. Do not combine space with time. Space is dark energy flow of gravitoethertons as such it is expanding our balloon universe of matter. But what is equal opposite reaction --that is your gravity effect. so planck length is nothing but gravitoethertons diameter and six quarks are six dimensional symphony of six dimensional string theory. I would suggest to apply new methods of algorithm combination to our present super computers to develop a better string theory.
Reply | Report Abuse | Link to thisCorrection: The article is listed as October 7th Physical Reveiw Letter.
Reply | Report Abuse | Link to thisAccording to quantum physics, it is impossible to observe the state of a quantum system without modifying it. Therefore can someone please explain how you can read qu-bits without affecting the calculations you are trying to determine?
Reply | Report Abuse | Link to thisPartial Differential equations were believed to be the most usless kind of mathematics - until used by Einstein for Theory of Relativity. So sometimes developments in mathematics does precede actual use !!!
Reply | Report Abuse | Link to this