Quantum algorithm for multivariate polynomial interpolation

Abstract

How many quantum queries are required to determine the coefficients of a degree-$d$ polynomial in $n$ variables? We present and analyze quantum algorithms for this multivariate polynomial interpolation problem over the fields ${\mathbb{F}}_q$, $\mathbb{R}$, and $\mathbb{C}$. We show that $k_{\mathbb{C}}$ and $2k_{\mathbb{C}}$ queries suffice to achieve probability $1$ for $\mathbb{C}$ and $\mathbb{R}$, respectively, where $k_{\mathbb{C}}=\lceil \frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{n+d}{d}\right)\rceil$ except for $d=2$ and four other special cases. For ${\mathbb{F}}_q$, we show that $\lceil \frac{d}{n+d}\left(\genfrac{}{}{0ex}{}{n+d}{d}\right)\rceil$ queries suffice to achieve probability approaching $1$ for large field order $q$. The classical query complexity of this problem is $\left(\genfrac{}{}{0ex}{}{n+d}{d}\right)$, so our result provides a speedup by a factor of $n+1$, $\frac{n+1}{2}$, and $\frac{n+d}{d}$ for $\mathbb{C}$, $\mathbb{R}$, and ${\mathbb{F}}_q$, 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 ${\mathbb{F}}_q$, we conjecture that $2k_{\mathbb{C}}$ queries also suffice to achieve probability approaching $1$ for large field order $q$, although we leave this as an open problem.