0. Grover Grover positive support Grover Ihara weighted Grover Ihara [19] P GL(2, F ) (F : p- ) p- Selberg (Ihara-Selberg Ihara ) 1980 Serre [

Transcription

1 Grover Grover positive support Grover Ihara weighted Grover Ihara [19 P GL(2, F ) (F : p- ) p- Selberg (Ihara-Selberg Ihara ) 198 Serre [32 Ihara 1986 Sunada [36,37 Ihara Ihara Hashimoto [ Ihara 199 Hashimoto [17 edge matrix Ihara 1992 Bass [5 Ihara growth 1999 Bartholdi [4 Bartholdi 11 Ihara ζ(s) = n=1 1 n s, s = σ + it C ζ(s) = p (1 p s ) 1, p : prime, reduced cycles Ihara cycle cycles 1

2 G = (V, E) V E V = V (G) E = E(G) V u, v uv = {u, v} ( ) G uv (u, v), (v, u) V V symmetric digraph D G = (V, D(G)) (u, v) arc G arcs D(G) = {(u, v), (v, u) uv E(G)} e = (u, v) D(G) u, v e, u = o(e), v = t(e) e 1 = (v, u) e = (u, v) inverse G path P = (e 1,, e n ) e i D(G), t(e i ) = o(e i+1 )(1 i n 1) e 1,, e n n P P = n o(p ) = o(e 1 ), t(p ) = t(e n ) P (o(p ), t(p ))-path path P = (e 1,, e n ) backtracking ( bump) e 1 i+1 = e i o(e 1 ) = t(e n ) path P = (e 1,, e n ) cycle cycle C 1 = (e 1,, e n ) C 2 = (e 1,, e n) k e i = e i+k mod n [C C cycle B r B r B r cycle cycle C reduced C C 2 backtracking cycle C prime cycle B C B r G prime, reduced cycle G v G π 1 (G, v) 1 (Sunada) G Ihara : Z(G, u) = Z G (u) = [C(1 u C ) 1 [C G prime, reduced cycle C C ([36 ) u C u 12 Ihara G n v 1,, v n G A(G) = (a ij ) 1 i,j n v i v j E(G)( (v i, v j ) D(G)) a ij = 1, a ij = v i deg G v i = {v j v i v j E(G)} G v deg G v = k( ) G k- Ihara ([38 ) 1 (Ihara) G (q + 1)- G Ihara : Z G (u) = (1 u 2 ) (m n) det(i n A(G)u + qu 2 I n ) 1 = exp( k 1 N k k uk ) m = E(G), n = V (G) N k G k reduced cycles 13 Ihara G n v 1,, v n m n n D = (d ij ) d ii = deg G v i 2m 2m B = B(G) = ((B) e,f ) e,f D(G) and J = J (G) = ((J ) e,f ) e,f D(G) (B) e,f = { 1 if t(e) = o(f), otherwise, (J ) e,f = { 1 if f = e 1, otherwise 2

3 B J G edge matrix 2 (Hashimoto; Bass) G Z G (u) 1 = det(i 2m u(b J )) = (1 u 2 ) m n det(i n ua(g) + u 2 (D I n )) = exp( k 1 m = E(G), n = V (G) N k G k reduced cycles N k k uk ) cycle edge matrix Ihara Remark G Ihara R ( (G) 1) 1 < R < (δ(g) 1) 1 ([23 ) (G),δ(G) G Lubotzky [24, Stark and Terras [35 Hashimoto [17, Northshield [29 Hashimoto [18, Terras [39 15 weighted weighted Hashimoto [16 Stark and Terras [34 G arc G D(G) = {e 1,, e m, e m+1,, e 2m }(e m+i = e 1 i (1 i m)) 2m u =: (u 1,, u 2m ) cycle C = (e i1,, e ik ) g(c) = u i1 u ik G edge ζ G (u) ζ G (u) = [C (1 g(c)) 1 [C G prime, reduced cycle 3 (Stark and Terras) m G ζ G (u) 1 = det(i 2m (B J )U) = det(i 2m U(B J )) U = diag(u 1,, u 2m ) u 1,, u 2m Mizuno and Sato [27 G u k = w(e k )t G weighted G V (G) = {v 1,, v n } n n W = (w ij ) 1 i,j n (v i, v j ) D(G) ij w ij w ij = W = W(G) G weighted matrix w(v i, v j ) = w ij, v i, v j V (G) w(e) = w ij, e = (v i, v j ) D(G) G path P = (e 1,, e r ) P norm w(p ) w(p ) = w(e 1 ) w(e r ) G weighted Z(G, w, t) = (1 w(c)t C ) 1 [C 3

4 [C G prime, reduced cycles weighted edge 4 (Mizuno and Sato) G n W = W(G) G weighted matrix w e D(G) w(e 1 ) = w(e) 1 Z(G, w, t) 1 = (1 t 2 ) m n det(i n tw(g) + t 2 (D I n )) w Z(G, w, t) weighted matrix G edge ζ G (u) u G (G ) u Watanabe and Fukumizu [4 G, ζ G (u) weighted matrix Gudder [ Meyer [26 2 Nayak and Vishwanath [28; 21 Ambainis, Bach, Nayak, Vishwanath and Watrous [2; 21 Aharonov, Ambainis, Kempe and Vazirani [1 22 Childs, Farhi and Gutmann [6 22 Konno [2 26 Emms, Hancock, Severini and Wilson [1 Grover positive support 28 Emms [9 Grover 21 Ren, Aleksic, Emms, Wilson and Hancock [3 Grover positive support Ihara edge matrix 211 Konno and Sato [22 Ihara weighted Grover positive support 22 ([21) Z 4

5 p q = 1 p (1 p 1) p q n(n = 1, 2, ) k(k =, ±1, ±2, ) l m l + m = n, l + m = k l = n k 2, m = n + k 2 p l q n l p l q n l n C l X n n P (X n = k) = n C l p l q n l X n n k= n P (X n = k) = n nc l p l q n l = (p + q) n = 1 p = q = 1/2 l= lim P (a X b n 1 b) = exp( x2 n n a 2π 2 )dx 1/ 2π exp( x 2 /2) N(, 1) 23 ([21,25) Z k Z ψ k = [ αk k= ψ k 2 = C 2 β k k= ( α k 2 + β k 2 ) = 1 ψ k α k, β k [ a b U = c d a 2 + b 2 = b 2 + c 2 = 1 a b + c d =, c = b, d = ā( = ad bc) p,q P = [ a b [, Q = c d U = P + Q 1 = p + q p, q 5

6 [ ψ n α n k = k β n k n(n = 1, 2, ) k(k =, ±1, ±2, ) ψ n k = Pψ n 1 k+1 + Qψn 1 k 1 (n = ) [ ψ α = φ = β [ C 2, ψ k = (k ) φ 2 = α 2 + β 2 = 1 φ n = 1 ψ 1 1 = Pψ 2 + Qψ = ψ 1 1 = Pψ + Qψ 2 = [ a b [ a b [ [ α β [ + c d [ + c d [ α β [ [ = = cα + dβ [ aα + bβ, k ±1 k ± 1 ψ 1 k = Pψ k+1 + Qψ k 1 = [ a b [ [ + c d [ [ = n = 2 ψ 2 = Pψ Qψ 1 1 = [ a b [ cα + dβ [ + c d [ aα + bβ = [ b(cα + dβ) c(aα + bβ) [ ψ 2 2 = d(aα + bβ) [, ψ 2 a(cα + dβ) 2 = k, ±2 k ± 1 ±1 [ ψ 2 k = X n n n k P (X n = k) = ψ n k 2 = α n k 2 + β n k 2 U = 1 2 [ [ α, β = 1 [ 1 2 i 6

7 n/k /2 1/ /4 1/2 1/4 1 n ( ) ([2 ) 5 (Konno) [ α β ( α 2 + β 2 = 1) lim P (u X v n n n v) = u X n n Z (n ) [ 1 a 2 π(1 z 2 ) a 2 z {1 2 ( α 2 β 2 + aα b β + āᾱbβ a 2 z}dz lim P (u X n n n v) = 24 Grover v u 1 π(1 z 2 ) 1 z 2 dz G n m G v d v = deg G v D(G) Emms [9 D(G) arc e = (u, v) pure x e = x uv { x e e D(G)} C 2m arc (u, v) arc (w, x) v = w x uv ψ = (u,v) D(G) α uv x uv, α uv C P ( x e ) = α uv α uv (u,v) D(G) α uv α uv = 1 ψ t+1, ψ t U ψ t+1 = Uψ t D(G) Grover U = (U (w,x),(u,v) )([14 ): 2/d v if v = w, x u, U (w,x),(u,v) = 2/d v 1 if v = w, x = u, otherwise 7

8 D(G) G Grover G V (G) = {u, v, w, x} D(G) = {(u, v), (v, u), (v, w), (w, v), (v, x), (x, v)} D(G) order (u, v), (v, u), (w, v), (v, w), (x, v), (v, x) Grover U 1 1/3 2/3 2/3 U = 1 2/3 1/3 2/3 1 2/3 2/3 1/3 ψ t = a x uv b x wv (a 2 + b 2 = 1) ψ t+1 = Uψ t = au x uv bu x wv x uv = T (1), x wv = T (1) ψ t+1 = a T ( 1/3 2/3 2/3) b T ( 2/3 1/3 2/3) = ( 1/3a 2/3) x vu + (2/3a + 1/3b) x vw + 2/3(a b) x vx ( 1/3a 2/3) 2 + (2/3a + 1/3b) 2 + 4/9(a b) 2 = a 2 + b 2 = 1 Grover 25 G, H G = H f : V (G) V (H) uv E(G) f(u)f(v) E(H) G, H G = H G, H G = H f(g) = f(h) f(g) Φ(G; λ) = det(λi A(G)) Φ(G; λ) = Φ(H; λ) G = H G, H ([3) Ihara Z(G, u) = Z(H; u) G = H G, H ([7) Shiau, Joynt and Coopersmith [33, Emms, Severini, Wilson,and Hancock [11, Douglas and Wang [8, Gamble, Friesen, Zhou, Joynt and Coopersmith [12 Emms, Hancock, Severini and Wilson [1 A = (a ij ) A positive support A + = (a + ij ) a + ij = { 1 if aij >, otherwise 8

9 1 (Emms, Hancock, Severini and Wilson) G, H G = H Spec((U(G) 3 ) + ) = Spec((U(H) 3 ) + ) Spec(F) F ( ) U(G) G Grover G n, k, λ, µ (n, k, λ, µ)- V (G) = n G v d v = k u, v λ x, y µ K n,n (2n, n,, n)- 14 ([1) (16, 6, 2, 2)- 2 (36, 15, 6, 6)- 32,548 ([11) Emms et al [11 (?) Spec((U(G) 3 ) + ) Φ((U(G) 3 ) + ; λ) 3 weighted Grover 31 weighted G n m W = W(G) G weighted matrix 2 2m 2m B w = B w (G) = (B (w) e,f ) e,f D(G) J = J (G) = (J e,f ) e,f D(G) B (w) e,f = { w(f) if t(e) = o(f), otherwise, J e,f = G 2 weighted Z 1 (G, w, t) = det(i n t(b w J )) 1 { 1 if f = e 1, otherwise e D(G) w(e) = 1 G 2 weighted G Ihara 2 weighted ([31 ) 6 (Sato) G W = W(G) G weighted matrix G 2 weighted Z 1 (G, w, t) 1 = (1 t 2 ) m n det(i n tw(g) + t 2 (D w I n )) n = V (G), m = E(G) D w = (d ij ) d ii = o(e)=v i w(e), V (G) = {v 1,, v n } 32 Grover Grover G n m n n T(G) = (T uv ) u,v V (G) { 1/(deg T uv = G u) if (u, v) D(G), otherwise 9

10 7 (Konno and Sato) G n v 1,, v n m G Grover U det(λi 2m U) = (λ 2 1) m n det((λ 2 + 1)I n 2λT(G)) = (λ2 1) m n det((λ 2 + 1)D 2λA(G)) d v1 d vn Proof G n m V (G) = {v 1,, v n } D(G) = {e 1,, e m, e 1 1,, e 1 m } j = 1,, n d j = d vj = deg v j 2m 2m B d = (B ef ) e,f D(G) { 2/do(f) if t(e) = o(f), B ef = otherwise 6 det(i 2m t(b d J )) = (1 t 2 ) m n det(i n tw d (G) + t 2 (D d I n )) W d (G) = (w uv ) u,v V (G) D d = (d uv ) u,v V (G) w uv = { 2/du if (u, v) D(G), otherwise, d uv = { 2 if u = v, otherwise d j (2/d j ) = 2 (1 j n) det(i 2m t( T B d T J )) = (1 t 2 ) m n det(i n tw d (G) + t 2 I n ) T B d T J = U and W d (G) = 2T(G) det(i 2m tu) = (1 t 2 ) m n det((1 + t 2 )I n 2tT(G)) t = 1/λ det (I 2m 1λ ) U = ( 1 1 ) m n λ 2 det ((1 + 1λ ) 2 I n 2λ ) T(G) det(λi 2m U) = (λ 2 1) m n det((λ 2 + 1)I n 2λT(G)) T(G) = D 1 A(G) det(λi 2m U) = (λ 2 1) m n det((λ 2 + 1)I n 2λD 1 A(G)) = (λ 2 1) m n det D 1 det((λ 2 + 1)D 2λA(G)) det D 1 = 1/(d v1 d vn ) QED det(λi 2m U) = (λ2 1) m n det((λ 2 + 1)D 2λA(G)) d v1 d vn 7 Grover U T(G) ([1) 1

11 Corollary 1 (Emms, Hancock, Severini and Wilson) G n m Grover U 2n λ = λ T ± i 1 λ 2 T λ T T(G) U 2(m n) ±1 Proof 7 det(λi 2m U) = (λ 2 1) m n (λ λ T λ) λ T Spec(T(G)) λ λ T λ = λ = λ T ± i 1 λ 2 T QED Emms et al [1 Grover Grover G Grover U Corollary 2 G n v 1, v n m k- Grover U 2n λ = λ A ± i k 2 λ 2 A k λ A A(G) U 2(m n) ±1 Proof 7 D = ki n kλ 2 + k 2λ A λ = QED det(λi 2m U) = (λ2 1) m n d v1 d vn λ A Spec(A(G)) λ = λ A ± i k 2 λ 2 A k 32 Grover positive support (kλ 2 + k 2λ A λ) G Grover positive support U + A(G) ([1) Ren, Aleksic, Emms, Wilson and Hancock [3 Grover positive support U + Ihara edge matrix 8 (Ren, Aleksic, Emms, Wilson and Hancock) G G δ δ(g) 2 B J G Perron-Frobenius operator edge matrix U G Grover B J U positive support B J = ( T U) + 11

12 2 8 Grover positive support U + 9 (Konno and Sato) G n v 1,, v n m G Grover positive support U + Proof 2 8 u = 1/λ det(λi 2m U + ) = (λ 2 1) m n det((λ 2 1)I n λa(g) + D) det(λi 2m uu + ) = det(i 2m u( T B T J )) = det(i 2m u(b J )) = (1 t 2 ) m n det(i n ua(g) + u 2 (D I n )) det (I 2m 1λ ) ( U+ = 1 1 ) m n ( λ 2 det I n 1 λ A(G) + 1 ) λ 2 (D I n) QED det(λi 2m U + ) = (λ 2 1) m n det((λ 2 1)I n λa(g) + D) 9 G Grover positive support U + A(G) Corollary 3 (Emms, Hancock, Severini and Wilson) Let G n m k- δ(g) 2 Grover positive support U + 2n λ = λ A 2 ± i k 1 λ 2 A /4 λ A A(G) U + 2(m n) ±1 Proof 9 D = ki n det(λi 2m U + ) = (λ 2 1) m n det(λ 2 + k 1)I n λa(g)) kλ 2 + k 1 λ A λ = QED = (λ 2 1) m n λ A Spec(A(G)) (kλ2 + k 1 λ A λ) λ = λ A 2 ± i k 1 λ 2 A /4 Spec(U), Spec(U + ), Spec((U 2 ) + ) G, H (n, k, λ, µ)- ( ) Spec(A(G)) = Spec(A(H)) = {k, θ, τ} θ = (λ τ) + 2, τ = (λ τ) +, = (λ τ) 2 + 4(k µ) 2 12

13 θ, τ n, k, λ, µ ([13 ) Cor 2 Cor 3 Emms et al [1 U, U +, (U 2 ) + Spec(U(G)) = Spec(U(H)), Spec(U(G) + ) = Spec(U(H) + ), Spec((U(G) 2 ) + ) = Spec((U(H) 2 ) + ) G = H Spec(U), Spec(U + ), Spec((U 2 ) + ) 4 Further Remark (1) 9 (U 2 ) + A(G) (2) 1 (U 3 ) + 2 (U 3 ) +? 3 (U n ) + 1,2,3 3 [1 D Aharonov, A Ambainis, J Kempe, and U V Vazirani, Quantum walks on graphs, Proc of the 33rd Annual ACM Symposium on Theory of Computing, 5-59, 21 [2 A Ambainis, E Bach, A Nayak, A Vishwanath and J Watrous, One-dimensional quantum walks, Proc of the 33rd Annual ACM Symposium on Theory of Computing, 37-49, 21 [3 G A Baker, Drum shapes and isospectral graphs, J Math Phys 7 (1966), [4 L Bartholdi, Counting paths in graphs, Enseign Math 45 (1999), [5 H Bass, The Ihara-Selberg zeta function of a tree lattice, Internat J Math 3 (1992), [6 A M Childs, E Farhi and S Gutmann, An example of the difference between quantum and classical random walks, Quantum Inform Process 1 (22), [7 Y Cooper, Properties determined by the Ihara zeta function of a graph, Electronic J Combin 16 (29), R84 [8 B L Douglas and J B Wang, Classically efficient graph isomorphism algorithm using quantum walks, arxiv: [9 D M Emms, Analysis of graph structure using quantum walks, Ph D Thesis, University of York, 28 [1 D M Emms, E R Hancock, S Severini and R C Wilson, A matrix representation of graphs and its spectrum as a graph invariant, Electronic J Combin 13 (26), R34 [11 D M Emms, S Severini, R C Wilson and E R Hancock, Coined quantum walks lift the cospectrality of graphs and trees, Pattern Recognit 42 (29), [12 J K Gamble, M Friesen, D Zhou, R Joynt and S N Coopersmith, Two-particle quantum walks applied to the graph isomorphism problem, Phys Rev A 81 (21),

14 [13 C, Godsil and G Royle, Algebraic Graph Theory, Springer, New York, 21 [14 L Grover, A first quantum mechanical algorithm for database search, Proc of the 28 th Annual ACM Symposium on Theory of Computing, , 1996 [15 S P Gudder, Quantum Probability, Academic Press Inc CA, 1988 [16 K Hashimoto, Zeta Functions of Finite Graphs and Representations of p-adic Groups, Adv Stud Pure Math Vol 15, pp , Academic Press, New York (1989) [17 K Hashimoto, On the zeta- and L-functions of finite graphs, Internat J Math 1 (199), [18 K Hashimoto, Artin-type L-functions and the density theorem for prime cycles on finite graphs, Internat J Math 3 (1992), [19 Y Ihara, On discrete subgroups of the two by two projective linear group over p-adic fields, J Math Soc Japan 18 (1966), [2 N Konno, Quantum random walks in one dimension, Quantum Inform Process 1 (22), [21,,, 28 [22 N Konno and I Sato, On the relation between quantum walks and zeta functions, Quantum Inform Process (in press) [23 M Kotani and T Sunada, Zeta functions of finite graphs, J Math Sci U Tokyo 7 (2), 7-25 [24 A Lubotzky, Cayley graphs: Eigenvalues, expanders and random walks, in: Surveys in Combinatorics, in: London Math Soc Lecture Note Ser, vol 218, Cambridge Univ Press, Cambridge, 1995, pp [25,,,, 21 [26 D Meyer, From quantum cellular automata to quantum lattice gases, J Statist Phys 85 (1996), [27 H Mizuno and I Sato, Weighted zeta functions of graphs, J Combin Theory Ser B 91 (24), [28 A Nayak, and A Vishwanath, Quantum walk on the line, DIMACS Technical report, 2-43, 2 [29 S Northshield, A note on the zeta function of a graph, J Combin Theory Ser B 74 (1998), [3 P Ren, T Aleksic, D Emms, RC Wilson and ER Hancock, Quantum walks, Ihara zweta functions and cospectrality in regular graphs, Quantum Inform Process (in press) [31 I Sato, A new Bartholdi zeta function of a graph Int J Algebra 1 (27), [32 J -P Serre, Trees, Springer-Verlag, New York, 198 [33 S -Y Shiau, R Joynt and S N Coopersmith, Physically-motivatred dynamical algorithms for the graph isomorphism problem, Quantum Inform Comput 5 (25), [34 H M Stark and A A Terras, Zeta functions of finite graphs and coverings, Adv Math 121 (1996), [35 H M Stark and A A Terras, Zeta functions of finite graphs and coverings III, Adv Math 28 (27), [36 T Sunada, L-Functions in Geometry and Some Applications, in Lecture Notes in Math, Vol 121, pp , Springer-Verlag, New York (1986) [37,,, 1988 [38 A Terras, Fourier Analysis on Finite Groups and Applications, Cambridge Univ Press, Cambridge 14

15 (1999) [39 A Terras, Zeta functions and chaos, preprint [4 Y Watanabe and K Fukumizu, Graph zeta function in the Bethe free energy and loopy belief propagation, to appear in Advances in Neural Information Processing Systems, 21 15