TY - JOUR

T1 - Up and down Grover walks on simplicial complexes

AU - Luo, Xin

AU - Tate, Tatsuya

N1 - Funding Information:
The first author was supported by China Scholarship Council to study at Tohoku University for one year. The second author is partially supported by JSPS Grant-in-Aid for Scientific Research, grant no. 25400068 and no. 15H02055 .
Publisher Copyright:
© 2018 Elsevier Inc.

PY - 2018/5/15

Y1 - 2018/5/15

N2 - Notions of up and down Grover walks on simplicial complexes are proposed and their properties are investigated. These are abstract Szegedy walks, which is a special kind of unitary operators on a Hilbert space. The operators introduced in the present paper are usual Grover walks on graphs defined by using combinatorial structures of simplicial complexes. But the shift operators are modified so that it can contain information of orientations of each simplex in the simplicial complex. It is well-known that the spectral structures of this kind of unitary operators are almost determined by its discriminant operators. It has strong relationship with combinatorial Laplacian on simplicial complexes and geometry, even topology, of simplicial complexes. In particular, theorems on a relation between spectrum of down discriminants and orientability, on a relation between symmetry of spectrum of discriminants and combinatorial structure of simplicial complex are given. Some examples, both of finite and infinite simplicial complexes, are also given. Finally, some aspects of finding probability and stationary measures are discussed.

AB - Notions of up and down Grover walks on simplicial complexes are proposed and their properties are investigated. These are abstract Szegedy walks, which is a special kind of unitary operators on a Hilbert space. The operators introduced in the present paper are usual Grover walks on graphs defined by using combinatorial structures of simplicial complexes. But the shift operators are modified so that it can contain information of orientations of each simplex in the simplicial complex. It is well-known that the spectral structures of this kind of unitary operators are almost determined by its discriminant operators. It has strong relationship with combinatorial Laplacian on simplicial complexes and geometry, even topology, of simplicial complexes. In particular, theorems on a relation between spectrum of down discriminants and orientability, on a relation between symmetry of spectrum of discriminants and combinatorial structure of simplicial complex are given. Some examples, both of finite and infinite simplicial complexes, are also given. Finally, some aspects of finding probability and stationary measures are discussed.

KW - Combinatorial Laplacian

KW - Grover walks

KW - Simplicial complex

UR - http://www.scopus.com/inward/record.url?scp=85041551519&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041551519&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2018.01.036

DO - 10.1016/j.laa.2018.01.036

M3 - Article

AN - SCOPUS:85041551519

SN - 0024-3795

VL - 545

SP - 174

EP - 206

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -