Article

Coins make quantum walks faster

Authors:

Andris Ambainis,

Alexander RivoshAuthors Info & Claims

SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 1099 - 1108

Published: 23 January 2005 Publication History

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).

References

[1]

{AA03} S. Aaronson and A. Ambainis. Quantum search of spatial regions. In Proc. 44th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pages 200--209, 2003.

Digital Library

[2]

{AAKV01} D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani. Quantum walks on graphs. In Proc. 33th STOC, pages 50--59, New York, NY, 2001. ACM.

Digital Library

[3]

{ABN+01} A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous. One-dimensional quantum walks. In Proc. 33th STOC, pages 60--69, New York, NY, 2001. ACM.

Digital Library

[4]

{Amb04} A. Ambainis. Quantum walk algorithm for element distinctness. Proc. 45th FOCS, to appear, 2004. Also lanl-arXive quant-ph/0311001.

Digital Library

[5]

{AKR04} A. Ambainis, J. Kempe, A. Rivosh. Coins make quantum walks faster. Technical report, lanl-arXive quant-ph/0402107, 2004.

[6]

{Ben02} Paul Benioff. Space searches with a quantum robot. In Quantum computation and information (Washington, DC, 2000), volume 305 of Contemp. Math., pages 1--12. Amer. Math. Soc., Providence. RI, 2002.

[7]

{BHMT02} G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In Quantum computation and information (Washington, DC, 2000), volume 305 of Contemp. Math., pages 53--74. Amer. Math. Soc., Providence, RI, 2002.

[8]

{CCD+03} A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorithmic speedup by a quantum walk. In Proc. 35th STOC, pages 59--68, 2003. quant-ph/0209131.

Digital Library

[9]

{CE03} A. M. Childs and J. M. Eisenberg. Quantum algorithms for subset finding. Technical report, lanl-arXive quant-ph/0311038, 2003.

[10]

{CFG02} A. Childs, E. Farhi, and S. Gutmann. An example of the difference between quantum and classical random walks. Quantum Information Processing, 1:35, 2002. lanl-report quant-ph/0103020.

Digital Library

[11]

{CG03} A. M. Childs and J. Goldstone. Spatial search by quantum walk. Phys. Rev. A, 70:022314, 2004. Also lanl-report quant-ph/0306054, 2003.

[12]

{CG04} A. M. Childs and J. Goldstone. Spatial search and the Dirac equation. Technical report, lanl-arXive quant-ph/0405120, 2004.

[13]

{FG98} E. Farhi and S. Gutmann. Quantum computation and decision trees. Phys. Rev. A, 58:915--928, 1998.

[14]

{Gro96} L. Grover. A fast quantum mechanical algorithm for database search. In Proc. 28th STOC, pages 212--219, Philadelphia, Pennsylvania, 1996. ACM Press.

Digital Library

[15]

{Kem03a} J. Kempe. Quantum random walks - an introductory overview. Contemporary Physics, 44(4):302--327, 2003. lanl-arXive quant-ph/0303081.

[16]

{Kem03b} J. Kempe. Quantum walks hit exponentially faster. In RANDOM-APPROX 2003, Lecture Notes in Computer Science, pages 354--369, Heidelberg, 2003. Springer. lanl-arXiv quant-ph/0205083.

[17]

{Mey96} D. Meyer. From quantum cellular automata to quantum lattice gases. J. Stat. Phys., 85:551--574, 1996.

[18]

{MR95} R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

[19]

{MR02} C. Moore and A. Russell. Quantum walks on the hypercube. In J. D. P. Rolim and S. Vadhan, editors, Proc. RANDOM 2002, pages 164--178, Cambridge, MA, 2002. Springer.

Digital Library

[20]

{MSS03} F. Magniez, M. Santha, and M. Szegedy. Quantum algorithms for the triangle problem. Proceedings of SODA'05, to appear. Also lanl-arXive quant-ph/0310134.

Digital Library

[21]

{SKW03} N. Shenvi, J. Kempe, and K. B. Whaley. A quantum random walk search algorithm. Phys. Rev. A, 67(5):052307, 2003. lanl-arXive quant-ph/0210064.

[22]

{She03} Neil Shenvi. Random Walk Simulations. unpublished.

[23]

{Sze04} M. Szegedy. Spectra of quantized walks and a √Δε rule, quant-ph/0401053.

[24]

{Sze04a} M. Szegedy. Quantum speedup of Markov chain based algorithms. Proceedings of FOCS'04, to appear.

Digital Library

Cited By

Abhijith JPatel A(2019)Improving the query complexity of quantum spatial search in two dimensionsQuantum Information & Computation10.5555/3370207.337020919:7-8(555-574)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.5555/3370207.3370209
Adami RFukuizumi RSegawa E(2019)A nonlinear quantum walk induced by a quantum graph with nonlinear delta potentialsQuantum Information Processing10.1007/s11128-019-2215-818:4(1-14)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s11128-019-2215-8
Xue XRuan YLiu Z(2019)Discrete-time quantum walk search on Johnson graphsQuantum Information Processing10.1007/s11128-018-2158-518:2(1-10)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s11128-018-2158-5
Show More Cited By

Recommendations

Generalized teleportation by quantum walks

We develop a generalized teleportation scheme based on quantum walks with two coins. For an unknown qubit state, we use two-step quantum walks on the line and quantum walks on the cycle with four vertices for teleportation. For any d-dimensional states, ...
Quantum walks: a comprehensive review

Quantum walks, the quantum mechanical counterpart of classical random walks, is an advanced tool for building quantum algorithms that has been recently shown to constitute a universal model of quantum computation. Quantum walks is now a solid field of ...
Experimental realization of quantum teleportation using coined quantum walks
Abstract
The goal of teleportation is to transfer the state of one particle to another particle. In coined quantum walks, conditional shift operators can introduce entanglement between position space and coin space. This entanglement resource can be used ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

January 2005

1205 pages

ISBN:0898715857

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 2005

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
873
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)2

Reflects downloads up to 09 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Abhijith JPatel A(2019)Improving the query complexity of quantum spatial search in two dimensionsQuantum Information & Computation10.5555/3370207.337020919:7-8(555-574)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.5555/3370207.3370209
Adami RFukuizumi RSegawa E(2019)A nonlinear quantum walk induced by a quantum graph with nonlinear delta potentialsQuantum Information Processing10.1007/s11128-019-2215-818:4(1-14)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s11128-019-2215-8
Xue XRuan YLiu Z(2019)Discrete-time quantum walk search on Johnson graphsQuantum Information Processing10.1007/s11128-018-2158-518:2(1-10)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s11128-018-2158-5
Abhijith JPatel A(2018)Spatial search on graphs with multiple targets using flip-flop quantum walkQuantum Information & Computation10.5555/3370234.337023718:15-16(1295-1331)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.5555/3370234.3370237
Portugal R(2018)Element distinctness revisitedQuantum Information Processing10.1007/s11128-018-1930-x17:7(1-15)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s11128-018-1930-x
Wong T(2018)Faster search by lackadaisical quantum walkQuantum Information Processing10.1007/s11128-018-1840-y17:3(1-9)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s11128-018-1840-y
Wong T(2017)Equivalence of Szegedy's and coined quantum walksQuantum Information Processing10.1007/s11128-017-1667-y16:9(1-15)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s11128-017-1667-y
Fuda TFunakawa DSuzuki A(2017)Localization of a multi-dimensional quantum walk with one defectQuantum Information Processing10.1007/s11128-017-1653-416:8(1-24)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s11128-017-1653-4
Wong TSantos R(2017)Exceptional quantum walk search on the cycleQuantum Information Processing10.1007/s11128-017-1606-y16:6(1-17)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s11128-017-1606-y
źTefaźák MSkoupý S(2017)Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphsQuantum Information Processing10.1007/s11128-017-1516-z16:3(1-14)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s11128-017-1516-z
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten