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:
“A hidden strength
Which if Heav’n gave it, may be term’d her own:
‘Tis chastity, my brother, chastity:
She that has that, is clad in compleat steel,
And like a quiver’d Nymph with Arrows keen
May trace huge Forests, and unharbour’d Heaths,
Infamous Hills, and sandy perilous wildes,
Where through the sacred rayes of Chastity,
No savage fierce, Bandite, or mountaneer
Will dare to soyl her Virgin purity,”
—John Milton (1608–1674)
“The government is huge, stupid, greedy and makes nosy, officious and dangerous intrusions into the smallest corners of life—this much we can stand. But the real problem is that government is boring. We could cure or mitigate the other ills Washington visits on us if we could only bring ourselves to pay attention to Washington itself. But we cannot.”
—P.J. (Patrick Jake)