Abstract
Recently, the quaternionic quantum walk was formulated by the first author as a generalization of discrete-time quantum walks. We deal with the right eigenvalue problem of quaternionic matrices in order to study spectra of the transition matrix of a quaternionic quantum walk. The way to obtain all the right eigenvalues of a quaternionic matrix is given. From the unitary condition on the transition matrix of a quaternionic quantum walk, we deduce some remarkable properties of it. Our main results determine all the right eigenvalues of the quaternionic quantum walk by using those of the corresponding weighted matrix. In addition, we give some examples of quaternionic quantum walks and their right eigenvalues.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Adler, S.L.: Quaternion Quantum Mechanics and Quantum Fields. Oxford University Press, Cambridge (1995)
Altmann, S.L.: Rotations, Quaternions, and Double Groups. Dover Publications, Mineola (2005)
Ambainis, A.: Quantum walks and their algorithmic applications. Int. J. Quantum Inf. 01, 507 (2003)
Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 37–49 (2001)
Aslaksen, H.: Quaternionic determinants. Math. Intell. 18, 57–65 (1996)
Bass, H.: The Ihara-Selberg zeta function of a tree lattice. Int. J. Math. 3, 717–797 (1992)
Birkhoff, G., von Neumann, J.: The logic of quantum mechanics. Ann. Math. 37, 823–843 (1936)
Brenner, J.L.: Matrices of quaternions. Pac. J. Math. 1, 329–335 (1951)
Cantero, M.J., Grunbaum, F.A., Moral, L., Velazquez, L.: The CGMV method for quantum walks. Quantum Inf. Process. 11, 1149–1192 (2012)
Conway, J.H., Smith, D.: On Quaternions and Octonions. A K Peters, Ltd, Natick (2003)
De Leo, S., Scolarici, G., Solombrino, L.: Quaternionic eigenvalue problem. J. Math. Phys. 43, 5815–5829 (2002)
Emms, D., Hancock, E.R., Severini, S., Wilson, R.C.: A matrix representation of graphs and its spectrum as a graph invariant. Electr. J. Comb. 13, R34 (2006)
Finkelstein, D., Jauch, J.M., Speiser, D.: Notes on quaternion quantum mechanics, CERN report 59–7 (1959). In: Hooker, C. (ed.) Logico-Algebraic Approach to Quantum Mechanics II. Reidel, Dordrecht (1979)
Foata, D., Zeilberger, D.: A combinatorial proof of Bass’s evaluations of the Ihara-Selberg zeta function for graphs. Trans. Am. Math. Soc. 351, 2257–2274 (1999)
Godsil, C., Guo, K.: Quantum walks on regular graphs and eigenvalues. Electr. J. Comb. 18, P165 (2011)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC), May 1996, pp. 212–219 (1996)
Hashimoto, K.: Zeta functions of finite graphs and representations of \(p\)-adic groups. In Adv. Stud. Pure Math., vol. 15, pp. 211–280. Academic Press, New York (1989)
Huang, L., So, W.: On left eigenvalues of a quaternionic matrix. Linear Algebra Appl. 323, 105–116 (2001)
Hall, H.T., Severini, S.: Locality for quantum systems on graphs depends on the number field. arXiv:1204.3681v2 [quant-ph] (2013)
Ihara, Y.: On discrete subgroups of the two by two projective linear group over \(p\)-adic fields. J. Math. Soc. Jpn. 18, 219–235 (1966)
Kempe, J.: Quantum random walks—an introductory overview. Contemp. Phys. 44, 307–327 (2003)
Konno, N.: Quantum walks. In: Franz, U., Schürmann, M. (eds.) Quantum Potential Theory. Lecture Notes in Mathematics, vol. 1954, pp. 309–452. Springer, Heidelberg (2008)
Konno, N.: Quaternionic quantum walks. Quantum Stud. Math. Found 2, 63–76 (2015)
Konno, N., Sato, I.: On the relation between quantum walks and zeta functions. Quantum Inf. Process. 11, 341–349 (2012)
Kotani, M., Sunada, T.: Zeta functions of finite graphs. J. Math. Sci. U Tokyo 7, 7–25 (2000)
Lee, H.C.: Eigenvalues and canonical forms of matrices with quaternion coefficients. Proc. R. Ir. Acad. Sect. A 52, 253–260 (1949)
Manouchehri, K., Wang, J.: Physical Implementation of Quantum Walks. Springer, Berlin (2013)
Portugal, R.: Quantum Walks and Search Algorithms. Springer, Berlin (2013)
Ren, P., Aleksic, T., Emms, D., Wilson, R.C., Hancock, E.R.: Quantum walks, Ihara zeta functions and cospectrality in regular graphs. Quantum Inf. Process. 10, 405–417 (2011)
Sato, I.: A new Bartholdi zeta function of a graph. Int. J. Algebra 1, 269–281 (2007)
Serre, J.-P.: Trees. Springer, New York (1980)
Stark, H.M., Terras, A.A.: Zeta functions of finite graphs and coverings. Adv. Math. 121, 124–165 (1996)
Sunada, T.: \(L\)-functions in geometry and some applications. In Lecture Notes in Math., vol. 1201, pp. 266–284. Springer, New York (1986)
Sunada, T.: Fundamental Groups and Laplacians. Kinokuniya, Tokyo (1988). (in Japanese)
Venegas-Andraca, S.E.: Quantum walks: a comprehensive review. Quantum Inf. Process. 11, 1015–1106 (2012)
Watrous, J.: Quantum simulations of classical random walks and undirected graph connectivity. J. Comput. Syst. Sci. 62(2), 376–391 (2001)
Zhang, F.: Quaternions and matrices of quaternions. Linear Algebra Appl. 251, 21–57 (1997)
Acknowledgments
The first author was partially supported by the Grant-in-Aid for Scientific Research (C) of Japan Society for the Promotion of Science (Grant No. 21540116). The third author is partially supported by the Grant-in-Aid for Scientific Research (C) of Japan Society for the Promotion of Science (Grant No. 19540154). We are grateful to K. Tamano, S. Matsutani and Y. Ide for some valuable comments on this work. We would also like to thank the referees for their valuable comments which helped to improve the manuscript.
Author information
Authors and Affiliations
Corresponding author
Appendix: Quaternionic quantum mechanics
Appendix: Quaternionic quantum mechanics
In this appendix, we review the general framework of quaternionic quantum mechanics in this section. Most of materials in this section are detailed in [1]. The origin of quaternionic quantum mechanics goes back to the axiomatization of quantum mechanics by Birkhoff and von Neumann in 1930s [7]. They established the foundation for quantum mechanics by using a logical and axiomatic method, so-called propositional calculi, which is equivalent to the Hilbert space approach for practical purposes. The model proposed by them is valid for various fields such as real, complex and quaternion number systems. In this way, the possibility of quaternionic quantum mechanics was first pointed out in [7]. After that, the subject was studied further by Finkelstein, Jauch and Speiser [13], and more recently by Adler and others. One significant motivation of studying quaternionic quantum mechanics is that physical reality might be described by quaternionic quantum system at the fundamental level, and this dynamics is described asymptotically by the (ordinary) quantum field theory at the level of all presently known physical phenomena.
The states of quaternionic quantum mechanics are described by vectors of a quaternionic Hilbert space \(\mathscr {H}_{\mathbb {H}}\) which is defined by the following axioms:
-
(I)
\(\mathscr {H}_{\mathbb {H}}\) is a right \(\mathbb {H}\)-vector space.
-
(II)
There exists a scalar product that is a map \((\ ,\ ) : \mathscr {H}_{\mathbb {H}}{\times }\mathscr {H}_{\mathbb {H}}{\longrightarrow }\mathbb {H}\) with the properties:
$$\begin{aligned} \begin{aligned} (\mathbf{f},\,\mathbf{g})^*&=(\mathbf{g},\,\mathbf{f}),\\ (\mathbf{f},\,\mathbf{f})&\text { is nonnegative real number, and } (\mathbf{f},\,\mathbf{f})=0{\;\Leftrightarrow \;}{} \mathbf{f}=0,\\ (\mathbf{f},\,\mathbf{g}+\mathbf{h})&=(\mathbf{f},\,\mathbf{g})+(\mathbf{f},\,\mathbf{h})\\ (\mathbf{f},\,\mathbf{g}{\lambda })&=(\mathbf{f},\,\mathbf{g})\lambda \quad \text {for every} \,\lambda {\in }\mathbb {H}. \end{aligned} \end{aligned}$$\(\Vert \mathbf{f}\Vert \) denotes \(\sqrt{(\mathbf{f},\,\mathbf{f})}\) and is called the norm of \(\mathbf{f}\).
-
(III)
\(\mathscr {H}_{\mathbb {H}}\) is separable and complete.
In the same way as in (complex) quantum mechanics, the bra-ket notation is used in quaternionic quantum mechanics. Ket states are denoted by \(|\mathbf{f}{\rangle }\) that satisfy \(|\mathbf{f}{\lambda }{\rangle }=|\mathbf{f}{\rangle }\lambda \) for every \(\lambda {\in }\mathbb {H}\). Bra states \({\langle }{} \mathbf{f}|\) are defined as their adjoints in a matrix sense so that \({\langle }{} \mathbf{f}|=|\mathbf{f}{\rangle }^{\dagger }\) where \(|\mathbf{f}{\rangle }^{\dagger }\) denotes the adjoint of \(|\mathbf{f}{\rangle }\). It follows that \({\langle }{} \mathbf{f}{\lambda }|={\lambda }^*{\langle }{} \mathbf{f}|\), and the scalar product can be presented as \((\mathbf{f},\,\mathbf{g})={\langle }{} \mathbf{f}|\mathbf{g}{\rangle }\). \({\langle }{} \mathbf{f}|\mathbf{g}{\rangle }\) is called the inner product or probability amplitude. If \(\mathscr {H}_{\mathbb {H}}\) is N-dimensional, then \(|\mathbf{f}{\rangle }\) and \({\langle }{} \mathbf{f}|\) are presented as follows:
and the scalar product is given by
For a probability amplitude \({\langle }{} \mathbf{g}|\mathbf{f}{\rangle }\), one associates a probability:
For any \(\omega {\;\in \;}\mathbb {H}\) such that \(|\omega |=1\), \(|{\langle }\mathbf{g}|\mathbf{f}{\omega }{\rangle }|^2=|{\langle }{} \mathbf{g}|\mathbf{f}{\rangle }|^2\). Hence, \(P_{\mathbf{g}(\mathbf{f}{\omega })}=P_{\mathbf{g}\mathbf{f}}\) for all \(\mathbf{g}{\;\in \;}\mathscr {H}_{\mathbb {H}}\). Thus, physical states bijectively correspond to sets of unit rays of \(\mathscr {H}_{\mathbb {H}}\) of the form:
Operators \(\mathbf{U}\) on \(\mathscr {H}_{\mathbb {H}}\) are assumed to act from the left as in \(\mathbf{U}|\mathbf{f}{\rangle }\) and satisfy
for all \(\lambda {\;\in \;}\mathbb {H}\). For any operator \(\mathbf{U}\), the adjoint operator \(\mathbf{U}^{\dagger }\) is defined by \((\mathbf{f},\,\mathbf{U}{} \mathbf{g})=(\mathbf{U}^{\dagger }{} \mathbf{f},\,\mathbf{g})\) for arbitrary \(\mathbf{f},\,\mathbf{g}\) in suitable domains. An operator \(\mathbf{U}\) is said to be self-adjoint if \(\mathbf{U}^{\dagger }=\mathbf{U}\) holds and unitary if \(\mathbf{U}{} \mathbf{U}^{\dagger }=\mathbf{U}^{\dagger }{} \mathbf{U}=\mathbf{1}\) holds. If \(\mathscr {H}_{\mathbb {H}}\) is finite dimensional, unitary operators are unitary as quaternionic matrices. In analogy with the complex case, right eigenvalues of the self-adjoint operator must be real.
In order to explain the dynamics of quaternionic quantum mechanics, we introduce the time evolution operator. We assume that time evolution preserves transition probabilities. Precisely, for arbitrary states \(|\mathbf{f}(t){\rangle },|\mathbf{g}(t){\rangle }\) at time t and \(|\mathbf{f}(t'){\rangle },|\mathbf{g}(t'){\rangle }\) at time \(t'=t+{\delta }t\), \(|{\langle }{} \mathbf{f}(t)|\mathbf{g}(t){\rangle }|=|{\langle }{} \mathbf{f}(t')|\mathbf{g}(t'){\rangle }|\) holds. Choosing appropriate quaternionic phases, we obtain that there exists a unitary operator \(\mathbf{U}(t',t)\) such that
\(\mathbf{U}(t',t)\) is called the time evolution operator and (A.2) is called the time evolution equation. If \(\mathscr {H}_{\mathbb {H}}\) is N-dimensional, then \(\mathbf{U}(t',t)\) represent as an \(N{\times }N\) quaternionic unitary matrix.
(A.2) requires a special choice of ray representative \(|\mathbf{f}(t){\rangle }\). From (A.1), general ray representatives can be expressed as \(|\mathbf{f}(t){\omega _\mathbf{f}}(t){\rangle }\) where \({\omega _\mathbf{f}}(t)\) is an arbitrary quaternion of norm one. Then, we have
where \(u(t',t)={\omega _\mathbf{f}}(t)^*{\omega _\mathbf{f}}(t')\). We notice that \(\mathbf{U}(t',t)\) and \(u(t',t)\) satisfy \(\mathbf{U}(t,t)=\mathbf{1}\) and \(u(t,t)=1\), respectively. Unlike the case of complex quantum mechanics, \(|\mathbf{f}(t){\omega _\mathbf{f}}(t){\rangle }\) and \(u(t',t)\) do not mutually commute. Hence, we cannot incorporate \(u(t',t)\) into the time evolution operator in the case of general ray representatives. Thus, we must keep in mind that when we operate the physical states in quaternionic quantum mechanics, we are making a special choice of ray representative.
We mention briefly the relationship between quaternionic and complex quantum mechanics. For the sake of simplicity, \(\mathscr {H}_{\mathbb {H}}\) is assumed to be N-dimensional. Then, \(\mathbf{U}(t',t)\) is an \(N{\times }N\) quaternionic unitary matrix. \(\mathbf{U}(t',t)\) has the symplectic decomposition \(\mathbf{U}(t',t)=\mathbf{U}^S(t',t)+j\mathbf{U}^P(t',t)\). Let \(|\mathbf{f}(t){\rangle }={}^{T}(f_1(t)\,f_2(t)\,{\ldots }\,f_N(t)){\;\in \;}\mathscr {H}_{\mathbb {H}}\) and \(f_{\ell }(t)=f_{\ell }^S(t)+jf_{\ell }^P(t)\) be the symplectic decomposition. Then, \(|\mathbf{f}(t){\rangle }\) has the symplectic decomposition \(|\mathbf{f}(t){\rangle }=|\mathbf{f}^S(t){\rangle }+j|\mathbf{f}^P(t){\rangle }\) where \(|\mathbf{f}^S(t){\rangle }={}^{T}(f_1^S(t)\,f_2^S(t)\,{\ldots }\,f_N^S(t))\) and \(|\mathbf{f}^P(t){\rangle }={}^{T}(f_1^P(t)\,f_2^P(t)\,{\ldots }\,f_N^P(t))\) are the simplex part and the perplex part, respectively. Substituting these symplectic decompositions into (A.2), we have the following two-component complex time evolution equation:
Thus, the quaternionic time evolution equation can be written equivalently as a two-component complex time evolution equation. Nevertheless, quaternionic quantum mechanics is not a mere translation of complex quantum mechanics. Let \({\langle }\mathbf{f}(t)|\mathbf{g}(t){\rangle }= {\langle }{} \mathbf{f}(t)|\mathbf{g}(t){\rangle }^S+j{\langle }{} \mathbf{f}(t)|\mathbf{g}(t){\rangle }^P\) be the symplectic decomposition of the probability amplitude where
Then, the probability is given by
in quaternionic quantum mechanics. On the other hand, for the two-component complex time evolution equation (A.3), the probability amplitude is given by
Hence, probabilities in (A.2) are not equal to those of corresponding complex quantum mechanical system (A.3), and the two systems are inequivalent as quantum mechanical systems.
Finally, we remark on physical relevance of quaternionic quantum physics without details. In quaternionic quantum mechanics, it is known that the S-matrix is always a complex matrix for appropriate ray representative choices for the states. Therefore, the asymptotic dynamics for quaternionic quantum mechanics can be viewed as the dynamics of an effective complex quantum mechanics. This suggests that quaternionic quantum systems may play a role as an underlying dynamics for complex quantum systems.
Further arguments on the relationship between quaternionic quantum mechanics and complex quantum mechanics can be found in [1].
Rights and permissions
About this article
Cite this article
Konno, N., Mitsuhashi, H. & Sato, I. The discrete-time quaternionic quantum walk on a graph. Quantum Inf Process 15, 651–673 (2016). https://doi.org/10.1007/s11128-015-1205-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11128-015-1205-8