Kane, Daniel M.; Kutin, Samuel A. Quantum interpolation of polynomials. (English) Zbl 1234.81057 Quantum Inf. Comput. 11, No. 1-2, 95-103 (2011). Summary: 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 \((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. Cited in 2 Documents MSC: 81P68 Quantum computation 68Q12 Quantum algorithms and complexity in the theory of computing 97N50 Interpolation and approximation (educational aspects) PDFBibTeX XMLCite \textit{D. M. Kane} and \textit{S. A. Kutin}, Quantum Inf. Comput. 11, No. 1--2, 95--103 (2011; Zbl 1234.81057)