1105.3310 (Ashley Montanaro)

The quantum query complexity of learning multilinear polynomials    [PDF]

Ashley Montanaro

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 F_q. Any bounded-error classical algorithm for this task requires Omega(n^d) queries to the polynomial. We give an exact quantum algorithm that uses O(n^(d-1)) queries for constant d, which is optimal. In the case q=2, this gives a quantum algorithm that uses O(n^(d-1)) queries to identify a codeword picked from the binary Reed-Muller code of order d.

View original: http://arxiv.org/abs/1105.3310