×

Quantum interpolation of polynomials. (English) Zbl 1234.81057

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.

MSC:

81P68 Quantum computation
68Q12 Quantum algorithms and complexity in the theory of computing
97N50 Interpolation and approximation (educational aspects)
PDFBibTeX XMLCite