Identifying Generalized Reed-Muller Codewords by Quantum Queries

We provide an exact quantum query algorithm that identifies uncorrupted codewords from a degree-d generalized Reed-Muller code of length qⁿ over the finite field of size q. When d is constant, the algorithm needs 𝒪(n^d-1) quantum queries, which is optimal. Classically, Ω(n^d) queries are necessary to accomplish this task, even with constant probability of error admitted. Our work extends a result by Montanaro about learning multilinear polynomials.