Skip to main content
SpringerLink
Log in

Lackadaisical Quantum Walk in the Hypercube to Search for Multiple Marked Vertices

  • Conference paper
  • First Online:
Intelligent Systems (BRACIS 2021)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 13073))

Included in the following conference series:

Abstract

Adding self-loops at each vertex of a graph improves the performance of quantum walks algorithms over loopless algorithms. Many works approach quantum walks to search for a single marked vertex. In this article, we experimentally address several problems related to quantum walk in the hypercube with self-loops to search for multiple marked vertices. We first investigate the quantum walk in the loopless hypercube. We saw that neighbor vertices are also amplified and that approximately 1/2 of the system energy is concentrated in them. We show that the optimal value of l for a single marked vertex is not optimal for multiple marked vertices. We define a new value of \(l = (n/N)\cdot k\) to search multiple marked vertices. Next, we use this new value of l found to analyze the search for multiple marked vertices non-adjacent and show that the probability of success is close to 1. We also use the new value of l found to analyze the search for several marked vertices that are adjacent and show that the probability of success is directly proportional to the density of marked vertices in the neighborhood. We also show that, in the case where neighbors are marked, if there is at least one non-adjacent marked vertex, the probability of success increases to close to 1. The results found show that the self-loop value for the quantum walk in the hypercube to search for several marked vertices is \(l = (n / N) \cdot k \).

Acknowledgments to the Science and Technology Support Foundation of Pernambuco (FACEPE) Brazil, Brazilian National Council for Scientific and Technological Development (CNPq), and Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001 by their financial support to the development of this research.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 79.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 99.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Aharonov, Y., Davidovich, L., Zagury, N.: Quantum random walks. Phys. Rev. A 48(2), 1687 (1993)

    Article  Google Scholar 

  2. Ambainis, A., Bačkurs, A., Nahimovs, N., Ozols, R., Rivosh, A.: Search by quantum walks on two-dimensional grid without amplitude amplification. In: Iwama, K., Kawano, Y., Murao, M. (eds.) TQC 2012. LNCS, vol. 7582, pp. 87–97. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-35656-8_7

    Chapter  MATH  Google Scholar 

  3. Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. arXiv preprint quant-ph/0402107 (2004)

    Google Scholar 

  4. Bezerra, G., Lugão, P., Portugal, R.: Quantum walk-based search algorithms with multiple marked vertices. Phys. Rev. A 103(6), 062202 (2021)

    Article  MathSciNet  Google Scholar 

  5. de Carvalho, J.H.A., de Souza, L.S., de Paula Neto, F.M., Ferreira, T.A.E.: Impacts of multiple solutions on the Lackadaisical Quantum Walk search algorithm. In: Cerri, R., Prati, R.C. (eds.) BRACIS 2020. LNCS (LNAI), vol. 12319, pp. 122–135. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-61377-8_9

    Chapter  Google Scholar 

  6. Carvalho, J.H.A., Souza, L.S., Paula Neto, F.M., Ferreira, T.A.E.: On applying the lackadaisical quantum walk algorithm to search for multiple solutions on grids. arXiv preprint quant-ph/2106.06274 (2021)

    Google Scholar 

  7. Kempe, J.: Quantum random walks hit exponentially faster. arXiv preprint quant-ph/0205083 (2002)

    Google Scholar 

  8. McMahon, D.: Quantum Computing Explained. Wiley, New York (2007)

    Google Scholar 

  9. Moore, C., Russell, A.: Quantum walks on the hypercube. In: Rolim, J.D.P., Vadhan, S. (eds.) RANDOM 2002. LNCS, vol. 2483, pp. 164–178. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45726-7_14

    Chapter  Google Scholar 

  10. Nahimovs, N.: Lackadaisical Quantum Walks with multiple marked vertices. In: Catania, B., Královič, R., Nawrocki, J., Pighizzini, G. (eds.) SOFSEM 2019. LNCS, vol. 11376, pp. 368–378. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-10801-4_29

    Chapter  Google Scholar 

  11. Nahimovs, N., Santos, R.A.M., Khadiev, K.R.: Adjacent vertices can be hard to find by quantum walks. Mosc. Univ. Comput. Math. Cybern. 43(1), 32–39 (2019)

    Article  MathSciNet  Google Scholar 

  12. Nahimovs, N., Santos, R.A.: Lackadaisical quantum walks on 2D grids with multiple marked vertices. arXiv preprint arXiv:2104.09955 (2021)

  13. Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. AAPT, Cambridge (2002)

    Google Scholar 

  14. Potoček, V., Gábris, A., Kiss, T., Jex, I.: Optimized quantum random-walk search algorithms on the hypercube. Phys. Rev. A 79(1), 012325 (2009)

    Article  Google Scholar 

  15. Rhodes, M.L., Wong, T.G.: Quantum walk search on the complete bipartite graph. Phys. Rev. A 99(3), 032301 (2019)

    Article  Google Scholar 

  16. Rhodes, M.L., Wong, T.G.: Search on vertex-transitive graphs by lackadaisical quantum walk. Quantum Inf. Process. 19(9), 1–16 (2020)

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  18. Singh, J., Singh, M.: Evolution in quantum computing. In: 2016 International Conference System Modeling & Advancement in Research Trends (SMART), pp. 267–270. IEEE (2016)

    Google Scholar 

  19. Souza, L.S., Carvalho, J.H.A., Ferreira, T.A.E.: Quantum walk to train a classical artificial neural network. In: 2019 8th Brazilian Conference on Intelligent Systems (BRACIS), pp. 836–841. IEEE (2019)

    Google Scholar 

  20. Souza, L.S., Carvalho, J.H.A., Ferreira, T.A.E.: Classical artificial neural network training using quantum walks as a search procedure. IEEE Trans. Comput. (2021)

    Google Scholar 

  21. Venegas-Andraca, S.E.: Quantum walks: a comprehensive review. Quantum Inf. Process. 11(5), 1015–1106 (2012)

    Article  MathSciNet  Google Scholar 

  22. Wang, H., Zhou, J., Wu, J., Yi, X.: Adjustable self-loop on discrete-time quantum walk and its application in spatial search. arXiv preprint arXiv:1707.00601 (2017)

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

    Article  MathSciNet  Google Scholar 

  24. Wong, T.G.: Faster search by lackadaisical quantum walk. Quantum Inf. Process. 17(3), 1–9 (2018)

    Article  MathSciNet  Google Scholar 

  25. Yanofsky, N.S., Mannucci, M.A.: Quantum Computing for Computer Scientists. Cambridge University Press, Cambridge (2008)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Estatística e Informática, Universidade Federal Rural de Pernambuco, Recife, Brazil

    Luciano S. de Souza & Tiago A. E. Ferreira

  2. Centro de Informática, Universidade Federal de Pernambuco, Recife, Brazil

    Jonathan H. A. de Carvalho

Authors
  1. Luciano S. de Souza
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jonathan H. A. de Carvalho
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tiago A. E. Ferreira
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Luciano S. de Souza .

Editor information

Editors and Affiliations

  1. Universidade Federal de Sergipe, São Cristóvão, Brazil

    André Britto

  2. Universidade de São Paulo, São Paulo, Brazil

    Karina Valdivia Delgado

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

de Souza, L.S., de Carvalho, J.H.A., Ferreira, T.A.E. (2021). Lackadaisical Quantum Walk in the Hypercube to Search for Multiple Marked Vertices. In: Britto, A., Valdivia Delgado, K. (eds) Intelligent Systems. BRACIS 2021. Lecture Notes in Computer Science(), vol 13073. Springer, Cham. https://doi.org/10.1007/978-3-030-91702-9_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-91702-9_17

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-91701-2

  • Online ISBN: 978-3-030-91702-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation