**59**, 199-216 (2007)

https://doi.org/10.1140/epjb/e2007-00281-5

## Investigation of continuous-time quantum walk by using Krylov subspace-Lanczos algorithm

^{1}
Department of Theoretical Physics and Astrophysics, Tabriz University, Tabriz, 51664, Iran

^{2}
Institute for Studies in Theoretical Physics and Mathematics, Tehran, 19395-1795, Iran

^{3}
Research Institute for Fundamental Sciences, Tabriz, 51664, Iran

^{4}
Department of Electrical Engineering, Sharif University of Technology, Azadi Ave., Tehran, Iran

Corresponding authors: ^{a}
jafarizadeh@tabrizu.ac.ir
- ^{b}
sofiani@tabrizu.ac.ir
- ^{c}
shsalimi@tabrizu.ac.ir
- ^{d}
jafarizadeh@ee.sharif.edu

Received:
9
March
2007

Published online:
17
October
2007

In papers [Jafarizadehn and Salimi, Ann. Phys. **322**, 1005 (2007) and J. Phys. A: Math. Gen. **39**, 13295 (2006)], the amplitudes of continuous-time quantum
walk (CTQW) on graphs possessing quantum decomposition (QD graphs)
have been calculated by a new method based on spectral
distribution associated with their adjacency matrix. Here in this
paper, it is shown that the CTQW on any arbitrary graph can be
investigated by spectral analysis method, simply by using Krylov
subspace-Lanczos algorithm to generate orthonormal bases of
Hilbert space of quantum walk isomorphic to orthogonal
polynomials. Also new type of graphs possessing generalized
quantum decomposition (GQD) have been introduced, where this is
achieved simply by relaxing some of the constrains imposed on QD
graphs and it is shown that both in QD and GQD graphs, the unit
vectors of strata are identical with the orthonormal basis
produced by Lanczos algorithm. Moreover, it is shown that
probability amplitude of observing the walk at a given vertex is
proportional to its coefficient in the corresponding unit vector
of its stratum, and it can be written in terms of the amplitude of
its stratum. The capability of Lanczos-based algorithm for
evaluation of CTQW on graphs (GQD or non-QD types), has been
tested by calculating the probability amplitudes of quantum walk
on some interesting finite (infinite) graph of GQD type and finite
(infinite) path graph of non-GQD type, where the asymptotic
behavior of the probability amplitudes at the limit of the large
number of vertices, are in agreement with those of central limit
theorem of [Phys. Rev. E **72**, 026113 (2005)]. At the end, some applications of the
method such as implementation of quantum search algorithms,
calculating the resistance between two nodes in regular networks
and applications in solid state and condensed matter physics, have
been discussed, where in all of them, the Lanczos algorithm,
reduces the Hilbert space to some smaller subspaces and the
problem is investigated in the subspace with maximal dimension.

PACS: 03.65.Ud – Entanglement and quantum nonlocality

*© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2007*