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