Skip to main content
SpringerLink
Log in

Localization of the Grover Walks on Spidernets and Free Meixner Laws

  • Published:
Communications in Mathematical Physics Aims and scope Submit manuscript

Abstract

A spidernet is a graph obtained by adding large cycles to an almost regular tree and considered as an example having intermediate properties of lattices and trees in the study of discrete-time quantum walks on graphs. We introduce the Grover walk on a spidernet and its one-dimensional reduction. We derive an integral representation of the n-step transition amplitude in terms of the free Meixner law which appears as the spectral distribution. As an application we determine the class of spidernets which exhibit localization. Our method is based on quantum probabilistic spectral analysis of graphs.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Ahlbrecht A., Scholz V.B., Werner A.H.: Disordered quantum walks in one lattice dimension. J. Math. Phys. 52, 102201 (2011)

    Article  MathSciNet  ADS  Google Scholar 

  2. Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. In: Proc. 33rd Annual ACM Symp. Theory of Computing, New York: ACM, 2001, pp. 37–49

  3. Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proc. 16th ACM-SIAM SODA Philadelphia PA: SIAM, 2005, pp. 1099–1108

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

    Article  MATH  Google Scholar 

  5. Anshelevich M.: Free Meixner states. Commun. Math. Phys. 276, 863–899 (2007)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  6. Bo zejko M., Bryc W.: On a class of free Lévy laws related to regression problem. J. Funct. Anal. 236, 59–77 (2006)

    Article  MathSciNet  Google Scholar 

  7. Cantero M.J., Grünbaum F.A., Moral L., Velázquez L.: Matrix-valued Szegő polynomials and quantum random walks. Commun. Pure Appl. Math. 63, 464–507 (2010)

    MATH  Google Scholar 

  8. Cantero M.J., Grünbaum F.A., Moral L., Velazquez L.: One-dimensional quantum walks with one defect. Rev. Math. Phys. 24, 1250002 (2012)

    Article  MathSciNet  Google Scholar 

  9. Chihara, T.S.: An Introduction to Orthogonal Polynomials. New York: Dover, 2011

  10. Chisaki K., Hamada M., Konno N., Segawa E.: Limit theorems for discrete-time quantum walks on trees. Interdiscip. Inform. Sci. 15, 423–429 (2009)

    MathSciNet  MATH  Google Scholar 

  11. Deift, P.A.: Orthogonal Polynomials and Random Matrices: A Riemann-Hilbert Approach, Courant Lecture Notes in Mathematics, Vol. 3, Povidence, RI: Amer. Math. Soc., 1999

  12. Gnutzmann S., Smilansky U.: Quantum graphs: Applications to quantum chaos and universal spectral statistics. Adv. Phys. 55, 527–625 (2006)

    Article  ADS  Google Scholar 

  13. Gudder, S.P.: Quantum Probability. London-New York: Academic Press, 1988

  14. Grünbaum, F.A., Velázquez, L., Werner, A.H., Werner, R.F.: Recurrence for discrete time unitary evolutions. Commun. Math. Phys. 320(2), 543–569 (2013)

    Google Scholar 

  15. Hora, A., Obata, N.: Quantum Probability and Spectral Analysis of Graphs. Berlin-Heidelberg-New York: Springer, 2007

  16. Igarashi, D., Obata, N.: Asymptotic spectral analysis of growing graphs: Odd graphs and spidernets. Banach Center Publications 73, 2006, Warsaw: Banach Center, pp. 245–265

  17. Inui N., Konno N., Segawa E.: One-dimensional three-state quantum walk. Phys. Rev. E 72, 056112 (2005)

    Article  ADS  Google Scholar 

  18. Joye A., Merkli M.: Dynamical localization of quantum walks in random environments. J. Stat. Phys. 140, 1023–1053 (2010)

    Article  MathSciNet  Google Scholar 

  19. Karski M., Föster L., Choi J.-M., Steffen A., Alt W., Meschede D., Widera A.: Quantum walk in position space with single optically trapped atoms. Science 325, 174–177 (2009)

    Article  ADS  Google Scholar 

  20. Kesten H.: Symmetric random walks on groups. Trans. Amer. Math. Soc. 92, 336–354 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  21. Konno N.: Quantum random walks in one dimension. Quantum Inf. Proc. 1, 345–354 (2002)

    Article  MathSciNet  Google Scholar 

  22. Konno N.: A new type of limit theorems for the one-dimensional quantum random walk. J. Math. Soc. Japan 57, 1179–1195 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  23. Konno, N.: Quantum walks. In: “Quantum Potential Theory, U. Franz, M. Schürmann, eds.,” Lecture Notes in Math. 1954, Berlin-Heidelberg-New York: Springer, 2008, pp. 309–452

  24. Konno N., Łuczak T., Segawa E.: Limit measures of inhomogeneous discrete-time quantum walks in one dimension. Quantum Inf. Proc. 12, 33–53 (2013)

    Article  ADS  MATH  Google Scholar 

  25. Konno N., Segawa E.: Localization of discrete-time quantum walks on a half line via the CGMV method. Quant.Inf. Comp. 11, 0485–0495 (2011)

    MathSciNet  Google Scholar 

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

    Article  ADS  MATH  Google Scholar 

  27. Obata N.: One-mode interacting Fock spaces and random walks on graphs. Stochastics 84, 383–392 (2012)

    MathSciNet  MATH  Google Scholar 

  28. Saitoh N., Yoshida H.: The infinite divisibility and orthogonal polynomials with a constant recursion formula in free probability theory. Probab. Math. Stat. 21, 159–170 (2001)

    MathSciNet  MATH  Google Scholar 

  29. Segawa, E.: Localization of quantum walks induced by recurrence properties of random walks. Theoretical and mathematical aspects of the discrete time quantum walk. J. Commun. Math. Phys. Nanosci. (2013, in press)

  30. Shikano Y., Katsura H.: Localization and factuality in inhomogeneous quantum walks with self-duality. Phys. Rev. E 82, 031122 (2010)

    Article  MathSciNet  ADS  Google Scholar 

  31. Sunada T., Tate T.: Asymptotic behavior of quantum walks on the line. J. Funct. Anal. 262, 2608–2645 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  32. Szegedy, M.: Quantum speed-up of Markov chain based algorithms, In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS’04), New Brunswick, NS: IEEE, 2004, pp. 32–41

  33. Urakawa H.: The Cheeger constant, the heat kernel, and the Green kernel of an infinite graph. Monatsh. Math. 138, 225–237 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  34. Venegas-Andraca, S.E.: Quantum Walks for Computer Scientists. San Rafael, CA: Morgan and Claypool, 2008

  35. Watabe K., Kobayashi N., Katori M., Konno N.: Limit distributions of two-dimensional quantum walks. Phys. Rev. A 77, 062331 (2008)

    Article  ADS  Google Scholar 

  36. Watrous J.: Quantum simulations of classical random walks and undirected graph connectivity. J. Comp. Syst. Sci. 62, 376–391 (2001)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, Faculty of Engineering, Yokohama National University, Yokohama, 240-8501, Japan

    Norio Konno

  2. Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579, Japan

    Nobuaki Obata & Etsuo Segawa

Authors
  1. Norio Konno
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nobuaki Obata
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Etsuo Segawa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Etsuo Segawa.

Additional information

Communicated by M. Aizenman

Rights and permissions

Reprints and permissions

About this article

Cite this article

Konno, N., Obata, N. & Segawa, E. Localization of the Grover Walks on Spidernets and Free Meixner Laws. Commun. Math. Phys. 322, 667–695 (2013). https://doi.org/10.1007/s00220-013-1742-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00220-013-1742-x

Keywords

Search

Navigation