[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

High-dimensional graphs convolution for quantum walks photonic applications

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

Quantum random walks represent a powerful tool for the implementation of various quantum algorithms. We consider a convolution problem for the graphs which provide quantum and classical random walks. We suggest a new method for lattices and hypercycle convolution that preserves quantum walk dynamics. Our method is based on the fact that some graphs represent a result of Kronecker’s product of line graphs. We support our methods by means of various numerical experiments that check quantum and classical random walks on hypercycles and their convolutions. Our findings may be useful for saving a significant number of qubits required for algorithms that use quantum walk simulation on quantum devices.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

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 used during this study are available within the article.

References

  1. Kac, M.: Random walk and the theory of Brownian motion. Am. Math. Mon. 54, 369–91 (1947)

    Article  MathSciNet  Google Scholar 

  2. Kutner, R., Masoliver, J.: The continuous time random walk, still trendy: fifty-year history, state of art and outlook. Eur. Phys. J. B 90, 50 (2017)

    Article  ADS  Google Scholar 

  3. Bartumeus, F., da Luz, M.G.E., Viswanathan, G.M., Catalan, J.: Animal search strategies: a quantitative random-walk analysis. Ecology 86(11), 3078–3087 (2005)

    Article  Google Scholar 

  4. Xia, F., Liu, J., Nie, H., Fu, Y., Wan, L., Kong, X.: Random walks: a review of algorithms and applications. IEEE Trans. Emerg. Top. Comput. Intell. 4(2), 95–107 (2019)

    Article  Google Scholar 

  5. Kempe, J.: Quantum random walks: an introductory overview. Contemp. Phys. 44(4), 307–327 (2003)

    Article  ADS  Google Scholar 

  6. Childs, A.M.: Universal computation by quantum walk. Phys. Rev. Lett. 102(18), 180501 (2009)

    Article  ADS  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  8. Ambainis, A.: Quantum walks and their algorithmic applications. Int. J. Quantum Inf. 1(04), 507–518 (2003)

    Article  Google Scholar 

  9. Madhu, A.K., Melnikov, A.A., Fedichkin, L.E., Alodjants, A.P., Lee, R.K.: Quantum walk processes in quantum devices. Heliyon 9(3), e13416 (2023)

    Article  Google Scholar 

  10. Portugal, R.: Quantum walks and search algorithms, vol. 19. Springer, New York (2013)

    Book  Google Scholar 

  11. Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., Lloyd, S.: Quantum machine learning. Nature 549(7671), 195–202 (2017)

    Article  ADS  Google Scholar 

  12. Melnikov, A., Kordzanganeh, M., Alodjants, A., Lee, R.K.: Quantum machine learning: from physics to software engineering. Adv. Phys. X 8(1), 2165452 (2023)

    Google Scholar 

  13. Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. In: Proceedings of the thirty-third annual ACM symposium on Theory of computing (pp. 37-49) (2001, July)

  14. Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proceedings of the thirty-third annual ACM symposium on Theory of computing (pp. 50-59) (2001, July)

  15. Solenov, D., Fedichkin, L.: Continuous-time quantum walks on a cycle graph. Phys. Rev. A 73(1), 012313 (2006)

    Article  ADS  MathSciNet  Google Scholar 

  16. Krovi, H., Brun, T.A.: Hitting time for quantum walks on the hypercube. Phys. Rev. A 73(3), 032341 (2006)

    Article  ADS  MathSciNet  Google Scholar 

  17. Kempe, J.: Discrete quantum walks hit exponentially faster. Probab. Theory Relat. Fields 133(2), 215–235 (2005)

    Article  MathSciNet  Google Scholar 

  18. Makmal, A., Zhu, M., Manzano, D., Tiersch, M., Briegel, H.J.: Quantum walks on embedded hypercubes. Phys. Rev. A 90(2), 022314 (2014)

    Article  ADS  Google Scholar 

  19. Santos, R.A.M., Portugal, R.: Quantum hitting time on the complete graph. Int. J. Quantum Inf. 8(05), 881–894 (2010)

    Article  Google Scholar 

  20. Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.A.: Exponential algorithmic speedup by a quantum walk. In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (pp. 59-68) (2003)

  21. Preskill, J.: Quantum Computing in the NISQ era and beyond. Quantum 2, 79 (2018)

    Article  Google Scholar 

  22. Melnikov, A.A., Fedichkin, L.E., Alodjants, A.: Predicting quantum advantage by quantum walk with convolutional neural networks. New J. Phys. 21(12), 125002 (2019)

    Article  MathSciNet  Google Scholar 

  23. Gurvitz, S.A., Fedichkin, L.E., Mozyrsky, D., Berman, G.P.: Relaxation and the Zeno effect in qubit measurements. Phys. Rev. Lett. 91, 066801 (2003)

    Article  ADS  Google Scholar 

  24. Melnikov, A.A., Fedichkin, L.E., Lee, R.K., Alodjants, A.P.: Machine learning transfer efficiencies for noisy quantum walks. Adv. Quantum Technol. 3(4), 1900115 (2020)

    Article  Google Scholar 

  25. Douglas, B.L., Wang, J.B.: Efficient quantum circuit implementation of quantum walks Phys. Rev. A 79, 052335 (2019)

    Article  Google Scholar 

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

  27. Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7, 193–209 (2008)

    Article  MathSciNet  Google Scholar 

  28. Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.H., Zhou, X.Q., Love, P.J., Aspuru-Guzik, A., O’Brien, J.L.: A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5(1), 4213 (2014)

    Article  ADS  Google Scholar 

  29. Perets, H.B., Lahini, Y., Pozzi, F., Sorel, M., Morandotti, R., Silberberg, Y.: Realization of quantum walks with negligible decoherence in waveguide lattices. Phys. Rev. Lett. 100(17), 170506 (2008)

    Article  ADS  Google Scholar 

  30. Perez-Leija, A., Keil, R., Kay, A., Moya-Cessa, H., Nolte, S., Kwek, L.C., Rodríguez-Lara, B.M., Szameit, A., Christodoulides, D.N.: Coherent quantum transport in photonic lattices. Phys. Rev. A 87(1), 012309 (2013)

    Article  ADS  Google Scholar 

  31. Tang, H., Di Franco, C., Shi, Z.Y., He, T.S., Feng, Z., Gao, J., Sun, Ke., Wang, C.Y., Lai, P.C., Xu, X.Y., Wang, Y., Qiao, L.F., Yang, A.L., Jin, X.M.: Experimental quantum fast hitting on hexagonal graphs. Nat. Photonics 12(12), 754–758 (2018)

    Article  ADS  Google Scholar 

  32. Maczewsky, L.J., Wang, K., Dovgiy, A.A., Miroshnichenko, A.E., Moroz, A., Ehrhardt, M., Heinrich, M., Christodoulides, D.N., Szameit, A., Sukhorukov, A.A.: Synthesizing multi-dimensional excitation dynamics and localization transition in one-dimensional lattices. Nat. Photonics 14(2), 76–81 (2020)

    Article  ADS  Google Scholar 

  33. Yu, S., Piao, X., Hong, J., Park, N.: Interdimensional optical isospectrality inspired by graph networks. Optica 3(8), 836–839 (2016)

    Article  ADS  Google Scholar 

  34. Dennis, E., Kitaev, A., Landahl, A., Preskill, J.: Topological quantum memory. J. Math. Phys. 43(9), 4452–4505 (2002)

    Article  ADS  MathSciNet  Google Scholar 

  35. Pedrocchi, F.L., Hutter, A., Wootton, J.R., Loss, D.: Enhanced thermal stability of the toric code through coupling to a bosonic bath. Phys. Rev. A 88, 062313 (2013)

    Article  ADS  Google Scholar 

  36. Lu, D., Biamonte, J.D., Li, J., Li, H., Johnson, T.H., Bergholm, V., Faccin, M., Zimborás, A., Laflamme, R., Baugh, J., Lloyd, S.: Chiral quantum walks. Phys. Rev. A 93(4), 042302 (2016)

    Article  ADS  Google Scholar 

  37. Melnikov, A.A., Alodjants, A.P., Fedichkin, L.E.: Tunneling in double-layer optical waveguides as quantum walks on graphs. Proc. Steklov Inst. Math. 313, 142 (2021)

    Article  MathSciNet  Google Scholar 

  38. Skryabin, N., Kalinkin, A., Dyakonov, I., Kulik, S.: Femtosecond laser written depressed-cladding waveguide 2 \(\times \) 2, 1 \(\times \) 2, and 3 \(\times \) 3 directional couplers in Tm3+:YAG crystal. Micromachines 11, 1 (2020)

    Article  Google Scholar 

  39. Chen, F., Aldana, J.: Optical waveguides in crystalline dielectric materials produced by femtosecond-laser micromachining. Laser Photonics Rev. 8, 251 (2014)

    Article  ADS  Google Scholar 

  40. Johansson, J.R., Nation, P.D., Nori, F.: QuTiP: an open-source Python framework for the dynamics of open quantum systems. Comput. Phys. Commun. 183(8), 1760–1772 (2012)

    Article  ADS  Google Scholar 

  41. Manzano, D.A.: A short introduction to the Lindblad master equation. AIP Adv. 10, 025106 (2020)

    Article  ADS  Google Scholar 

Download references

Acknowledgements

The results of this work related to Sect.2 were funded by the Ministry of Science and Higher Education of the Russian Federation and South Ural State University (Agreement No. 075-15-2022-1116). Studies described in Sects. 3 and 4 are supported by project No. 2019-1339 (Goszadanie) of the Ministry of Science and Higher Education of the Russian Federation.

Author information

Author notes

  1. Roman Abramov, Leonid Fedichkin, Dmitry Tsarev and Alexander Alodjants have contributed equally to this work.

Authors and Affiliations

  1. Technical University of Munich, Arcisstraße 21, 80333, Munich, Germany

    Roman Abramov

  2. Valiev Institute of Physics and Technology, Russian Academy of Sciences, Moscow, Russia, 117218

    Leonid Fedichkin

  3. Institute of Advanced Data Transfer, ITMO University, Kronverksky Pr. 49, bldg. A, St. Petersburg, Russia, 197101

    Dmitry Tsarev & Alexander Alodjants

  4. Quantum Light Engineering Laboratory, Institute of Natural and Exact Sciences, South Ural State University, Lenin Av., 76, Chelyabinsk, Russia, 454080

    Dmitry Tsarev

Authors
  1. Roman Abramov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Leonid Fedichkin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dmitry Tsarev
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Alexander Alodjants
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Roman Abramov or Alexander Alodjants.

Ethics declarations

Conflict of interest

The authors have no conflicts of interest to declare that are relevant to the content of this article.

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

Abramov, R., Fedichkin, L., Tsarev, D. et al. High-dimensional graphs convolution for quantum walks photonic applications. Quantum Inf Process 23, 175 (2024). https://doi.org/10.1007/s11128-024-04351-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-024-04351-8

Keywords

Search

Navigation