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:
“Yet there is a mystery here and it is not one that I understand: without the sting of otherness, of—even—the vicious, without the terrible energies of the underside of health, sanity, sense, then nothing works or can work. I tell you that goodness-what we in our ordinary daylight selves call goodness: the ordinary, the decent—these are nothing without the hidden powers that pour forth continually from their shadow sides. Their hidden aspects contained and tempered.”
—Doris Lessing (b. 1919)
“We have heard all of our lives how, after the Civil War was over, the South went back to straighten itself out and make a living again. It was for many years a voiceless part of the government. The balance of power moved away from it—to the north and the east. The problems of the north and the east became the big problem of the country and nobody paid much attention to the economic unbalance the South had left as its only choice.”
—Lyndon Baines Johnson (1908–1973)