Lecturer: Gábor Ivanyos
|
In quantum algorithms for the hidden subgroup problem an efficient solution to finding hidden subgroups in the semidirect product of (Zp )n and Z2 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(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 (Zpk )n in time polynomial in n and exponential in pk. We also discuss some related open questions. |