Posted on 12/03/2005 10:46:50 PM PST by sourcery
Researchers at the University of Michigan have been able to use a small quantum computer consisting of two atoms to do a super-fast data base search. This same system could someday be scaled to a much larger quantum computer that could outperform any conventional computer for certain applications.
The super-fast search is called Grover's Quantum Search Algorithm, and it can be used to search unsorted databases for specific information. If you wanted to find a name belonging to a phone number in the phonebook, Grover's algorithm could be used to search for the corresponding name much faster than using a normal computer. For example, for a phone book with 1 million names, it would only take 1,000 "looks" to find the right match—the square root of 1 million—instead of an exhaustive search over all 1 million entries in the phone book.
The search was implemented using two atoms, each of which stores a single bit of information, for a total of four possible states. It's a system that increases exponentially, so by adding one atom the memory doubles, said Christopher Monroe, professor of physics and co-author of a paper on the topic, "Implementation of Grover's Quantum Search Algorithm in a Scalable System," appearing in the November issue of Physical Review.
"You don't have to add too many atoms before you have a huge system," he said. The research was led by graduate student Kathy-Anne Brickman in Monroe's research group at the U-M Department of Physics and the FOCUS Ultrafast Optics Center.
In this case, using the hypothetical phone book analogy, researchers used four numbers and tried to find the corresponding name. After looking only once, the algorithm was successful in finding the correct answer 60 percent of the time, better than the maximum possible success rate of 50 percent using a normal computer.
To understand how it works, think of the four states as a single wave, Monroe said. Researchers can manipulate the wave to mark any one of the four states and "look" at the system by zapping it with a specially tuned laser, which makes the atoms interact in certain ways. This involves the "entanglement" of the two atom bits, or a special linking that is only allowed in quantum systems. Einstein called entanglement "spooky action at a distance," and it is this feature of quantum physics that allows the fast search.
To test the algorithm, researchers marked one of the four states by adjusting the part of the wave corresponding to that particular state. Then, by manipulating the laser and entangling the atoms, researchers were able to make the incorrect values cancel out one another through quantum interference, leaving only the marked state.
"When we look at this four-state system, we can look at it in a way that you can't do in a regular phone book," Monroe said. "We don't want to exhaustively look at all possibilities before uncovering which one was marked. While this is obviously a very small quantum computer, the main point is that this exact system can be efficiently scaled to much larger memories."
Ping
me
(Voice of Homer Simpson) - "Take that Google!"
Whom are we calling, exactly?
Yes but can it find Schrodinger's Cat ?
Both yes and no.
Sounds like the Bubble sort algorithm I learned in college
Grover's Quantum Search Algorithm does not rely on sorting. It enables searching through unsorted data as quickly as though the data had been sorted--which matters because there are many situations where sorting the data is not possible, is prohibitively expensive, or conflicts with other requirements (e.g., when there is more than one data field in each record by which the data set could be sorted and/or searched.)
And here I thought Grover was just a funny character on Sesame Street.
Nope, these are unsorted databases. I, too, did a lot of experiments with bubble sorts, spanning-tree sorts, etc. back in college.
I did come up with a similar idea 30 years ago, should have patented it! But having no access to an electron microscope and other tools, I elected to instead experiment with drinking beers.
I wish I had this for my PC :)
Absolutely. The cat is always where it is supposed to be, but whether or not it is alive.... that is the question.
Did you get them sorted?
He's not just funny. He's cute, too. :)
Pinging...
...thought you might be interested if you're still reading this board.
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.
