



@article {1922,
	title = {Quantum algorithm for multivariate polynomial interpolation},
	journal = {Proceedings of The Royal Society A},
	volume = {474},
	year = {2018},
	month = {2018/01/17},
	abstract = {<p>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 kC and 2kC queries suffice to achieve probability 1 for C and R, respectively, where kC = \&lceil; 1 n+1 ( n+d d )\&rceil; except for d = 2 and four other special cases. For Fq, we show that \&lceil; d n+d ( n+d d )\&rceil; 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 speedup 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.</p>},
	doi = {10.1098/rspa.2017.0480},
	url = {http://rspa.royalsocietypublishing.org/content/474/2209/20170480},
	author = {Jianxin Chen and Andrew M. Childs and Shih-Han Hung}
}
