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:
“It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
—François, Duc De La Rochefoucauld (1613–1680)
“Hypocrisy is the essence of snobbery, but all snobbery is about the problem of belonging.”
—Alexander Theroux (b. 1940)