[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Faster search by lackadaisical quantum walk

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

In the typical model, a discrete-time coined quantum walk searching the 2D grid for a marked vertex achieves a success probability of \(O(1/\log N)\) in \(O(\sqrt{N \log N})\) steps, which with amplitude amplification yields an overall runtime of \(O(\sqrt{N} \log N)\). We show that making the quantum walk lackadaisical or lazy by adding a self-loop of weight 4 / N to each vertex speeds up the search, causing the success probability to reach a constant near 1 in \(O(\sqrt{N \log N})\) steps, thus yielding an \(O(\sqrt{\log N})\) improvement over the typical, loopless algorithm. This improved runtime matches the best known quantum algorithms for this search problem. Our results are based on numerical simulations since the algorithm is not an instance of the abstract search algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings 28th Annual ACM Symposium Theory Computing, STOC ’96, pp. 212–219. ACM, New York, NY (1996)

  2. Benioff, P.: Space Searches with a Quantum Robot, volume 305 of Contemporary Mathematics, pp. 1–12. American Mathematical Society, Providence, RI (2002)

    MATH  Google Scholar 

  3. Aaronson, S., Ambainis, A.: Quantum search of spatial regions. Theor. Comput. 1(4), 47–79 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  4. Childs, A.M., Goldstone, J.: Spatial search by quantum walk. Phys. Rev. A 70, 022314 (2004)

    Article  ADS  Google Scholar 

  5. Meyer, D.A., Wong, T.G.: Connectivity is a poor indicator of fast quantum search. Phys. Rev. Lett. 114, 110503 (2015)

    Article  ADS  Google Scholar 

  6. Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings 16th Annual ACM-SIAM Symposium Discrete Algorithms, SODA ’05, pp. 1099–1108. SIAM, Philadelphia, PA (2005)

  7. Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum Amplitude Amplification and Estimation, volume 305 of Contemporary Mathematics, pp. 53–74. American Mathematical Society, Providence, RI (2002)

    MATH  Google Scholar 

  8. Childs, A.M., Goldstone, J.: Spatial search and the Dirac equation. Phys. Rev. A 70, 042312 (2004)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  9. Wong, T.G.: Grover search with lackadaisical quantum walks. J. Phys. A Math. Theor. 48(43), 435304 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  10. Wong, T.G.: Coined quantum walks on weighted graphs. J. Phys. A Math. Theor. 50(47), 475301 (2017)

    Article  ADS  MathSciNet  Google Scholar 

  11. Tulsi, A.: Faster quantum-walk algorithm for the two-dimensional spatial search. Phys. Rev. A 78, 012310 (2008)

    Article  ADS  MATH  Google Scholar 

  12. Ambainis, A., Bačkurs, A., Nahimovs, N., Ozols, R., Rivosh, A.: Search by quantum walks on two-dimensional grid without amplitude amplification. In: Proceedings 7th Annual Conference Theory of Quantum Computation, Communication, and Cryptography, TQC 2012, pp. 87–97. Springer, Tokyo (2013)

  13. Krovi, H., Magniez, F., Ozols, M., Roland, J.: Quantum walks can find a marked element on any graph. Algorithmica 74(2), 851–907 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  14. Portugal, R., Fernandes, T.D.: Quantum search on the two-dimensional lattice using the staggered model with hamiltonians. Phys. Rev. A 95, 042341 (2017)

    Article  ADS  Google Scholar 

  15. Meyer, D.A.: From quantum cellular automata to quantum lattice gases. J. Stat. Phys. 85(5–6), 551–574 (1996)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  16. Meyer, D.A.: On the absence of homogeneous scalar unitary cellular automata. Phys. Lett. A 223(5), 337–340 (1996)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  17. Shenvi, N., Kempe, J., Whaley, K.B.: Quantum random-walk search algorithm. Phys. Rev. A 67, 052307 (2003)

    Article  ADS  Google Scholar 

  18. Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’04, pp. 32–41. IEEE Computer Society, Washington, DC (2004)

  19. Magniez, F., Nayak, A., Richter, P.C., Santha, M.: On the hitting times of quantum versus random walks. Algorithmica 63(1), 91–116 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  20. Wong, T.G.: Equivalence of Szegedy’s and coined quantum walks. Quantum Inf. Process. 16(9), 215 (2017)

    Article  ADS  MathSciNet  Google Scholar 

  21. Abal, G., Donangelo, R., Marquezino, F.L., Portugal, R.: Spatial search on a honeycomb network. Math. Struct. Comput. Sci. 20(6), 999–1009 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  22. Marquezino, FdL, Portugal, R., Boettcher, S.: Spatial search algorithms on hanoi networks. Phys. Rev. A 87, 012329 (2013)

    Article  ADS  Google Scholar 

Download references

Acknowledgements

Thanks to Scott Aaronson for useful discussions. This work was supported by the U.S. Department of Defense Vannevar Bush Faculty Fellowship of Scott Aaronson.

Author information

Author notes

  1. Thomas G. Wong

    Present address: Department of Physics, Creighton University, 2500 California Plaza, Omaha, NE, 68178, USA

Authors and Affiliations

  1. Department of Computer Science, University of Texas at Austin, 2317 Speedway, Austin, TX, 78712, USA

    Thomas G. Wong

Authors
  1. Thomas G. Wong
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thomas G. Wong.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wong, T.G. Faster search by lackadaisical quantum walk. Quantum Inf Process 17, 68 (2018). https://doi.org/10.1007/s11128-018-1840-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-018-1840-y

Keywords

Search

Navigation