software gets the picture
Technology Research News
When 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
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
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
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
4/11, 2002, 2002
Chip juggles droplets
reading into writing
Radio ID locks lost laptops
gets the picture
Laser blasts make memory
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link