A hidden subgroup problem algorithm is one of the most advanced algorithms in quantum com- puting. The factorization problem and the dlp problem are particular cases of HSP. The goal of that algorithm is to learn the algebraic structure of some abelian group G "hidden inside an algebraic oper- ator". By assumption, we know the generators X1, ... , In for G. Roughly speaking, each iteration of the algorithm produces a random relation for x1, ..., In, i.e., a tuple (Q1, ..., An) E Z" satisfying Q1X1 + ... + Anln = 0). It can produce a useless relation, like (0,...,0). It can produce a redundant relation, i.e., one that follows from already found relations. Exercise 7.3. [10pts] Suppose that G is an abelian group generated by z and x2. Using a quantum algorithm we learn that x and X2 are subject to the following relations: 6x1 + 10x2 = 0 r2 = 14x1 2x 2 = 0 13 = -4x1 + 18x2 = 0. Assuming that this set of relations is complete (all other relations follow from ri, r2, r3) express G as a direct product of cyclic groups. 11 = =