Quantum Computing (fall2013) Instructor:Shengyu Zhang. Lecture 3 Hidden Subgroup Problem 1:Group Representations Stud ies of Hidden Subgroup Problem for non-Abelian groups often need knowledge of group representations,which is the subject of this lecture. 1.Linear representation of finite groups Suppose that V is a vector space over C.The general linear group GL(V)is the group of invertible linear operators from V to itself.Here we only consider the case V=C".The group GL(V)can also be identified with the group of invertible matrices in Cnxn. For a finite group G,a linear representation is a homomorphism p:G-GL(V).The dimension of V is called the degree of p,denoted by do.(Homomorphism:The map p is a homomorphism if p(x)p(y)=p(xy),Vx,yE G.)Note that this implies that p(x-1)= p(x)-1,and p(1c)=I where 1c is the identify element ofthe group G. Example 1.Trivial representation:p(x)=1,Vx EG.Here the degree do =1. Example 2.Regular representation:V spanx):xE G}.The left regular representation L is defined by L(x)ly)=Ixy),and the right regular representation R is defined by R(x)ly)=lyx-1).Here the degree d dg IGl. Two representations p and p2 are isomorphic if there is an invertible linear operator M:VV s.t.p(x)M =Mp2(x),Vx E G.Intuitively,it means that the two representations are the same up to a change of basis. For a representation p:G-GL(V),a subspace w of V is called G-invariant if p(x)WcW,x∈G. Claim.If W is G-invariant,then there is another subspace W's.t.V=W W',and W' is also G-invariant
Quantum Computing (Fall 2013) Instructor: Shengyu Zhang. Lecture 3 Hidden Subgroup Problem1: Group Representations Studies of Hidden Subgroup Problem for non-Abelian groups often need knowledge of group representations, which is the subject of this lecture. 1. Linear representation of finite groups Suppose that 𝑉 is a vector space over ℂ. The general linear group 𝐺𝐿(𝑉) is the group of invertible linear operators from 𝑉 to itself. Here we only consider the case 𝑉 = ℂ 𝑛 . The group 𝐺𝐿(𝑉) can also be identified with the group of invertible matrices in ℂ 𝑛×𝑛 . For a finite group 𝐺, a linear representation is a homomorphism 𝜌: 𝐺 → 𝐺𝐿(𝑉). The dimension of 𝑉 is called the degree of 𝜌, denoted by 𝑑𝜌 . (Homomorphism: The map 𝜌 is a homomorphism if 𝜌(𝑥)𝜌(𝑦) = 𝜌(𝑥𝑦),∀𝑥, 𝑦 ∈ 𝐺.) Note that this implies that 𝜌(𝑥 −1 ) = 𝜌(𝑥) −1 , and 𝜌(1𝐺 ) = 𝐼 where 1𝐺 is the identify element of the group 𝐺. Example 1. Trivial representation: 𝜌(𝑥) = 1,∀𝑥 ∈ 𝐺. Here the degree 𝑑𝜌 = 1. Example 2. Regular representation: 𝑉 = 𝑠𝑝𝑎𝑛{|𝑥〉:𝑥 ∈ 𝐺}. The left regular representation 𝐿 is defined by 𝐿(𝑥)|𝑦〉 = |𝑥𝑦〉, and the right regular representation 𝑅 is defined by 𝑅(𝑥)|𝑦〉 = |𝑦𝑥 −1 〉. Here the degree 𝑑𝐿 = 𝑑𝑅 = |𝐺|. Two representations 𝜌1 and 𝜌2 are isomorphic if there is an invertible linear operator 𝑀: 𝑉 → 𝑉 s.t. 𝜌1 (𝑥)𝑀 = 𝑀𝜌2 (𝑥),∀𝑥 ∈ 𝐺. Intuitively, it means that the two representations are the same up to a change of basis. For a representation 𝜌: 𝐺 → 𝐺𝐿(𝑉), a subspace 𝑊 of 𝑉 is called 𝐺-invariant if 𝜌(𝑥)𝑊 ⊆ 𝑊, ∀𝑥 ∈ 𝐺. Claim. If 𝑊 is 𝐺-invariant, then there is another subspace 𝑊′ s.t. 𝑉 = 𝑊 ⊕ 𝑊′, and 𝑊′ is also 𝐺-invariant
See [Ser77]for two proofs.By this result,we know that if there is a G-invariant subspace W, then V=Ww'for a subspace w',and the representation can also be decomposed into the direct sum of two subrepresentations,namely p =pw pw'.In matrix form,p is a block diagonal matrix Pw If p doesn't have any nontrivial G-invariant subspace,we call p irreducible.We use G to denote the set of irreducible representations of G.We sometimes use"irrep"as a shorthand for"irreducible representation". Fact.Every representation is isomorphic to a direct sum of irreducible representations. An important result about irreducible representations is the following Schur's lemma. Theorem(Schur's lemma).For two irreducible representations p and p2 with degree n and n2,respectively,assume that there is a matrix M E Cmxnz s.t.p(x)M= Mpz(x),Vx EG.If p is not isomorphic to p2,then M=0.If p=P2 and n=n2, then M=AI for some real number A. Proof.See [Ser77]. This lemma can be used to prove the following fundamental orthogonality theorem. Theorem.For any two different irreducible representations P and P2 in matrix form,and any i,je [n],i',j'E [n2],it holds that 2px1P2(x)7=0. XE When p and p2 take unitary matrices,then the above equality changes to p()1=0. XEG Proof.See [Ser77] 2.Character theory For a representation p,its character is simply a function A:GC defined by A(x)= tr(p(x)),where tr is the trace---sum of eigenvalues.Note that A(1)=do.A character is irreducible if it is the character of an irreducible representation
See [Ser77] for two proofs. By this result, we know that if there is a 𝐺-invariant subspace 𝑊, then 𝑉 = 𝑊 ⊕ 𝑊′ for a subspace 𝑊′, and the representation can also be decomposed into the direct sum of two subrepresentations, namely 𝜌 = 𝜌𝑊 ⊕ 𝜌𝑊′ . In matrix form, 𝜌 is a block diagonal matrix ( 𝜌𝑊 𝜌𝑊′ ). If 𝜌 doesn’t have any nontrivial 𝐺-invariant subspace, we call 𝜌 irreducible. We use 𝐺̂ to denote the set of irreducible representations of 𝐺. We sometimes use “irrep” as a shorthand for “irreducible representation”. Fact. Every representation is isomorphic to a direct sum of irreducible representations. An important result about irreducible representations is the following Schur’s lemma. Theorem (Schur’s lemma). For two irreducible representations 𝜌1 and 𝜌2 with degree 𝑛1 and 𝑛2 , respectively, assume that there is a matrix 𝑀 ∈ ℂ 𝑛1×𝑛2 s.t. 𝜌1 (𝑥)𝑀 = 𝑀𝜌2 (𝑥),∀𝑥 ∈ 𝐺. If 𝜌1 is not isomorphic to 𝜌2 , then 𝑀 = 0. If 𝜌1 = 𝜌2 and 𝑛1 = 𝑛2 , then 𝑀 = 𝜆𝐼 for some real number 𝜆. Proof. See [Ser77]. This lemma can be used to prove the following fundamental orthogonality theorem. Theorem. For any two different irreducible representations 𝜌1 and 𝜌2 in matrix form, and any 𝑖,𝑗 ∈ [𝑛1 ], 𝑖′,𝑗′ ∈ [𝑛2 ], it holds that ∑ 𝜌1 (𝑥 −1 ) 𝑖𝑗𝜌2 (𝑥) 𝑖 ′ 𝑗 ′ 𝑥∈𝐺 = 0. When 𝜌1 and 𝜌2 take unitary matrices, then the above equality changes to ∑ 𝜌1 (𝑥) 𝑖𝑗 ∗ 𝜌2 (𝑥) 𝑖 ′ 𝑗 ′ 𝑥∈𝐺 = 0. Proof. See [Ser77] 2. Character theory For a representation 𝜌, its character is simply a function 𝜆: 𝐺 → ℂ defined by 𝜆(𝑥) = 𝑡𝑟(𝜌(𝑥)), where 𝑡𝑟 is the trace---sum of eigenvalues. Note that 𝜆(1) = 𝑑𝜌 . A character is irreducible if it is the character of an irreducible representation
The following theorem is a simple corollary of the orthogonality of irreducible representations. Theorem.Different irreducible characters and are orthogonal:xe(x)(x)=0. Two elements x and y are called conjugate if 3g EG s.t.gxg-1=y.It's an equivalent relation and thus partitions G into conjugacy classes.Class functions are constant for members of the same conjugacy class.It is not hard to see that characters are class functions. For two complex-valued functions and on G,define two inner products (,)=a2xe6()(x)and(0,0）=a26(x)(x) where the superscript is the complex conjugate.These two inner products are the same if one of the functions is a character,due to the following fact. Fact.For a character x of G,x(x1)=x(x)*. Proo时X(x-1)=tr(p(x-1)=::(p(x-1)=::(p(x)-1)=∑：：(p(x)=x(x), where i(M)'s are the eigenvalues of M. 3.Regular representation and Fourier transform Recall the left regular representation L(x)ly)=Ixy)and the right regular representation R(x)ly)=lyx-1).The following equalities hold. L~⊕pec(p⑧1an)andR~⊕peG(1a,⑧p*), (1) In fact,these hold for the same isomorphism,which is the Fourier transform over G. Formally,define the Fourier transform by the following. lWH)兰a2p64lp,p,where》=忘2A=1p(r.k. In other words,the Fourier transform is E。=ex. XEG Note that F depends on the choice of basis for each irrep of dimension greater than 1
The following theorem is a simple corollary of the orthogonality of irreducible representations. Theorem. Different irreducible characters 𝜆 and 𝜆 ′ are orthogonal: ∑ 𝜆(𝑥) ∗𝜆′(𝑥) 𝑥∈𝐺 = 0. Two elements 𝑥 and 𝑦 are called conjugate if ∃𝑔 ∈ 𝐺 s.t. 𝑔𝑥𝑔−1 = 𝑦. It’s an equivalent relation and thus partitions 𝐺 into conjugacy classes. Class functions are constant for members of the same conjugacy class.It is not hard to see that characters are class functions. For two complex-valued functions 𝜙 and 𝜓 on 𝐺, define two inner products (𝜙, 𝜓) = 1 |𝐺| ∑ 𝜙(𝑥)𝜓(𝑥 −1 ) 𝑥∈𝐺 and 〈𝜙, 𝜓〉 = 1 |𝐺| ∑ 𝜙(𝑥)𝜓(𝑥) ∗ 𝑥∈𝐺 where the superscript * is the complex conjugate. These two inner products are the same if one of the functions is a character, due to the following fact. Fact. For a character 𝜒 of 𝐺, 𝜒(𝑥 −1 ) = 𝜒(𝑥) ∗ . Proof. 𝜒(𝑥 −1 ) = tr(𝜌(𝑥 −1 )) = ∑ 𝜆𝑖 (𝜌(𝑥 −1 )) 𝑖 = ∑ 𝜆𝑖 (𝜌(𝑥) −1 ) 𝑖 = ∑ 𝜆𝑖 (𝜌(𝑥)) ∗ 𝑖 = 𝜒(𝑥) ∗ , where 𝜆𝑖 (𝑀)’s are the eigenvalues of 𝑀. 3. Regular representation and Fourier transform Recall the left regular representation 𝐿(𝑥)|𝑦〉 = |𝑥𝑦〉 and the right regular representation 𝑅(𝑥)|𝑦〉 = |𝑦𝑥 −1 〉. The following equalities hold. 𝐿 ∼ ⨁ (𝜌 ⊗ 1𝑑𝜌 ) 𝜌∈𝐺̂ and 𝑅 ∼ ⨁ (1𝑑𝜌 ⊗ 𝜌 ∗ ) 𝜌∈𝐺̂ . (1) In fact, these hold for the same isomorphism, which is the Fourier transform over 𝐺. Formally, define the Fourier transform by the following. |𝑥〉 ↦ |𝑥̂〉 ≝ 1 √|𝐺| ∑ 𝑑𝜌 |𝜌, 𝜌(𝑥)〉 𝜌∈𝐺̂ , where |𝜌(𝑥)〉 = 1 √𝑑𝜌 ∑ 𝜌(𝑥) 𝑗,𝑘 𝑑𝜌 𝑗,𝑘=1 |𝑗, 𝑘〉. In other words, the Fourier transform is 𝐹𝐺 = ∑|𝑥̂〉〈𝑥| 𝑥∈𝐺 . Note that 𝐹𝐺 depends on the choice of basis for each irrep of dimension greater than 1
Theorem.The Fourier transform F simultaneously decomposes the left and right regular representations L and R into their irreducible components. Proof.We verify for left regular representation,and the case for R is similar. ix)=FGL(x)F毫=∑创 y∈G da =ΣΣΣ Ndad yeG.g'∈Gj,k='k'=1 G X o(xy)j.ko'(y).j.kXo'.j'.k'l 足Σ空空 Ndoda yeG o.o'EGj.k.t=1 j'.k'=1 IG] Xa(x)j.co(y)eko'y).j.k)o'.j'.k'l =ΣΣ a(x)j.elo.j.k)(o.e.kl cEGj.k.(=1 =⊕[x)⑧1a,] geG The identity Eq.(1)also implies the following basic fact. Fact.IGI=∑pecd 4.Abelian groups For a cyclic group Zn,the irreps are py:Ix)wy for ye[n].The Fourier transform is pe:lx)H斤Zyo'lbW.Fora finite Abelian group,suppsesmicto,×…×Zne,then the irreps arewhere and the Fouriertransform is Pyiy:x1.x) yh…ye For Abelian groups,all irreps are one-dimensional.The converse is also true:Any non-Abelian group has an irrep with degree strictly larger than 1
Theorem. The Fourier transform 𝐹𝐺 simultaneously decomposes the left and right regular representations 𝐿 and 𝑅 into their irreducible components. Proof. We verify for left regular representation, and the case for 𝑅 is similar. The identity Eq.(1) also implies the following basic fact. Fact. |𝐺| = ∑ 𝑑𝜌 2 𝜌∈𝐺̂ . 4. Abelian groups For a cyclic group ℤ𝑛, the irreps are 𝜌𝑦 :|𝑥〉 ↦ 𝜔𝑛 𝑥𝑦 for 𝑦 ∈ [𝑛]. The Fourier transform is 𝜌𝑘:|𝑥〉 ↦ 1 √𝑛 ∑ 𝜔𝑛 𝑥𝑦 𝑦 |𝑦〉. For a finite Abelian group, suppose it is isomorphic to ℤ𝑛1 × …× ℤ𝑛𝑡 , then the irreps are 𝜌𝑦1…𝑦𝑡 :|𝑥1… 𝑥𝑡 〉 ↦ 𝜔𝑛1 𝑥1𝑦1 … 𝜔𝑛𝑡 𝑥𝑡𝑦𝑡 where 𝑥𝑖 ,𝑦𝑖 ∈ [𝑛𝑖 ], and the Fourier transform is 𝜌𝑦1…𝑦𝑡 :|𝑥1…𝑥𝑡 〉 ↦ 1 √𝑛 ∑ 𝜔𝑛1 𝑥1𝑦1 …𝜔𝑛𝑡 𝑥𝑡𝑦𝑡 |𝑦1 … 𝑦𝑡 〉 𝑦1…𝑦𝑡 . For Abelian groups, all irreps are one-dimensional. The converse is also true: Any non-Abelian group has an irrep with degree strictly larger than 1
One can also note that Abelian groups G have the property that GG,which non-Abelian groups do not enjoy. Note A good(and concise)reference for group representation is [Ser77].[CvD10]also has an appendix for some basic knowledge about group representation,though it takes a matrix (instead of operator)view.For general introduction of algebra,see [Art10].For more extensive introduction of abstract algebra,a standard textbook is [DF03]. Reference [Art10]Michael Artin,Algebra,2 edition,Pearson,2010. [CvD10]Andrew M.Childs and Wim van Dam,Quantum algorithms for algebraic problems,Reviews of Modern Physics,Volume 82,January-March 2010 [DF03]David S.Dummit and Richard M.Foote,Abstract Algebra,Wiley,2003. [Ser77]Jean-Pierre Serre,Linear representations of finite groups,Springer-Verlag,1977. Exercise 1.Prove that characters are class functions,namely x(xyx-1)=x(y).Also prove another property: x(x-1)=X(x)* 2.Check that the Fourier transform defined is unitary
One can also note that Abelian groups 𝐺 have the property that 𝐺 ≅ 𝐺̂, which non-Abelian groups do not enjoy. Note A good (and concise) reference for group representation is [Ser77]. [CvD10] also has an appendix for some basic knowledge about group representation, though it takes a matrix (instead of operator) view. For general introduction of algebra, see [Art10]. For more extensive introduction of abstract algebra, a standard textbook is [DF03]. Reference [Art10] Michael Artin, Algebra, 2 nd edition, Pearson, 2010. [CvD10] Andrew M. Childs and Wim van Dam, Quantum algorithms for algebraic problems, Reviews of Modern Physics, Volume 82, January–March 2010. [DF03] David S. Dummit and Richard M. Foote, Abstract Algebra, Wiley, 2003. [Ser77] Jean-Pierre Serre, Linear representations of finite groups, Springer-Verlag, 1977. Exercise 1. Prove that characters are class functions, namely 𝜒(𝑥𝑦𝑥 −1) = 𝜒(𝑦). Also prove another property: 𝜒(𝑥 −1) = 𝜒(𝑥) ∗ . 2. Check that the Fourier transform defined is unitary
