Lecturer: Gábor Ivanyos

In quantum algorithms for the hidden subgroup problem an efficient solution to finding hidden subgroups in the semidirect product of (Z and Z^{n} would give an important inductive tool. A standard quantum algorithmic technique reduces this special case of the hidden subgroup problem to the following task, called the Hyperplane Cover problem:
assume that we can draw a sample of points of PG(_{2}n-1,p) according to a distribution which is either uniform or
(nearly) uniform on the points not contained in a specific hyperplane. The task is deciding which is the case.
Using generalized Reed-Muller codes we show that the Hyperplane Cover problem can be solved in time polynomial in n and exponential in p.
The method generalizes to solving an analogous problem in (Z )_{pk} in time polynomial in ^{n}n and exponential in p. We also discuss some related open questions.
^{k} |