A new algorithm may give quantum computers a new, practical job: quickly solving monster linear equations. Such problems are at the heart of complex processes such as image and video processing, genetic analyses and even Internet traffic control. The new work, published October 7 in Physical Review Letters, may dramatically expand the range of potential uses for quantum computers.
The new quantum algorithm is “head-smackingly good,” says computer scientist Daniel Spielman of Yale University. “It is both very powerful, and very natural. I read the abstract and said, ‘Why didn’t I think of that?’”
In the new study, Aram Harrow of the University of Bristol in England along with Avinatan Hassidim and Seth Lloyd, both of MIT, propose that large datasets of linear equations could be encoded in quantum forms, such as the spins of nuclei, individual atoms or photons. Such a system would allow quantum computers to handily solve problems made up of billions or even trillions of variables (such as the x’s, y’s and z’s that plague algebra students).
“Solving these gigantic equations is a really huge problem,” Lloyd says. “Even though there are good algorithms for doing it, it still takes a very long time.”
A trillion-variable problem would take a classical computer at least a hundred trillion steps to solve, Lloyd says. But with the newly proposed algorithm, a quantum computer could solve the problem in just a few hundred steps, the researchers calculate.
Strange quantum mechanical principles that operate on very small scales give quantum computers their immense number-crunching power. One of the strangest physical properties, called superposition, allows a single quantum bit of information to represent both a 0 and 1 at the same time, while a classical bit can only represent either a 0 or a 1. Performing a mathematical operation on a single quantum bit, or qubit, is like doing many operations simultaneously, says Lloyd. “You don’t have to read all the data individually — you can read aspects of them all at once,” he says.
Lloyd and his colleagues plan to test the algorithm in the lab by having a quantum computer solve a set of linear equations with four variables. After that, Lloyd says he plans to look around for “more fun problems to solve.”
Spielman says that this newly proposed algorithm is exciting because it hints that quantum computers may have many more hidden talents. “It’s given me a lot of hope for quantum computing,” he says.
