## Abstract

We show how to search N items arranged on a √N × √N grid in time O(√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 Ω(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(√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 be chosen judiciously: we show that another "natural" choice of coin gives a walk that takes Ω(N) steps. We also show that in 2 dimensions it is sufficient to have a two-dimensional coin-space to achieve the time O(√N log N).

Original language | English (US) |
---|---|

Pages | 1099-1108 |

Number of pages | 10 |

State | Published - 2005 |

Event | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: Jan 23 2005 → Jan 25 2005 |

### Other

Other | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | Vancouver, BC |

Period | 1/23/05 → 1/25/05 |

## ASJC Scopus subject areas

- Software
- Mathematics(all)