# Quantum algorithm for multivariate polynomial interpolation

 Title Quantum algorithm for multivariate polynomial interpolation Publication Type Journal Article Year of Publication 2018 Authors Chen, J, Childs, AM, Hung, S-H Journal Proceedings of The Royal Society A Volume 474 Issue 2209 Date Published 2018/01/17 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 Fq, R, and C. We show that kC and 2kC queries suffice to achieve probability 1 for C and R, respectively, where kC = ⌈ 1 n+1 ( n+d d )⌉ except for d = 2 and four other special cases. For Fq, we show that ⌈ d n+d ( n+d d )⌉ 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. URL http://rspa.royalsocietypublishing.org/content/474/2209/20170480 DOI 10.1098/rspa.2017.0480