  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}}=\smash{\lceil\frac{1}{n+1}{n+d\choose d}\rceil}$ except for
$d=2$ and four other special cases. For $\mathbb{F}_q$, we show that
$\smash{\lceil\frac{d}{n+d}{n+d\choose d}\rceil}$ queries suffice to achieve
probability approaching $1$ for large field order $q$. The classical query
complexity of this problem is $\smash{n+d\choose d}$, 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.
