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 human face is a weak guarantee; yet it deserves some consideration. And if I had to whip the wicked, I would do so more severely to those who belied and betrayed the promises that nature had implanted on their brows; I would punish malice more harshly when it was hidden under a kindly appearance.”
—Michel de Montaigne (1533–1592)
“Involuntary mental hospitalization is like slavery. Refining the standards for commitment is like prettifying the slave plantations. The problem is not how to improve commitment, but how to abolish it.”
—Thomas Szasz (b. 1920)