Sampling ability broadens quantum computing
By Eric Smalley, Technology Research NewsThough quantum computers are not likely to emerge from the laboratory for a long time, the range of problems they will eventually be able to tackle is steadily expanding. Bell Labs last month announced an algorithm that will allow quantum computers to do sampling computations, expanding their potential capabilities beyond factorization and searching.
The sampling algorithm, written by Bell Labs' researcher Lov K. Grover, enables three types of applications for quantum computing: statistical sampling, searching with sketchy information and Monte Carlo integration, which is a technique for approximating the answers to scientific problems that are too difficult to solve.
Although only simple prototypes have been built to date, quantum computers have proven to be blazingly fast. Quantum computers solve problems almost instantly because they process every possible answer simultaneously. The difficulty is in extracting the answer. At the heart of each quantum algorithm is a series of quantum mechanical operations that ensure that when the system is measured, and thus taken out of its quantum state, the answer is preserved.
Quantum computers are so fast because there are far fewer quantum mechanical operations in a quantum algorithm than steps in a comparable classical algorithm. If an algorithm on a classical computer takes 100 steps to solve a problem, a comparable quantum algorithm would take the square root of 100, or 10, steps. The advantage increases as the problem gets more complicated: only the most powerful supercomputers running for weeks can crack the Data Encryption Standard because it takes about 1018 steps. The square root of 1018 is one billion. Some of today's desktop computers can process one billion steps in one second.
Grover's quantum sampling algorithm is similar to classical algorithms that use sampling but takes advantage of the quantum speed-up. "The difference is that usually the classical problem is so complicated that no one bothers to solve it as it is," Grover said.
Grover’s algorithm allows searches through large numbers of possibilities using queries that can yield more than one right answer. In these searches, the queries use multiple terms which can be weighted according to probabilities. For example, you would be able to search through a city telephone directory using information like first name and neighborhood if you were unsure of the last name of the person you were looking for. You would select possible last names and give them probabilities and the algorithm would return the closest matches based on all the information, Grover said.
The sampling algorithm is an extension of a quantum search algorithm Grover devised in 1996. That algorithm was a major breakthrough in the fledgling field of quantum computing because it gave the theoretical devices some of the capabilities of today's classical computers. The sampling algorithm could yield an even broader range of applications for quantum computers, Grover said.
Although the sampling algorithm is probably not as "novel and exciting" as Grover's original search algorithm, no one doubts the importance of sampling on quantum computers, said Daniel Lidar, a physicist researching quantum computing at the University of California at Berkeley. Lidar co-authored a paper that extended Grover's original search algorithm to support random distributions, which in turn was a precursor to Grover's sampling algorithm.
Quantum computers, and thus the sampling algorithm, are not likely to be commercially available for more than two decades, according to Grover. Funding for the project was supplied by the National Security Agency and the U.S. Army Research Office.
Timeline: >20 years
Funding: Government
TRN Categories: Quantum Computing; Data Structures and Algorithms
Story Type: News
Related Elements: Technical paper in Computing Research Repository
Advertisements:
June 28/July 5, 2000
Page One
Cortex chip goes both ways
Sampling ability broadens quantum computing
Nano-scale plotter goes parallel
NASA grasps intricacies of human hand
Algorithm evolves more efficient engine
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
