Hidden subgroup problem: Let G be a group, X a finite set, and f : G → X a function that hides a subgroup H ≤ G. The function f is given via an oracle, which uses O(log |G|+log|X|) bits. Using information gained from evaluations of f via its oracle, determine a generating set for H.
A special case is when X is a group and f is a group homomorphism in which case H corresponds to the kernel of f.
Read more about Hidden Subgroup Problem: Motivation, Algorithms
Famous quotes containing the words hidden and/or problem:
“The chess-board is the world; the pieces are the phenomena of the universe; the rules of the game are what we call the laws of Nature. The player on the other side is hidden from us. We know that his play is always fair, just, and patient. But also we know, to our cost, that he never overlooks a mistake, or makes the smallest allowance for ignorance.”
—Thomas Henry Huxley (1825–1895)
“What had really caused the women’s movement was the additional years of human life. At the turn of the century women’s life expectancy was forty-six; now it was nearly eighty. Our groping sense that we couldn’t live all those years in terms of motherhood alone was “the problem that had no name.” Realizing that it was not some freakish personal fault but our common problem as women had enabled us to take the first steps to change our lives.”
—Betty Friedan (20th century)