Synopsis: Treasure hunt

A new approach proves that a quantum random walk is faster than the classical version at finding marked points on a graph.

Many classical computer algorithms make use of random walks. Among these are spatial search algorithms, which are mathematically equivalent to the task of finding a marked element on a graph. The speed of such an algorithm is characterized by its “hitting time,” which is defined as the expectation value of the number of steps needed to reach a marked state.

It has long been suspected that a suitable quantum algorithm must exist that performs the same search with far fewer steps—of the order of the square root of the classical hitting time—but attempts to simply generalize the classical random walk to the quantum case have only been partially successful.

In an article appearing in Physical Review A, Hari Krovi, Maris Ozols, and Jérémie Roland at NEC Laboratories, Inc., in the US, have finally succeeded in developing a quantum algorithm, which for any reversible random walk and any set of marked vertices, has a running time that scales like the square root of the classical hitting time. Rather than base their algorithm on a conventional quantum walk, they resort to what is called the “adiabatic quantum-computing paradigm.” Here, the solution to the graph problem is obtained as the endpoint of the “trajectory” that the ground state of a Hamiltonian takes as a parameter, s, is slowly varied.

This type of adiabatic quantum computation is equivalent to the more familiar “circuit” model of quantum computation, which means that a formulation of the search problem in terms of more than one quantum model should be possible [1]. – Julio Gea-Banacloche

[1] H. Krovi, F. Magniez, M. Ozols, and J. Roland, in Proceedings of the 37th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 6198 (Springer, New York, 2010), pp. 540–551.


Announcements

More Announcements »

Subject Areas

Quantum Information

Previous Synopsis

Astrophysics

Solar lab

Read More »

Next Synopsis

Semiconductor Physics

A bumpy road

Read More »

Related Articles

Synopsis: All-Around Single-Photon Source
Quantum Information

Synopsis: All-Around Single-Photon Source

A quantum dot embedded in a micropillar is an efficient source of pure and indistinguishable single photons. Read More »

Focus: Burglar Alarm Based on Quantum Mechanics
Quantum Information

Focus: Burglar Alarm Based on Quantum Mechanics

Researchers demonstrated a scheme that relies on quantum mechanics to prevent unauthorized access to restricted objects, such as nuclear materials. Read More »

Viewpoint: Closing the Door on Einstein and Bohr’s Quantum Debate
Optics

Viewpoint: Closing the Door on Einstein and Bohr’s Quantum Debate

By closing two loopholes at once, three experimental tests of Bell’s inequalities remove the last doubts that we should renounce local realism. They also open the door to new quantum information technologies. Read More »

More Articles