The quantum query complexity of learning multilinear polynomials

In this note we study the number of quantum queries required to identify an unknown multilinear polynomial of degree d in n   variables over a finite field FqFq. Any bounded-error classical algorithm for this task requires Ω(nd)Ω(nd) queries to the polynomial. We give an exact quantum algorithm that uses O(nd−1)O(nd−1) queries for constant d  , which is optimal. In the case q=2q=2, this gives a quantum algorithm that uses O(nd−1)O(nd−1) queries to identify a codeword picked from the binary Reed–Muller code of order d.

► An efficient quantum algorithm for learning multilinear polynomials is given. ► The algorithm allows efficient learning of binary Reed–Muller codes. ► The algorithm is asymptotically optimal.