Quantum interpolation of polynomials
Daniel M. Kane, Samuel Kutin · Quantum Information and Computation · 2011
Can a quantum computer efficiently interpolate polynomials? We consider black-box algorithms that seek to learn information about a polynomial $f$ from input/output pairs $(x_i, f(x_i))$. We define a more general class of \emph{$(d,S)$-independent} function properties, where, outside of a set $S$ of exceptions, knowing $d$ input values does not help one predict the answer. There are essentially two strategies to computing such a function: query $d+1$ random input values, or search for one of the $|S|$ exceptions. We show that, up to constant factors, we cannot beat these two approaches.