Quantum Computing (fall2013) Instructor:Shengyu Zhang. Lecture 4 Hidden Subgroup Problem 2:Fourier sampling and query-efficient algorithms. 1.HSP:What and why. Suppose that G is a group and H is a subgroup.Recall that cosets of H partition the group G.A function f:GS hides a subgroup H<G if f(x)=f(y)for x and y in the same coset and f(x)f(y)for x and y in different cosets. Definition.Given a black box function f:GS (for some finite set S)that hides a subgroup H <G,the Hidden Subgroup Problem (HSP)asks to find H. Two important special cases:symmetric group and dihedral group. Symmetric group Sn:the set of permutations on n elements.An efficient algorithm for HSP for symmetric group can be used to solve Graph Isomorphism in poly(n)time. Graph Isomorphism(GI):Given two n-node graphs G and G2,decide whether they are isomorphic,ie.whether there exists a permutation iES s.t.(G)=G2 Here for a graph G=(V,E),π(G)=(V,π(E)whereπ(E)={(π(i),πU):(i,j)∈E} Thus the two graphs are isomorphic if the following holds:(i,j)EE iff (n(i),n()E E2 Graph Isomorphism is known to be equivalent to the following variants:Graph Isomorphism Finding(given two isomorphic graphs,find an isomorphism),Graph Isomorphism Counting (given two isomorphic graphs,count the number of isomorphisms),Graph Automorphism Finding (given a graph G,find its automorphism group Aut(G)n:n(G)=G}).The decision version of Graph Automorphism(just to decide whether Aut(G)={1))is a clearly no harder,and possibly easier task. Graph Isomorphism is a fundamental problem that appears in many disciplines,and it's one of the few problems whose complexity isn't pinned down:It's not known to be in P,but it's also not known to be NP-complete either.Actually,most people believe that it is not NP-complete.It may be well in P and we just haven't found an algorithm yet
Quantum Computing (Fall 2013) Instructor: Shengyu Zhang. Lecture 4 Hidden Subgroup Problem2: Fourier sampling and query-efficient algorithms. 1. HSP: What and why. Suppose that 𝐺 is a group and 𝐻 is a subgroup. Recall that cosets of 𝐻 partition the group 𝐺. A function 𝑓: 𝐺 → 𝑆 hides a subgroup 𝐻 ≤ 𝐺 if 𝑓(𝑥) = 𝑓(𝑦) for 𝑥 and 𝑦 in the same coset and 𝑓(𝑥) ≠ 𝑓(𝑦) for 𝑥 and 𝑦 in different cosets. Definition. Given a black box function 𝑓: 𝐺 → 𝑆 (for some finite set 𝑆) that hides a subgroup 𝐻 ≤ 𝐺, the Hidden Subgroup Problem (HSP) asks to find 𝐻. Two important special cases: symmetric group and dihedral group. Symmetric group 𝑆𝑛 : the set of permutations on 𝑛 elements. An efficient algorithm for HSP for symmetric group can be used to solve Graph Isomorphism in 𝑝𝑜𝑙𝑦(𝑛) time. Graph Isomorphism (GI): Given two 𝑛-node graphs 𝐺1 and 𝐺2 , decide whether they are isomorphic, i.e. whether there exists a permutation 𝜋 ∈ 𝑆𝑛 s.t. 𝜋(𝐺1 ) = 𝐺2 . Here for a graph 𝐺 = (𝑉, 𝐸), 𝜋(𝐺) = (𝑉, 𝜋(𝐸)) where 𝜋(𝐸) = {(𝜋(𝑖),𝜋(𝑗)) ∶ (𝑖,𝑗) ∈ 𝐸}. Thus the two graphs are isomorphic if the following holds: (𝑖,𝑗) ∈ 𝐸1 iff (𝜋(𝑖),𝜋(𝑗)) ∈ 𝐸2 . Graph Isomorphism is known to be equivalent to the following variants: Graph Isomorphism Finding (given two isomorphic graphs, find an isomorphism), Graph Isomorphism Counting (given two isomorphic graphs, count the number of isomorphisms), Graph Automorphism Finding (given a graph 𝐺, find its automorphism group 𝐴𝑢𝑡(𝐺) ≝ {𝜋: 𝜋(𝐺) = 𝐺}). The decision version of Graph Automorphism (just to decide whether 𝐴𝑢𝑡(𝐺) = {𝟏}) is a clearly no harder, and possibly easier task. Graph Isomorphism is a fundamental problem that appears in many disciplines, and it’s one of the few problems whose complexity isn’t pinned down: It’s not known to be in P, but it’s also not known to be NP-complete either. Actually, most people believe that it is not NP-complete. It may be well in P and we just haven’t found an algorithm yet
Given the equivalence between GI and Graph Automorphism Finding(GA),we can see why GI reduces to HSP for symmetric group.First reduce GI to GA.Now for GA,given a graph G,define f on S by f()=(G).We claim that f hides Aut(G).Actually, f(π)=f(σ)台π(G)=o(G)台o-1π(G)=G 台o-1π∈Aut(G)台OAut(G)=πAut(G) The second major application of HSP for non-Abelian groups is the (Approximate)Shortest Vector problem,which reduces to HSP for dihedral group.We'll define(Approximate) Shortest Vector problem and dihedral group next. Consider R"and a set of basis,namely n linearly independent vectors in it.An n-dimensional lattice is the set of all integer linear combinations of n basis vectors.In the Shortest Vector problem,we want to find a shortest (but nonzero)vector in the lattice.That is, we want to use integer linear combination of basis vectors to get a vector that is very close to the origin.This problem itself is NP-hard,and we consider a relaxed version,that the input is promised to have only one (up to its sign)vector that achieves the minimum length;all the other vectors are at least g(n)times longer.Of course,the larger g(n)is,the stronger the promise and thus the easier the problem.It is known that if g(n)=0(1)then the problem is still NP-hard,and if g(n)=(1+e)(m),then the problem becomes in P.The question is what the complexity is for g(n)=poly(n).It is conjectured to be hard,and actually cryptosystems are built based on this computational assumption.What can a quantum computer do?If HSP for dihedral group is easy,then there is an efficient quantum algorithm to solve the (Approximate)Shortest Vector problem.The reduction is nontrivial,and we won't do it here.(It's actually one of the reading projects.)We'll just introduce what a dihedral group is. Consider a regular n-gon on a 2D plane.A symmetry is a rotation or a reflection which keeps the n-gon unchanged.A regular n-gon has 2n symmetries:n rotational ones and n reflection ones,the collection of which form the dihedral group Dan So D2n=(T,s|rn=1,s2=1,s-1rs=r-1) (D2n is generated by elements r and s satisfying the relations rn =1,s2 =1,s-irs r1)
Given the equivalence between GI and Graph Automorphism Finding (GA), we can see why GI reduces to HSP for symmetric group. First reduce GI to GA. Now for GA, given a graph 𝐺, define 𝑓 on 𝑆𝑛 by 𝑓(𝜋) = 𝜋(𝐺). We claim that 𝑓 hides 𝐴𝑢𝑡(𝐺). Actually, 𝑓(𝜋) = 𝑓(𝜎) ⇔ 𝜋(𝐺) = 𝜎(𝐺) ⇔ 𝜎 −1𝜋(𝐺) = 𝐺 ⇔ 𝜎 −1𝜋 ∈ 𝐴𝑢𝑡(𝐺) ⇔ 𝜎𝐴𝑢𝑡 (𝐺) = 𝜋𝐴𝑢𝑡(𝐺) The second major application of HSP for non-Abelian groups is the (Approximate) Shortest Vector problem, which reduces to HSP for dihedral group. We’ll define (Approximate) Shortest Vector problem and dihedral group next. Consider ℝ 𝑛 and a set of basis, namely 𝑛 linearly independent vectors in it. An 𝑛-dimensional lattice is the set of all integer linear combinations of 𝑛 basis vectors. In the Shortest Vector problem, we want to find a shortest (but nonzero) vector in the lattice. That is, we want to use integer linear combination of basis vectors to get a vector that is very close to the origin. This problem itself is NP-hard, and we consider a relaxed version, that the input is promised to have only one (up to its sign) vector that achieves the minimum length; all the other vectors are at least 𝑔(𝑛) times longer. Of course, the larger 𝑔(𝑛) is, the stronger the promise and thus the easier the problem. It is known that if 𝑔(𝑛) = 𝑂(1) then the problem is still NP-hard, and if 𝑔(𝑛) = (1 + 𝜖) Ω(𝑛) , then the problem becomes in P. The question is what the complexity is for 𝑔(𝑛) = 𝑝𝑜𝑙𝑦(𝑛). It is conjectured to be hard, and actually cryptosystems are built based on this computational assumption. What can a quantum computer do? If HSP for dihedral group is easy, then there is an efficient quantum algorithm to solve the (Approximate) Shortest Vector problem. The reduction is nontrivial, and we won’t do it here. (It’s actually one of the reading projects.) We’ll just introduce what a dihedral group is. Consider a regular 𝑛-gon on a 2D plane. A symmetry is a rotation or a reflection which keeps the 𝑛-gon unchanged. A regular 𝑛-gon has 2𝑛 symmetries: 𝑛 rotational ones and 𝑛 reflection ones, the collection of which form the dihedral group 𝐷2𝑛 . So 𝐷2𝑛 = 〈 𝑟,𝑠 ∣ 𝑟 𝑛 = 1, 𝑠 2 = 1, 𝑠 −1 𝑟𝑠 = 𝑟 −1 〉 (𝐷2𝑛 is generated by elements 𝑟 and 𝑠 satisfying the relations 𝑟 𝑛 = 1, 𝑠 2 = 1, 𝑠 −1 𝑟𝑠 = 𝑟 −1 .)
2.Detour:density matrices. Mixed states:Pure states with probabilities. ·lp〉→X,rank-1 positive semi--definite(psd)matrix 。 flp,pi}→∑ipili)il trace-1 psd matrices. Fact:Any trace-1 psd matrix also corresponds to an ensemble ),pi}of quantum pure states. Proof.Do the spectral decomposition and use the fact that the trace is 1 to conclude that the sum of eigenvalues is 1.▣ ·Unitary transform:p→UpUt Measurement:{Mi}with EiM,Mi=I.Then Prli]tr(MipM),and the post-measurement state is MipM/tr(MipM). Why use density matrices:Because only those matter---The exact ensemble of pure states doesn't since we can't distinguish different ensembles with the same density matrix. Composition:P1⑧P2 3.Standard approach,weak and strong Fourier sampling Standard approach: 后2.cy ausa.又)(》 asure☒奇CHeH xh)for a random x∈G Writing this in the density matrix form,we have the following 1 1 P=IGIHI Ixh)(xh'l XEG XETH h,h'EH h,h'EH where Th is a set of representatives. Weak Fourier sampling:
2. Detour: density matrices. Mixed states: Pure states with probabilities. |𝜓〉 → |𝜓〉〈𝜓|, rank-1 positive semi-definite (psd) matrix {|𝜓𝑖 〉,𝑝𝑖 } → ∑𝑖 𝑝𝑖 |𝜓𝑖 〉〈𝜓𝑖 |, trace-1 psd matrices. Fact: Any trace-1 psd matrix also corresponds to an ensemble {|𝜓𝑖 〉,𝑝𝑖 } of quantum pure states. Proof. Do the spectral decomposition and use the fact that the trace is 1 to conclude that the sum of eigenvalues is 1. □ Unitary transform: 𝜌 → 𝑈𝜌𝑈† . Measurement: {𝑀𝑖 } with ∑ 𝑀𝑖 † 𝑖 𝑀𝑖 = 𝐼. Then Pr[𝑖] = 𝑡𝑟(𝑀𝑖𝜌𝑀𝑖 † ), and the post-measurement state is 𝑀𝑖𝜌𝑀𝑖 † /𝑡𝑟(𝑀𝑖𝜌𝑀𝑖 † ). Why use density matrices: Because only those matter---The exact ensemble of pure states doesn’t since we can’t distinguish different ensembles with the same density matrix. Composition: 𝜌1 ⊗ 𝜌2. 3. Standard approach, weak and strong Fourier sampling Standard approach: 1 √|𝐺| ∑ |𝑥〉 𝑥∈𝐺 𝑞𝑢𝑒𝑟𝑦 𝑓 → 1 √|𝐺| ∑ |𝑥〉|𝑓(𝑥)〉 𝑥∈𝐺 𝑚𝑒𝑎𝑠𝑢𝑟𝑒 𝑓(𝑥) → 1 √|𝐻| ∑ |𝑥ℎ〉 ℎ∈𝐻 for a random 𝑥 ∈ 𝐺 Writing this in the density matrix form, we have the following 𝜌 = 1 |𝐺||𝐻| ∑ |𝑥ℎ〉〈𝑥ℎ ′ | 𝑥∈𝐺 ℎ,ℎ ′∈𝐻 = 1 |𝐺| ∑ |𝑥ℎ〉〈𝑥ℎ ′ | 𝑥∈𝑇𝐻 ℎ,ℎ ′∈𝐻 where 𝑇𝐻 is a set of representatives. Weak Fourier sampling:
1 P=GIHI a6-石￡am(2oap4a h,h'EH 1 =IGIH Rer=aN)=aw h.hH measure p observepw,p.atr(,⑧2 h)）=02nEHx,h) Question:Does polylog |G samples of p contain enough info to determine H? For Abelian groups:Yes,as previously discussed. Another class of subgroups that weak Fourier sampling suffices:normal subgroups. Definition.A subgroup H<G is normal if gH Hg,for all g EG. So if H is normal subgroup,then for any gE G,hg gh'for some h'E H.And if h runs over H,then so does h'. Theorem.If H is a normal subgroup of G,then the weak Fourier sampling gives p with probability dH/G if H ker (p),and 0 otherwise. Proof Ifker (p).then one observes If H is not contained in ker (p),then 3h'E H s.t.p(h*)1.Now note that ()()((k)-DG2) h'EH thus by Schur's lemma,EneHp(h)=AI for some ER But 2m片-2ww-(②w Thus EneHp(h)=0.So one observes p w.p.0. ▣
𝜌 = 1 |𝐺||𝐻| ∑ 𝑅(ℎ)|𝑥〉〈𝑥|𝑅(ℎ ′ ) † 𝑥∈𝐺 ℎ,ℎ ′∈𝐻 = 1 |𝐺||𝐻| ∑ 𝑅(ℎ)(∑|𝑥〉〈𝑥| 𝑥∈𝐺 )𝑅(ℎ ′ ) † ℎ,ℎ ′∈𝐻 = 1 |𝐺||𝐻| ∑ 𝑅(ℎ)𝑅(ℎ ′ ) † ℎ,ℎ ′∈𝐻 = 1 |𝐺||𝐻| ∑ 𝑅(ℎℎ ′−1 ) ℎ,ℎ ′∈𝐻 = 1 |𝐺| ∑ 𝑅(ℎ) ℎ∈𝐻 𝐹𝐺 → 1 |𝐺|∑⊕𝜌∈𝐺̂ (𝐼𝑑𝜌 ⊗ 𝜌(ℎ) ∗ ) ℎ∈𝐻 = 1 |𝐺| ⊕𝜌∈𝐺̂ (𝐼𝑑𝜌 ⊗ ∑𝜌(ℎ) ∗ ℎ∈𝐻 ) 𝑚𝑒𝑎𝑠𝑢𝑟𝑒 𝜌 → observe 𝜌 w.p. 1 |𝐺| 𝑡𝑟 (𝐼𝑑𝜌 ⊗ ∑ 𝜌(ℎ) ∗ ℎ∈𝐻 ) = 𝑑𝜌 |𝐺| ∑ 𝜒𝜌 (ℎ) ∗ ℎ∈𝐻 Question: Does 𝑝𝑜𝑙𝑦log |𝐺| samples of 𝜌 contain enough info to determine 𝐻? For Abelian groups: Yes, as previously discussed. Another class of subgroups that weak Fourier sampling suffices: normal subgroups. Definition. A subgroup 𝐻 ≤ 𝐺 is normal if 𝑔𝐻 = 𝐻𝑔, for all 𝑔 ∈ 𝐺. So if 𝐻 is normal subgroup, then for any 𝑔 ∈ 𝐺, ℎ𝑔 = 𝑔ℎ′ for some ℎ ′ ∈ 𝐻. And if ℎ runs over 𝐻, then so does ℎ′. Theorem. If 𝐻 is a normal subgroup of 𝐺, then the weak Fourier sampling gives 𝜌 with probability 𝑑𝜌 2 |𝐻|/|𝐺| if 𝐻 ⊆ ker (𝜌), and 0 otherwise. Proof. If 𝐻 ⊆ ker (𝜌), then one observes 𝜌 w.p. 𝑑𝜌 |𝐺| ∑ 𝜒𝜌 (ℎ) ∗ ℎ∈𝐻 = 𝑑𝜌 |𝐺| ∑ℎ∈𝐻 𝑑𝜌 = 𝑑𝜌 2 |𝐻| |𝐺| . If 𝐻 is not contained in ker (𝜌), then ∃ℎ ∗ ∈ 𝐻 s.t. 𝜌(ℎ ∗ ) ≠ 𝐼. Now note that (∑ 𝜌(ℎ) ℎ∈𝐻 )𝜌(𝑔) = ∑𝜌(ℎ)𝜌(𝑔) ℎ∈𝐻 = ∑ 𝜌(ℎ𝑔) ℎ∈𝐻 = ∑ 𝜌(𝑔ℎ′) ℎ ′∈𝐻 = 𝜌(𝑔)(∑ 𝜌(ℎ) ℎ∈𝐻 ), thus by Schur’s lemma, ∑ 𝜌(ℎ) ℎ∈𝐻 = 𝜆𝐼 for some 𝜆 ∈ ℝ. But 𝜌(ℎ ∗ )(∑ 𝜌(ℎ) ℎ∈𝐻 ) = ∑ 𝜌(ℎ ∗ℎ) ℎ∈𝐻 = (∑𝜌(ℎ) ℎ∈𝐻 ), Thus ∑ 𝜌(ℎ) ℎ∈𝐻 = 0. So one observes 𝜌 w.p. 0. □
The algorithm for HSP for normal subgroup is very similar to that for Abelian HSP. .Use weak Fourier sampling to get p,pz,for T=(loglGl). Output KT=nf=1ker (P) Theorem.K=H with high probability. Proof.If ker(K,)≠H,we claim that Pr[K,∈ker(pr+i)】≤Indeed, Pr[K,eker(p+i】=∑. d1H_IGIH_H川1 1G- p:KtEker (p) K,1G=K≤i Here we used a fact that for any normal subgroup N of G Strong Fourier sampling: Weak Fourier sampling fails to provide sufficient information for HSP for S and D2n.So people resort to strong Fourier sampling,which uses the remaining state p(H)= 高2aeHp(内. Question:What basis to use to measure this state? It turns out that even random basis can already solve some cases,such as HSP for Heisenberg Group 0 0 0 :a,b.cEFp c 1 However,for symmetric group,even strong Fourier sampling fails.Multi-register measurement is needed
The algorithm for HSP for normal subgroup is very similar to that for Abelian HSP. Use weak Fourier sampling to get 𝜌1 , 𝜌2 , … , 𝜌𝑇 for 𝑇 = 𝑂(log|𝐺|). Output 𝐾𝑇 =∩𝑡=1 𝑇 ker (𝜌𝑡 ) Theorem. 𝐾𝑇 = 𝐻 with high probability. Proof. If ker(𝐾𝑡 ) ≠ 𝐻, we claim that Pr[𝐾𝑡 ⊆ ker (𝜌𝑡+1 )] ≤ 1 2 . Indeed, Pr[𝐾𝑡 ⊆ ker(𝜌𝑡+1 )] = ∑ 𝑑𝜌 2 |𝐻| |𝐺| 𝜌:𝐾𝑡⊆ker (𝜌) = |𝐺| |𝐾𝑡 | |𝐻| |𝐺| = |𝐻| |𝐾𝑡 | ≤ 1 2 . Here we used a fact that for any normal subgroup 𝑁 of 𝐺, ∑ 𝑑𝜌 2 𝜌∈𝐺̂:𝑁⊆ker (𝜌) = |𝐺| |𝑁| . □ Strong Fourier sampling: Weak Fourier sampling fails to provide sufficient information for HSP for 𝑆𝑛 and 𝐷2𝑛 . So people resort to strong Fourier sampling, which uses the remaining state 𝜌(𝐻) = 1 |𝐻| ∑ 𝜌(ℎ) ℎ∈𝐻 . Question: What basis to use to measure this state? It turns out that even random basis can already solve some cases, such as HSP for Heisenberg Group {( 1 0 0 𝑏 1 0 𝑎 𝑐 1 ) : 𝑎, 𝑏, 𝑐 ∈ 𝔽𝑝 } However, for symmetric group, even strong Fourier sampling fails. Multi-register measurement is needed