Solving big problems with new quantum algorithm

Nov 09, 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: A quantum logic gate between light and matter

add to favorites email to friend print save as pdf

Related Stories

Quantum computing may actually be useful, after all

Oct 09, 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 ...

Quantum computer solves problem, without running

Feb 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 ...

Quantum Computer Science on the Internet

Jul 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 o ...

Taking Computers to the Quantum Level

May 09, 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 ...

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 import ...

Recommended for you

CERN: World-record current in a superconductor

22 hours ago

In the framework of the High-Luminosity LHC project, experts from the CERN Superconductors team recently obtained a world-record current of 20 kA at 24 K in an electrical transmission line consisting of two ...

High power laser sources at exotic wavelengths

Apr 14, 2014

High power laser sources at exotic wavelengths may be a step closer as researchers in China report a fibre optic parametric oscillator with record breaking efficiency. The research team believe this could ...

Novel technique opens door to better solar cells

Apr 14, 2014

A team of scientists, led by Assistant Professor Andrivo Rusydi from the Department of Physics at the National University of Singapore's (NUS) Faculty of Science, has successfully developed a technique to ...

User comments : 0

More news stories

CERN: World-record current in a superconductor

In the framework of the High-Luminosity LHC project, experts from the CERN Superconductors team recently obtained a world-record current of 20 kA at 24 K in an electrical transmission line consisting of two ...

Glasses strong as steel: A fast way to find the best

Scientists at Yale University have devised a dramatically faster way of identifying and characterizing complex alloys known as bulk metallic glasses (BMGs), a versatile type of pliable glass that's stronger than steel.

ESO image: A study in scarlet

This new image from ESO's La Silla Observatory in Chile reveals a cloud of hydrogen called Gum 41. In the middle of this little-known nebula, brilliant hot young stars are giving off energetic radiation that ...

First direct observations of excitons in motion achieved

A quasiparticle called an exciton—responsible for the transfer of energy within devices such as solar cells, LEDs, and semiconductor circuits—has been understood theoretically for decades. But exciton movement within ...

Patent talk: Google sharpens contact lens vision

(Phys.org) —A report from Patent Bolt brings us one step closer to what Google may have in mind in developing smart contact lenses. According to the discussion Google is interested in the concept of contact ...

Warm US West, cold East: A 4,000-year pattern

Last winter's curvy jet stream pattern brought mild temperatures to western North America and harsh cold to the East. A University of Utah-led study shows that pattern became more pronounced 4,000 years ago, ...