Hidden subgroup problem

EN Texto em inglês Ainda não há artigo no teu idioma: trecho em inglês.

The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. It is a generalization of problems including factoring, discrete logarithm, graph isomorphism, and the shortest vector problem. This makes it especially important in the theory of quantum computing because Shor's algorithms for factoring and finding discrete logarithms in quantum computing are instances of the hidden subgroup problem for finite abelian groups, while the other problems correspond to finite groups that are not abelian. Given a group G {\displaystyle G} , a subgroup H ≤ G {\displaystyle H\leq G} , and a set X {\displaystyle X} , we say a function f : G → X {\displaystyle f:G\to X} hides the subgroup H {\displaystyle H} if for all g 1 , g 2 ∈ G , f ( g 1 ) = f ( g 2 ) {\displaystyle g_{1},g_{2}\in G,f(g_{1})=f(g_{2})} if and only if g 1 H = g 2 H {\displaystyle g_{1}H=g_{2}H} . Equivalently, f {\displaystyle f} is constant on each coset of H, while it is different between the different cosets of H. Hidden subgroup problem: Let G {\displaystyle G} be a group, X {\displaystyle X} a finite set, and f : G → X {\displaystyle f:G\to X} a function that hides a subgroup H ≤ G {\displaystyle H\leq G} . The function f {\displaystyle f} is given via an oracle, which uses O ( log ⁡ | G | + log ⁡ | X | ) {\displaystyle O(\log |G|+\log |X|)} bits. Using information gained from evaluations of f {\displaystyle f} via its oracle, determine a generating set for H {\displaystyle H} . A special case is when X {\displaystyle X} is a group and f {\displaystyle f} is a group homomorphism in which case H {\displaystyle H} corresponds to the kernel of f {\displaystyle f} . The hidden subgroup problem is especially important in the theory of quantum computing for the following reasons. There is an efficient quantum algorithm for solving HSP over finite abelian groups in time polynomial in log ⁡ | G | {\displaystyle \log |G|} .