Ad-Hoc Networks
- PDF / 3,386,479 Bytes
- 81 Pages / 547.087 x 737.008 pts Page_size
- 94 Downloads / 265 Views
A
A
Abelian Hidden Subgroup Problem 1995; Kitaev MICHELE MOSCA 1,2 1 Combinatorics and Optimization / Institute for Quantum Computing, University of Waterloo, Waterloo, ON, Canada 2 Perimeter Institute for Theoretical Physics, St. Jerome’s University, Waterloo, ON, Canada
Keywords and Synonyms Generalization of Abelian stabilizer problem; Generalization of Simon’s problem Problem Definition The Abelian hidden subgroup problem is the problem of finding generators for a subgroup K of an Abelian group G, where this subgroup is defined implicitly by a function f : G ! X, for some finite set X. In particular, f has the property that f (v) = f (w) if and only if the cosets1 v + K and w + K are equal. In other words, f is constant on the cosets of the subgroup K, and distinct on each coset. It is assumed that the group G is finitely generated and that the elements of G and X have unique binary encodings (the binary assumption is not so important, but it is important to have unique encodings.) When using variables g and h (possibly with subscripts) multiplicative notation is used for the group operations. Variables x and y (possibly with subscripts) will denote integers with addition. The boldface versions x and y will denote tuples of integers or binary strings. By assumption, there is computational means of computing the function f , typically a circuit or “black box” that maps the encoding of a value g to the encoding of f (g). The 1 Assuming
additive notation for the group operation here.
theory of reversible computation implies that one can turn a circuit for computing f (g) into a reversible circuit for computing f (g) with a modest increase in the size of the circuit. Thus it will be assumed that there is a reversible circuit or black box that maps (g; z) 7! (g; z ˚ f (g)), where ˚ denotes the bitwise XOR (sum modulo 2), and z is any binary string of the same length as the encoding of f (g). Quantum mechanics implies that any reversible gate can be extended linearly to a unitary operation that can be implemented in the model of quantum computation. Thus, it is assumed that there is a quantum circuit or black box that implements the unitary map U f : jgijzi 7! jgijz ˚ f (g)i. Although special cases of this problem have been considered in classical computer science, the general formulation as the hidden subgroup problem seems to have appeared in the context of quantum computing, since it neatly encapsulates a family of “black-box” problems for which quantum algorithms offer an exponential speed up (in terms of query complexity) over classical algorithms. For some explicit problems (i. e., where the black box is replaced with a specific function, such as exponentiation modulo N), there is a conjectured exponential speed up. Abelian Hidden Subgroup Problem Input: Elements g1 ; g2 ; : : : ; g n 2 G that generate the Abelian group G. A black box that implements U f : jm1 ; m2 ; : : : ; m n ijyi 7! jm1 ; m2 ; : : : ; m n ij f (g) ˚ yi, where g = g1m1 g2m2 : : : g nm n , and K is the hidden subgroup corresponding to f . Outp
Data Loading...
