Solving big problems with new quantum algorithm

November 9, 2009,
Solving big problems

(PhysOrg.com) -- In a recently published paper, Aram Harrow at the University of Bristol and colleagues from MIT in the United States have discovered a quantum algorithm that solves large problems much faster than conventional computers can.

One of the most basic problems in maths is solving very large linear equations. There's nothing mysterious about them, they simply take time and the more variables there are, the longer it takes. Even a supercomputer would struggle to solve a system of equations that has a trillion variables.

However, in a new paper recently published in , Aram Harrow at the University of Bristol and colleagues from MIT in the United States have discovered a quantum algorithm that solves the problem much faster than conventional computers can. And the larger the problem, the greater the speedup.

To understand how the quantum algorithm works, think of a digital equaliser in a stereo CD player. The equaliser needs to amplify some components of the signal and attenuate others. Ordinary equalisers employ classical computer algorithms that treat each component of the sound one at a time.

By contrast, a quantum equaliser could employ a quantum algorithm that treats all components together at once (a trick called 'quantum parallelism'). The result is a huge reduction in the difficulty of signal processing.

“Large-scale linear systems of equations exist in many fields, such as weather prediction, engineering, and computer vision”, says Harrow. “Quantum computers could supply serious improvements for these and many other problems. For example, a trillion-variable problem would take a classical computer at least a hundred trillion steps to solve, but using the new algorithm, a quantum computer could solve the problem in just a few hundred steps”.

The solution could also be applied to other complex processes such as image and video processing, genetic analyses and even Internet traffic control.

More information: Quantum Algorithm for Linear Systems of Equations, Phys. Rev. Lett. 103, 150502 (2009), DOI:10.1103/PhysRevLett.103.150502

Provided by University of Bristol (news : web)

Explore further: Quantum computing may actually be useful, after all

Related Stories

Quantum computing may actually be useful, after all

October 9, 2009

(PhysOrg.com) -- In recent years, quantum computers have lost some of their luster. In the 1990s, it seemed that they might be able to solve a class of difficult but common problems — the so-called NP-complete problems ...

Quantum computer solves problem, without running

February 22, 2006

By combining quantum computation and quantum interrogation, scientists at the University of Illinois at Urbana-Champaign have found an exotic way of determining an answer to an algorithm – without ever running the algorithm.

Quantum Computer Science on the Internet

July 31, 2004

A simulated quantum computer went online on the Internet last month. With the ability to control 31 quantum bits, it is the most powerful of its type in the world. Software engineers can use it to test algorithms that might ...

Taking Computers to the Quantum Level

May 9, 2006

“If Moore’s Law holds for another 10-15 years,” says Dr. Raymond Laflamme, “we’ll have transistors the size of atoms.” Laflamme is a physicist at the University of Waterloo in Ontario, Canada. He is part of a ...

Ion trap quantum computing

May 12, 2009

(PhysOrg.com) -- “Right now, classical computers are faster than quantum computers,” René Stock tells PhysOrg.com. “The goal of quantum computing is to eventually speed up the time scale of solving certain important ...

Recommended for you

Walking crystals may lead to new field of crystal robotics

February 23, 2018

Researchers have demonstrated that tiny micrometer-sized crystals—just barely visible to the human eye—can "walk" inchworm-style across the slide of a microscope. Other crystals are capable of different modes of locomotion ...

Researchers turn light upside down

February 23, 2018

Researchers from CIC nanoGUNE (San Sebastian, Spain) and collaborators have reported in Science the development of a so-called hyperbolic metasurface on which light propagates with completely reshaped wafefronts. This scientific ...

Seeing nanoscale details in mammalian cells

February 23, 2018

In 2014, W. E. Moerner, the Harry S. Mosher Professor of Chemistry at Stanford University, won the Nobel Prize in chemistry for co-developing a way of imaging shapes inside cells at very high resolution, called super-resolution ...

Recurrences in an isolated quantum many-body system

February 23, 2018

It is one of the most astonishing results of physics—when a complex system is left alone, it will return to its initial state with almost perfect precision. Gas particles, for example, chaotically swirling around in a container, ...

Hauling antiprotons around in a van

February 22, 2018

A team of researchers working on the antiProton Unstable Matter Annihilation (PUMA) project near CERN's particle laboratory, according to a report in Nature, plans to capture a billion antiprotons, put them in a shipping ...

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.