Quantum algorithm for multivariate polynomial interpolation
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
How many quantum queries are required to determine the coefficients of a degree-d polynomial in n variables? We present and analyse quantum algorithms for this multivariate polynomial interpolation problem over the fields Fq, R and C. We show that kC and 2kC queries suffice to achieve probability 1 for C and R, respectively, where kC=⌈(1/(n+1))(n+dd)⌉ except for d=2 and four other special cases. For Fq, we show that ⌈(d/(n+d))(n+d d) ⌉ queries suffice to achieve probability approaching 1 for large field order q. The classical query complexity of this problem is (n+d d) , so our result provides a speed-up by a factor of n+1, (n+1)/2 and (n+d)/d for C, R and Fq, respectively. Thus, we find a much larger gap between classical and quantum algorithms than the univariate case, where the speedup is by a factor of 2. For the case of Fq, we conjecture that 2kC queries also suffice to achieve probability approaching 1 for large field order q, although we leave this as an open problem.