Physicists take first step towards super-fast search algorithms for quantum computers

Jul 09, 2009

When you toss a coin, you either get heads or tails. By contrast, things are not so definite at the microcosmic level. An atomic 'coin' can display a superposition of heads and tails when it has been thrown. However, this only happens if you do not look at the coin. If you do, it decides in favour of one of the two states. If you leave the decision where a quantum particle should go to a coin like this, you get unusual effects. For the first time, physicists at the University of Bonn have demonstrated these effects in an experiment with caesium. Their research will be published in the next issue of the scientific journal Science.

Let's assume we carried out the following experiment: we put a coin in the hand of a test person. We'll simply call this person Hans. Hans's task is now to toss the coin several times. Whenever the coin turns up 'heads', his task is to take a step to the right. By contrast, if it turns up 'tails', he takes a step to the left. After 10 throws we look where Hans is standing. Probably he won't have moved too far from his initial position, as 'heads' and 'tails' turn up more or less equally often. In order to walk 10 paces to the right, Hans would have to get 10 'heads' successively. And that tends not happen that often.

Now, we assume that Hans is a very patient person. He is so patient that he does this experiment 1000 times successively. After each go, we record his position. When at the end we display this result as a graph, we get a typical bell curve. Hans very often ends up somewhere close to his starting positions after 10 throws. By contrast, we seldom find him far to the left or right.

The experiment is called a 'random walk'. The phenomenon can be found in many areas of modern science, e.g. as Brownian motion. In the world of , there is an analogy with intriguing new properties, the 'quantum walk'. Up to now, this was a more or less a theoretical construct, but physicists at the University of Bonn have now actually carried out this kind of 'quantum walk'.

A single caesium atom held in a kind of tweezers composed of laser beams served as a random walker and coin at the same time. Atoms can adopt different quantum mechanical states, similar to head and tails of a coin facing upwards. Yet at the microcosmic level everything is a little more complicated. This is because quantum particles can exist in a superposition of different states. Basically, in that case 'a bit of heads' and 'a bit of tails' are facing upwards. Physicists also call this superposition.

Using two conveyor belts made of laser beams, the Bonn physicists pulled their caesium atom in two opposite directions, the 'heads' part to the right, the 'tails' part to the left. 'This way we were able to move both states apart by fractions of a thousandth of a millimetre,' Dr. Artur Widera from the Bonn Institute of Applied Physics explains. After that, the scientists 'threw the dice once more' and put each of both components into a superposition of heads and tails again.

After several steps of this 'quantum walk' a caesium atom like this that has been stretched apart is basically everywhere. Only when you measure its position does it 'decide' at which position of the 'catwalk' it wants to turn up. The probability of its position is predominantly determined by a second effect of quantum mechanics. This is due to two parts of the atom being able to reinforce themselves or annihilate themselves. As in the case of light physicists call this interference.

As in the example of Hans the coin thrower, you can now carry out this 'quantum walk' many times. You then also get a curve which reflects the atom's probability of presence. And that is precisely what the physicists from Bonn measured. 'Our curve is clearly different from the results obtained in classical random walks. It does not have its maximum at the centre, but at the edges,' Artur Widera's colleague Michal Karski points out. 'This is exactly what we expect from theoretical considerations and what makes the quantum walk so attractive for applications.' For comparison the scientists destroyed the quantum mechanical after every single 'throw of the coin'. Then the 'quantum walk' becomes a 'random walk', and the caesium atom behaves like Hans. 'And that is exactly the effect we see,' Michal Karski says.

Professor Dieter Meschede's group has been working on the development of so-called quantum computers now for many years. With the 'quantum walk' the team has now achieved a further seminal step on this path. 'With the effect we have demonstrated, entirely new algorithms can be implemented,' Artur Widera explains. Search processes are one example. Today, if you want to trace a single one in a row of zeros, you have to check all the digits individually. The time taken therefore increases linearly with the number of digits. By contrast, using the 'quantum walk' algorithm the random walker can search in many different places simultaneously. The search for the proverbial needle in a haystack would thus be greatly speeded up.

Source: University of Bonn (news : web)

Related Stories

Quantum Computer: Laser tweezers sort atoms

Jul 12, 2006

Physicists of the University of Bonn have taken one more important hurdle on the path to what is known as a quantum computer: by using 'laser tweezers' they have succeeded in sorting up to seven atoms and lining ...

Physicists perform the first ever quantum calculation

Dec 11, 2007

University of Queensland researchers are part of an international team to have made the first ever execution of a quantum calculation, a major step towards building the first quantum computers.

Next step to the quantum computer

Oct 06, 2004

Physicists at the University of Bonn build quantum data memory Physicists from the University of Bonn have succeeded in taking a decisive step forward towards processing quantum information with neutral atoms: in the la ...

Physicists establish 'spooky' quantum communication

Sep 05, 2007

Physicists at the University of Michigan have coaxed two separate atoms to communicate with a sort of quantum intuition that Albert Einstein called "spooky."

Yale scientists bring quantum optics to a microchip

Sep 08, 2004

A report in the journal Nature describes the first experiment in which a single photon is coherently coupled to a single superconducting qubit (quantum bit or "artificial atom"). This represents a new paradigm in which ...

Quantum Mechanical Con Game

May 05, 2008

For the first time, physicists have come up with a scheme that would allow a quantum mechanical expert to win every time in a con game with a victim who only knows about classical physics. Prior quantum cons have typically ...

Recommended for you

Physicists design quantum switches which can be activated by single photons

Apr 18, 2014

Harvard researchers have succeeded in creating quantum switches that can be turned on and off using a single photon, a technological achievement that could pave the way for the creation of highly secure quantum networks. ...

'Dressed' laser aimed at clouds may be key to inducing rain, lightning

Apr 18, 2014

The adage "Everyone complains about the weather but nobody does anything about it," may one day be obsolete if researchers at the University of Central Florida's College of Optics & Photonics and the University ...

Higher-order nonlinear optical processes observed using the SACLA X-ray free-electron laser

Apr 18, 2014

X-rays are used extensively for medical imaging and airport security, as well as for examining the atomic-scale crystallographic structure of materials. Until recently, the high-energy x-rays needed to probe ...

Could 'Jedi Putter' be the force golfers need?

Apr 18, 2014

Putting is arguably the most important skill in golf; in fact, it's been described as a game within a game. Now a team of Rice engineering students has devised a training putter that offers golfers audio, ...

Technologies for the optical characterization of materials at terahertz frequencies

Apr 18, 2014

The noncontact measurement of material properties using light is used in a wide variety of applications, from airport security scanners to medical x-ray imaging and various analytical techniques. Some of ...

Impurity size affects performance of emerging superconductive material

Apr 18, 2014

Research from North Carolina State University finds that impurities can hurt performance – or possibly provide benefits – in a key superconductive material that is expected to find use in a host of applications, ...

ciantic
not rated yet Jul 09, 2009
Huh? Is the measurement of this quantum walk step done after *each* step, or after several steps?

What does this "For comparison the scientists destroyed the quantum mechanical superposition after every single 'throw of the coin'. Then the 'quantum walk' becomes a 'random walk', and the caesium atom behaves like Hans." mean exactly?

My interpretation was this: "For comparsion the scientists measured the value after each step.", which lead me to think how did they do the `other` walk? If so, then my conclusion for the quantum walk that leads to the "maximum at the edges" is following: "They measure the value after *several* steps."

Is that right?
PPihkala
5 / 5 (1) Jul 09, 2009
"They measure the value after *several* steps."

Is that right?

I think that is so. I understand it so that by doing several steps after each other, without looking what the result is, they kind of get the superpositioned atom to spread into two parts, the left going and the right going one. And then the atom only 'decides' when looked where to stand. Now because it was previously ran into two parts that were ran into borders, it's going to be more probable that you will find it standing at the edges, at either one.
SmartK8
not rated yet Jul 10, 2009
It's interesting as well as mind boggling. This article seems to implicate that when a dice is thrown, and the results are not measured (which cannot itself be achieved, thus the experiment with a cesium atom), it behaves as a "quantum walk". So the measurement forces it to behave according to the Bell's curve ("random walk"). To clarify PPihkala. I don't think the atom is split into the parts physically. It is just in a probability superposition. Anyway, this article confuses me a bit. I would expect that measured state (after few throws) will be present equally in all the steps from minimum to maximum. Can someone explain, how the quantum probability forces this type of graph (de facto reversed Bell's curve) ?

Update: I got it I guess. It's because of the interference.
Birger
not rated yet Jul 10, 2009
Since there are putative quantum algorithms for even the so-called "Fourier transform" -used by computers for pattern recognition- a tiny quantum computer chip would be able to rival the human brain in its ability to identify objects (a task that requires enormous computer power, but which the brain handles through layers of "neural networks" and massively parallel processing).
One obvious application is the interpretation of CCTV images without human operators.

What many have failed to see is the consequences for modern warfare: anything bigger than a bird or small mammal on the battlefield could immediately be detected by small sensors with such quantum computer chips.
A human-operated armoured vechicle or aircraft, would thus immediately be detected once it broke cover. Small, remotely operated vehicles might survive on a battlefield, but holding captured ground requires a human presence.
In principle, it could make offensive warfare very costly, like WWI before the advent of the tank.
ciantic
not rated yet Jul 10, 2009
I found other resources that confirm this for instance in this http://arxiv.org/.../0303081 at the page 4: "If we continued the quantum walk with such a measurement at each iteration we obtain the plain classical random walk on the line (or on the circle)."

and also at the same page: "In the quantum random walk we will of course not measure the coin register during intermediate iterations, but rather keep the quantum correlations between different positions and let them interfere in subsequent steps." thus there exists coin (Hadamarad coin) that when:

throw, look; throw, look; ... 100 times you get bell's curve, but if you do:

throw, throw, look; throw, throw, look; ... 100 times you get curve like in the paper above.

Pretty neat, not sure what the implications are yet.
El_Nose
not rated yet Jul 10, 2009
-- Hey remember the advent of classical computing that u learn in sophomore year in college and the class is really boring but you go through the generations on computers real quick so that you at least now how we got to where we are.

This reminds me of the first and second generation of computing where computations were in essence done mechanically like moving this atom around and measuring. I wonder knowing that we will eventually abstract this foundation away can we begin trying to think on that new level of abstration today.

Do we know enough about this layer of abstration to let it go and work a layer higher or are we in need of the engineering invention equivalent of the transistor tube to move away from gears and pulleys again??? PLEASE RESPOND
lysdexia
not rated yet Jul 16, 2009
There's no "a dice".

It's easy; the inverse probability plot is for the potential, and the obverse for the cinetic.

Fast is not a speed; glue is fast.
ben6993
not rated yet Jul 16, 2009
Thank you ciantic for the reference to Kempe's article. I have downloaded it and skimmed the first half. I can see it is a truly wonderful new area without understanding the non-classical parts yet. It will provide months of bedside reading/learning matter!

Classical random walks seem to behave like the boring stay at home who never ventures far from home. I am not clear whether the quantum random walk particles are like the Ben Fogle adventurer always at either the North or South Pole, ie, stiving to infinity to leave all else behind, or are they exhibiting fractal-like behaviour where they stay within bounds and have a complex pattern of location?

Pauli's exclusion principle, I think, pertains to different electons not being in the same state. And the electons near an atom have shell patterns of locations. But the particle in this random walk is on its own. Well not completely on its own as it is operating within the laws of physics, and therefore sits in spacetime. And the single particle appears to be able to be everywhere at the same time, with varying probablilities. So is the single particle interacting with itself? And so can the exclusion principle apply to the varying possible positions of the single particle? And will a single particle interact with itself to locate in shells even where there is no central nucleus?

What would a quantum random walk be like for two particle in an enclosed space?

A complex, and beautiful, fractal picture like a mandlebrot diagram can result from applying a simple formula. Would a particle, or point, generating the 2-D mandlebrot picture, using the simple formula for its position, appear to be located in shells if it were only measured in 1-D? Likewise is the quantum random walk particle inabiting higher dimensions where it has a rich pattern that defaults to shells when looked at in reduced numbers of dimensions?

And can you take a mandlebrot picture and re-run it but this time taking the point or particle on a quantum random walk as it also follows the simple formula? Ie make it follow the formula but with an extra random element included in the formula?

More news stories

'Dressed' laser aimed at clouds may be key to inducing rain, lightning

The adage "Everyone complains about the weather but nobody does anything about it," may one day be obsolete if researchers at the University of Central Florida's College of Optics & Photonics and the University ...

After 13 years, progress in pitch-drop experiment (w/ video)

(Phys.org) —As Cyclone Ita hit northern Australia last weekend, a much slower collision occurred in the world's longest-running lab project, The University of Queensland's Pitch Drop Experiment.

How to test the twin paradox without using a spaceship

Forget about anti-ageing creams and hair treatments. If you want to stay young, get a fast spaceship. That is what Einstein's Theory of Relativity predicted a century ago, and it is commonly known as "twin ...

Researchers find tin selenide shows promise for efficiently converting waste heat into electrical energy

(Phys.org) —A team of researchers working at Northwestern University has found that tin selenide (SnSe) has the highest Carnot efficiency for a thermoelectric cycle ever found, making it potentially a possible ...

Micro-macro entangled 'cat states' could one day test quantum gravity

(Phys.org) —In Schrödinger's famous thought experiment, a cat's quantum state becomes entangled with the quantum state of a decaying nucleus, resulting in the odd situation that the cat is both alive and ...

West Africa's Ebola outbreak prompts changes in I.Coast cuisine

West Africa's first outbreak of Ebola fever is bad news for gourmets in Ivory Coast, but brings respite from the hunter to species sought out for tasty meat but feared to carry the disease.

NASA: Engineer vital to 1969 moon landing dies

John C. Houbolt, an engineer whose contributions to the U.S. space program were vital to NASA's successful moon landing in 1969, has died. He was 95.

Researchers use Twitter to predict crime

Hidden in the Twittersphere are nuggets of information that could prove useful to crime fighters—even before a crime has been committed.

Google Trends info is placed on inbox duty for subscribers

(Phys.org) —Google Trends has added a new service to its mix, where users can enter email subscriptions for Google Trends, and as a can be sent notifications on topics of interest, showing them what is ...

Nintendo's trailblazing Game Boy marks 25th anniversary

Nintendo's trailblazing Game Boy marks its 25th anniversary on Monday with the portable device's legacy living on in cutting-edge smartphone games and among legions of nostalgic fans.