An Application of Generalized Reed-Muller Codes to Quantum Computing.

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.

back to EIDMA Seminar Combinatorial Theory announcements