Quantum
software gets the picture
By
Eric Smalley,
Technology Research NewsWhen you look at a tile floor, you may think about how well the pattern goes with the rest of the room, but you won't wonder whether there is a pattern there in the first place.
A computer, on the other hand, would have a hard time simply figuring out that a black tile followed by a white tile followed by a black tile followed by a white tile constitutes a pattern.
It is clear that quantum computers, which use the quirks of quantum physics to compute, will be orders of magnitude more efficient at many tasks than ordinary, classical computers, if and when sufficiently large quantum computers can be built.
A physicist at the University of British Columbia has come up with an algorithm that proves that quantum computers would be faster at finding patterns, too. "Finding and recognizing [a linear] pattern can be accomplished much faster on a quantum computer than on a classical one," said Ralf Schützhold, a researcher at the University of British Columbia.
The algorithm would allow quantum computers to detect an 8-by-8 grid of alternating black and white squares set in an array of 640 otherwise randomly distributed squares.
This seemingly simple task takes a classical computer about 6,000 steps because it would have to compare each square to every other square, one at a time.
A quantum computer, however, can examine all of the possible solutions to a problem at the same time, in this case comparing all the squares to each other at once. The algorithm proves that this particular task can be represented mathematically in a way that a quantum computer can carry it out.
Quantum computers can check all solutions at once because they use atoms or subatomic particles to make quantum bits, or qubits. The particles have two opposite orientations that can represent the 1s and 0s of computer information.
The power of a quantum computer comes from the quirky physics of these tiny particles. When a particle is isolated from its environment it is in the weird quantum state of superposition, meaning it is in both orientations at once, and so can represent a mix of 1 and 0. This allows a string of particles in superposition to represent every combination of 1s and 0s at the same time, and a quantum computer to process all the numbers that represent possible solutions to a problem with one set of operations.
The pattern-finding algorithm is an addition to a growing set of quantum algorithms based on the quantum Fourier transform, a mathematical formula for finding order.
Other researchers have demonstrated that quantum computers would be exponentially faster than classical computers for pattern-matching tasks like finding a mug shot in a database that matches an image from a security camera. Schützhold's pattern-finding algorithm performs the first task of a pattern recognition application: finding patterns in raw data.
Pattern finding is a key component of speech, face, and handwriting recognition programs, and of software that sorts seismographs and other large sets of scientific data, said Schützhold. The exponential speed-up promised by quantum computers might enable us to attack problems that would take classical computers "longer than the age of the universe" to solve, he said.
This particular algorithm is not likely to be used in practical applications, however. "The problem I discussed is very simple and probably not extremely important or relevant for practical applications," said Schützhold. "My main point is to demonstrate the possible exponential speed-up," he said.
The pattern-finding algorithm is also not a particularly efficient quantum algorithm, said David Meyer, a mathematics professor at the University of California at San Diego. But it is important for demonstrating that quantum computers could be used to speed up image processing tasks, he said. "There are probably other image processing problems for which quantum algorithms will be more successful," he added.
Researchers generally agree that it is likely to take at least two decades to develop practical quantum computers. Quantum computing research is now at a stage comparable to when electrical engineers began to build and combine small numbers of transistors half a century ago, said Schützhold.
Transistors are electrical switches that combine to form the basic logic circuits of computers. Today's PCs have about one billion transistors. Useful quantum computers will require at least one million qubits, the quantum equivalent of transistors. The largest prototype quantum computer built so far had seven qubits.
The research was funded by the Alexander von Humboldt Foundation in Germany and the Natural Sciences and Engineering Research Council of Canada (NSERC).
Timeline: > 20 years
Funding: Private, Government
TRN Categories: Data Structures and Algorithms; Quantum Computing and Communications
Story Type: News
Related Elements: Technical paper, "Pattern recognition on a quantum computer," posted on the arXive physics archive at http://arXiv.org/abs/quant-ph/0208063
Advertisements:
September 4/11, 2002, 2002
Page One
Chip juggles droplets
Software turns reading into writing
Radio ID locks lost laptops
Quantum software gets the picture
Laser blasts make memory
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.
