The hidden subgroup problem asks for a subgroup H≤G given an oracle f:G→X that is constant on each left coset of H and takes different values on different cosets. Abelian instances are solved by preparing coset states and applying a group quantum Fourier transform.
For a group action F:G×X→X and fixed x, the orbit map fx(g)=F(g,x) hides the stabilizer subgroup Gx: fx(g)=fx(h) exactly when h−1g∈Gx, equivalently when g and h lie in the same left coset of Gx.
Ancestors (5)
Incoming links (2)
Discussion (0)
New discussionThere are no discussions about this article yet.
Articles by others on the same topic (1)
The Hidden Subgroup Problem (HSP) is a central problem in the field of computational group theory and quantum computing. It is a generalization of several important problems, including the factoring problem and the discrete logarithm problem, both of which are of significant interest in cryptography.