Quantum search by continuous-time quantum walk on t-designs | Quantum Information Processing Skip to main content
Springer Nature Link
Log in

Quantum search by continuous-time quantum walk on t-designs

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

This work examines the time complexity of quantum search algorithms on combinatorial t-designs with multiple marked elements using the continuous-time quantum walk. Through a detailed exploration of t-designs and their incidence matrices, we identify a subset of bipartite graphs that are conducive to success compared to random-walk-based search algorithms. These graphs have adjacency matrices with eigenvalues and eigenvectors that can be determined algebraically and are also suitable for analysis in the multiple-marked vertex scenario. We show that the continuous-time quantum walk on certain symmetric t-designs achieves an optimal running time of \(O\left( \sqrt{n}\right) \), where n is the number of points and blocks, even when accounting for an arbitrary number of marked elements. Upon examining two primary configurations of marked elements distributions, we observe that the success probability is consistently o(1), but it approaches 1 asymptotically in certain scenarios.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Explore related subjects

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

Data availability

All data generated or analyzed during this study are included in this published article.

References

  1. Farhi, E., Gutmann, S.: Quantum computation and decision trees. Phys. Rev. A 58, 915–928 (1998)

    Article  MathSciNet  ADS  Google Scholar 

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

    Article  ADS  Google Scholar 

  3. Marsh, S., Wang, J.B.: Combinatorial optimization via highly efficient quantum walks. Phys. Rev. Res. 2, 023302 (2020)

    Article  Google Scholar 

  4. Kadian, K., Garhwal, S., Kumar, A.: Quantum walk and its application domains: a systematic review. Comput. Sci. Rev. 41, 100419 (2021)

    Article  MathSciNet  Google Scholar 

  5. Portugal, R.: Quantum Walks and Search Algorithms, 2nd edn. Springer, Cham (2018)

    Book  Google Scholar 

  6. Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2), 325–328 (1997)

    Article  ADS  Google Scholar 

  7. Philipp, P., Tarrataca, L., Boettcher, S.: Continuous-time quantum search on balanced trees. Phys. Rev. A 93, 032305 (2016)

    Article  MathSciNet  ADS  Google Scholar 

  8. Tanaka, H., Sabri, M., Portugal, R.: Spatial search on Johnson graphs by continuous-time quantum walk. Quantum Inf. Process. 21(2), 74 (2022)

    Article  MathSciNet  ADS  Google Scholar 

  9. Stinson, D.R.: Combinatorial Designs: Constructions and Analysis. Springer, New York (2004)

    Google Scholar 

  10. Beth, T., Jungnickel, D., Lenz, H.: Design Theory, vol. 1, 2nd edn. Cambridge University Press, Cambridge (1999)

    Book  Google Scholar 

  11. Rothaus, O.S.: On “bent’’ functions. J. Comb. Theory Ser. A 20(3), 300–305 (1976)

    Article  Google Scholar 

  12. Dankert, C., Cleve, R., Emerson, J., Livine, E.: Exact and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev. A 80, 012304 (2009)

    Article  ADS  Google Scholar 

  13. Ambainis, A., Emerson, J.: Quantum t-designs: t-wise independence in the quantum world. In: Twenty-second annual IEEE conference on computational complexity (CCC’07), pp. 129–140 (2007)

  14. Emerson, J., Alicki, R., Życzkowski, K.: Scalable noise estimation with random unitary operators. J. Opt. B Quantum Semiclassical Opt. 7(10), S347 (2005)

    Article  MathSciNet  ADS  Google Scholar 

  15. Godsil, C., Royle, G.F.: Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics. Springer, New York (2001)

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

    Article  ADS  Google Scholar 

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

    Article  ADS  Google Scholar 

  18. Pan, N., Chen, T., Sun, H., Zhang, X.: Electric-circuit realization of fast quantum search. Research 2021, 9793071 (2021)

    Article  ADS  Google Scholar 

  19. Ji, T., Pan, N., Chen, T., Zhang, X.: Fast quantum search of multiple vertices based on electric circuits. Quantum Inf. Process. 21(5), 172 (2022)

    Article  ADS  Google Scholar 

  20. Ji, T., Pan, N., Chen, T., Zhang, X.: Quantum search of many vertices on the joined complete graph. Chin. Phys. B 31(7), 070504 (2022)

    Article  ADS  Google Scholar 

  21. Wong, T.G.: Spatial search by continuous-time quantum walk with multiple marked vertices. Quantum Inf. Process. 15(4), 1411–1443 (2016)

    Article  MathSciNet  ADS  Google Scholar 

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

    Article  MathSciNet  ADS  Google Scholar 

  23. Lugão, P.H.G., Portugal, R., Sabri, M., Tanaka, H.: Multimarked spatial search by continuous-time quantum walk. arXiv:2203.14384 (2022)

  24. Apers, S., Chakraborty, S., Novo, L., Roland, J.: Quadratic speedup for spatial search by continuous-time quantum walk. Phys. Rev. Lett. 129, 160502 (2022)

    Article  MathSciNet  ADS  Google Scholar 

  25. Roget, M., Kadri, H., Di Molfetta, G.: Optimality conditions for spatial search with multiple marked vertices. Phys. Rev. Res. 5, 033021 (2023)

    Article  Google Scholar 

  26. Colbourne, C., Dinitz, J.: Handbook of Combinatorial Designs. CRC Press, Boca Raton (2007)

    Google Scholar 

  27. Chakraborty, S., Novo, L., Roland, J.: Optimality of spatial search via continuous-time quantum walks. Phys. Rev. A 102, 032214 (2020)

    Article  MathSciNet  ADS  Google Scholar 

  28. Chan, A., Godsil, C.D., Tamon, C., Xie, W.: Of shadows and gaps in spatial search. Quantum Inf. Comput. 22(13 &14), 1110–1131 (2022)

    MathSciNet  Google Scholar 

  29. Teixeira da Silva, C.F., Posner, D., Portugal, R.: Walking on vertices and edges by continuous-time quantum walk. Quantum Inf. Process. 22(2), 93 (2023)

    Article  MathSciNet  ADS  Google Scholar 

  30. Portugal, R., Moqadam, J.K.: Implementation of continuous-time quantum walks on quantum computers. arXiv:2212.08889 (2022)

  31. Chen, Q.: PhD thesis, University of Waterloo, in preparation

Download references

Acknowledgements

We are indebted to Chris Godsil and Qiuting Chen for their insightful discussions, which significantly contributed to the formulation of Theorem 1 [31]. The work of P. Lugão was supported by CNPq grant number 140897/2020-8, and FAPERJ grant number E-26/202.351/2022. The work of R. Portugal was supported by FAPERJ grant number CNE E-26/200.954/2022, and CNPq grant numbers 308923/2019-7 and 409552/2022-4. The authors have no Conflict of interest to declare that are relevant to the content of this article.

Author information

Author notes

  1. Pedro H. G. Lugão and Renato Portugal have been contributed equally to this work.

Authors and Affiliations

  1. Celso Suckow da Fonseca Federal Center for Technological Education - CEFET/RJ, Rua do Imperador, Petrópolis, RJ 25620-003, Brazil

    Pedro H. G. Lugão

  2. National Laboratory of Scientific Computing - LNCC, Av. Getúlio Vargas, Petrópolis, RJ, 25651-075, Brazil

    Pedro H. G. Lugão & Renato Portugal

Authors
  1. Pedro H. G. Lugão
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Renato Portugal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pedro H. G. Lugão.

Ethics declarations

Conflict of interest

The authors declare that there is no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lugão, P.H.G., Portugal, R. Quantum search by continuous-time quantum walk on t-designs. Quantum Inf Process 23, 140 (2024). https://doi.org/10.1007/s11128-024-04355-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-024-04355-4

Keywords

Search

Navigation