Super-fast quantum search achieved with individual atoms

December 2, 2005
An abstraction of two cadmium ions entangled

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.

Image: An abstraction of two cadmium ions entangled. The bright yellow balls are the ions (painted in cadmium yellow), and all the fun stuff in between depicts the "spooky action-at-a-distance" that is responsible for the power behind quantum computing. Painting by former U-M post doc Boris Blinov.

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

For more information on Monroe's group, visit: monroelab2.physics.lsa.umich.edu/

Source: University of Michigan

Explore further: New 'building material' points toward quantum computers

Related Stories

New 'building material' points toward quantum computers

September 28, 2017

A Danish-American research team has shown that it is possible to produce Majorana particles in a new building material. The research, led by scientists from Niels Bohr institute, University of Copenhagen, paves the road for ...

JILA spinning method confirms the electron still seems round

October 10, 2017

JILA physicists have for the first time used their spinning molecules technique to measure the "roundness" of the electron, confirming the leading results from another group and suggesting that more precise assessments are ...

Artificial intelligence for obtaining chemical fingerprints

September 26, 2017

Researchers at the Universities of Vienna and Göttingen have succeeded in developing a method for predicting molecular infrared spectra based on artificial intelligence. These chemical "fingerprints" could only be simulated ...

Quantum machine learning

September 14, 2017

Language acquisition in young children is apparently connected with their ability to detect patterns. In their learning process, they search for patterns in the data set that help them identify and optimize grammar structures ...

Recommended for you

Mountain glaciers shrinking across the West

October 22, 2017

Until recently, glaciers in the United States have been measured in two ways: placing stakes in the snow, as federal scientists have done each year since 1957 at South Cascade Glacier in Washington state; or tracking glacier ...

When words, structured data are placed on single canvas

October 22, 2017

If "ugh" is your favorite word to describe entering, amending and correcting data on the rows and columns on spreadsheets you are not alone. Coda, a new name in the document business, feels it's time for a change. This is ...

Dawn mission extended at Ceres

October 20, 2017

NASA has authorized a second extension of the Dawn mission at Ceres, the largest object in the asteroid belt between Mars and Jupiter. During this extension, the spacecraft will descend to lower altitudes than ever before ...

Metacognition training boosts gen chem exam scores

October 20, 2017

It's a lesson in scholastic humility: You waltz into an exam, confident that you've got a good enough grip on the class material to swing an 80 percent or so, maybe a 90 if some of the questions go your way.

Carbon coating gives biochar its garden-greening power

October 20, 2017

For more than 100 years, biochar, a carbon-rich, charcoal-like substance made from oxygen-deprived plant or other organic matter, has both delighted and puzzled scientists. As a soil additive, biochar can store carbon and ...

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.