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