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
4.Query efficient algorithm When multi-register measurement is used,we can solve HSP using only polylog |Gl queries to f,though the computational time is still exponential. Recall that the standard approach gives(h Our task is just to identify H from a collection {pH:H <G).In general,mixed state identification is known to have the following bound Theorem.There exists a quantum measurement that identifies p:i=1,...,N}with probability at least 1-N max F(pi,pi). i#i Here F(p.)=tr=is a measure of how close two mixed statesp and o are.The F value is always between 0 and 1,and the closer to 1,then closer the two states.So to identify P(namely to identify H),it is enough if PH's for different H are far from each other.It turns out that this is more or less true. Theorem.F(pa,P#)<1/V2. We will not prove this result,but only explain how to use it.It is not hard to verify that F(p⑧n,o⑧m)=F(p,o)n. By the above results,we know that if we want the error probability to be e,then we need to use K copies of p_H,satisfying maxF(Pp)K≤e. N i≠j Solving this givesKo.How large is N?It'sjust the number of subgroups. Fact.Any group G has at most 2g subgroups. Proof.Each subgroup has a generating set of size at most log |Gl,because adding one more generator at least double the size of the subgroup.Therefore,the number of subgroups is at most (ogi)
4. Query efficient algorithm When multi-register measurement is used, we can solve HSP using only 𝑝𝑜𝑙𝑦log |𝐺| queries to 𝑓, though the computational time is still exponential. Recall that the standard approach gives 𝜌𝐻 = 1 |𝐺||𝐻| ∑ |𝑥ℎ〉〈𝑥ℎ ′ 𝑥∈𝐺 | ℎ,ℎ ′∈𝐻 . Our task is just to identify 𝐻 from a collection {𝜌𝐻 : 𝐻 ≤ 𝐺}. In general, mixed state identification is known to have the following bound. Theorem. There exists a quantum measurement that identifies {𝜌𝑖 : 𝑖 = 1, …, 𝑁} with probability at least 1 − 𝑁√max 𝑖≠𝑗 𝐹(𝜌𝑖 ,𝜌𝑗 ). Here 𝐹(𝜌, 𝜎) = 𝑡𝑟√√𝜌𝜎√𝜌 = ‖√𝜌√𝜎‖ 𝑡𝑟 is a measure of how close two mixed states 𝜌 and 𝜎 are. The 𝐹 value is always between 0 and 1, and the closer to 1, then closer the two states. So to identify 𝜌𝐻 (namely to identify 𝐻), it is enough if 𝜌𝐻 ’s for different 𝐻 are far from each other. It turns out that this is more or less true. Theorem. 𝐹(𝜌𝐻, 𝜌𝐻 ′ ) ≤ 1/√2. We will not prove this result, but only explain how to use it. It is not hard to verify that 𝐹(𝜌 ⊗𝑛 , 𝜎 ⊗𝑛 ) = 𝐹(𝜌, 𝜎) 𝑛 . By the above results, we know that if we want the error probability to be 𝜖, then we need to use 𝐾 copies of 𝜌_𝐻, satisfying 𝑁√max 𝑖≠𝑗 𝐹(𝜌𝑖 , 𝜌𝑗 ) 𝐾 ≤ 𝜖. Solving this gives 𝐾 ≥ 𝑂 (log 𝑁 𝜖 ). How large is 𝑁? It’s just the number of subgroups. Fact. Any group 𝐺 has at most 2 log2|𝐺| subgroups. Proof. Each subgroup has a generating set of size at most log |𝐺|, because adding one more generator at least double the size of the subgroup. Therefore, the number of subgroups is at most ( |𝐺| log|𝐺| ) ≤ 2 log2 |𝐺| . □
Reference [CvD10]Andrew M.Childs and Wim van Dam,Quantum algorithms for algebraic problems,Reviews of Modern Physics,Volume 82,January-March 2010. [Lom04]Chris Lomont,The hidden subgroup problem-review and open problems, arXiv:quant-ph/0411037vl
Reference [CvD10] Andrew M. Childs and Wim van Dam, Quantum algorithms for algebraic problems, Reviews of Modern Physics, Volume 82, January–March 2010. [Lom04] Chris Lomont, The hidden subgroup problem - review and open problems, arXiv:quant-ph/0411037v1