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:
“Impenetrable in their dissimulation, cruel in their vengeance, tenacious in their purposes, unscrupulous as to their methods, animated by profound and hidden hatred for the tyranny of man—it is as though there exists among them an ever-present conspiracy toward domination, a sort of alliance like that subsisting among the priests of every country.”
—Denis Diderot (1713–1784)
“Every child is an artist. The problem is how to remain an artist once he grows up.”
—Pablo Picasso (1881–1973)