Quantum algorithm for multivariate polynomial interpolation

Jianxin Chen, Andrew M. Childs, Shih-Han Hung

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 pol…