Coins Make Quantum Walks Faster

被引：0

作者：

Ambainis, Andris ^{[1
]}

Kempe, Julia ^{[1
]}

Rivosh, Alexander ^{[1
]}

机构：

[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

来源：

PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 2005年

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show how to search N items arranged on a root N x root N grid in time O(root N log N), using a discrete time quantum walk. This result for the first time exhibits a significant difference between discrete time and continuous time walks without coin degrees of freedom, since it has been shown recently that such a continuous time walk needs time Omega(N) to perform the same task. Our result improves on a previous bound for quantum local search by Aaronson and Ambainis. We generalize our result to 3 and more dimensions where the walk yields the optimal performance of O(root N) and give several extensions of quantum walk search algorithms and generic expressions for its performance for general graphs. The coin-flip operation needs to he chosen judiciously: we show that another "natural" choice of coin gives a walk that takes Omega(N) steps. We also show that in 2 dimensions it is sufficient to have a two-dimensional coin-space to achieve the time O(root N log N).

引用

页码：1099 / 1108

页数：10

共 24 条

[11] CHILDS AM, 2004, QUANTPH0405120 LANLA
[12] An Example of the Difference Between Quantum and Classical Random Walks
Childs, Andrew M.
Farhi, Edward
Gutmann, Sam
[J]. QUANTUM INFORMATION PROCESSING, 2002, 1 (1-2) : 35 - 43
[13] Quantum computation and decision trees
Farhi, E
Gutmann, S
[J]. PHYSICAL REVIEW A, 1998, 58 (02): : 915 - 928
[14] Grover L. K., 1996, P 28 ANN ACM S THEOR, P212, DOI [DOI 10.1145/237814.237866, 10.1145/237814.237866]
[15] Kempe J, 2003, LECT NOTES COMPUT SC, V2764, P354
[16] Quantum random walks: an introductory overview
Kempe, J
[J]. CONTEMPORARY PHYSICS, 2003, 44 (04) : 307 - 327
[17] MAGNIEZ F, 2005, P SODA 05 IN PRESS
[18] From quantum cellular automata to quantum lattice gases
Meyer, DA
[J]. JOURNAL OF STATISTICAL PHYSICS, 1996, 85 (5-6) : 551 - 574
[19] Moore C., 2002, PROC 6 INT WORKSHOP, P164
[20] Motwani Rajeev, 1995, RANDOMIZED ALGORITHM

← 1 2 3 →