Fetching the paper…

Reading the bibliography…

2011

The quantum query complexity of learning multilinear polynomials

Montanaro, Ashley

Original
PDF
Post on X

Understand

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.

The quantum query complexity of learning multilinear polynomials · Around

Built on

Bounds for the quantity of information transmitted by a quantum communication channel
A. S. Holevo · 1973
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1997
Earlier work this paper cites.
Finite fields
R. Lidl and H. Niederreiter · 1997
Earlier work this paper cites.
Quantum entanglement and the communication complexity of the inner product function
R. Cleve, W. van Dam, M. Nielsen, and A. Tapp · 1998
Earlier work this paper cites.
How many functions can be distinguished with k quantum queries?, 1999
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser · 1999
Earlier work this paper cites.

Similar

Quantum versus classical learnability
R. Servedio and S. Gortler · 2001
Cited alongside, same era.
Sharp quantum versus classical query complexity separations
J. Niel de Beaudrap, R. Cleve, and J. Watrous · 2002
Cited alongside, same era.
Lower bounds on quantum query complexity
P. Høyer and R. Špalek · 2005
Cited alongside, same era.
Elements of Information Theory
T. Cover and J. Thomas · 2006
Cited alongside, same era.

Then

Quantum algorithms for some hidden shift problems
W. van Dam, S. Hallgren, and L. Ip · 2006
Later among the works it cites.
Testing polynomials over general fields
T. Kaufman and D. Ron · 2006
Later among the works it cites.
Quantum computation beyond the circuit model
Original
S. Jordan · 2008
Later among the works it cites.
Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm
Original
M. Rötteler · 2009
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…