An Example of the Difference Between Quantum and Classical Random Walks

被引：335

作者：

Childs, Andrew M. ^{[1
]}

Farhi, Edward ^{[1
]}

Gutmann, Sam ^{[2
]}

机构：

[1] MIT, Ctr Theoret Phys, Cambridge, MA 02139 USA

[2] Northeastern Univ, Dept Math, Boston, MA 02115 USA

来源：

QUANTUM INFORMATION PROCESSING | 2002年 / 1卷 / 1-2期

关键词：

quantum random walk; hitting times;

D O I：

10.1023/A:1019609420309

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

In this note, we discuss a general definition of quantum random walks on graphs and illustrate with a simple graph the possibility of very different behavior between a classical random walk and its quantum analog. In this graph, propagation between a particular pair of nodes is exponentially faster in the quantum case.

引用

页码：35 / 43

页数：9

共 6 条

[1]

AHARONOV D, QUANTPH0012090

[2] QUANTUM RANDOM-WALKS [J].

AHARONOV, Y ;

DAVIDOVICH, L ;

ZAGURY, N .

PHYSICAL REVIEW A, 1993, 48 (02) :1687-1690

[3]

Andris Ambainis, 2001, P 33 ANN ACM S THEOR, P37, DOI DOI 10.1145/380752.380757

[4] Quantum computation and decision trees [J].

Farhi, E ;

Gutmann, S .

PHYSICAL REVIEW A, 1998, 58 (02) :915-928

[5] THE FUNCTIONAL INTEGRAL CONSTRUCTED DIRECTLY FROM THE HAMILTONIAN [J].

FARHI, E ;

GUTMANN, S .

ANNALS OF PHYSICS, 1992, 213 (01) :182-203

[6] On the absence of homogeneous scalar unitary cellular automata [J].

Meyer, DA .

PHYSICS LETTERS A, 1996, 223 (05) :337-340

← 1 →