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 $\Fq$, $\R$, and $\C$. We show that $k_{\C}$ and $2k_{\C}$ queries suffice to achieve probability $1$ for $\C$ and $\R$, respectively, where $k_{\C}=\smash{\lceil\frac{1}{n+1}{n+d\choose d}\rceil}$ except for $d=2$ and four other special cases. For $\Fq$, 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 $\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 $2k_{\C}$ queries also suffice to achieve probability approaching $1$ for large field order $q$, although we leave this as an open problem.