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:
“For believe me!—the secret to harvesting the greatest abundance and the greatest enjoyment from existence is this—living dangerously! Build your cities on the slopes of Vesuvius! Send your ships into uncharted seas! Live at war with your peers and yourselves! Be robbers and conquerors, so long as you cannot be rulers and possessors, you knowing ones! The time will soon be past when you could be content to live hidden in the forests like timid deer.”
—Friedrich Nietzsche (1844–1900)
“One thing in any case is certain: man is neither the oldest nor the most constant problem that has been posed for human knowledge.”
—Michel Foucault (1926–1984)