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.)
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
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.
