Quantum algorithm for multivariate polynomial interpolation. (31st January 2018)

• Record Type: Journal Article
• Authors: Chen, Jianxin; Childs, Andrew M.; Hung, Shih-Han
• Is Part Of: Proceedings. Volume 474:Number 2209(2018)
• Publication Date: 2018-01-31
• Subjects: quantum algorithms -- query complexity -- polynomial interpolation; Physical sciences -- Periodicals; Engineering -- Periodicals; Mathematics -- Periodicals; 500
• DOI: 10.1098/rspa.2017.0480
• Languages: English
• ISSNs: 1364-5021

Abstract

Abstract : How many quantum queries are required to determine the coefficients of a degree- d polynomial in n variables? We present and analyse quantum algorithms for this multivariate polynomial interpolation problem over the fields F q, R and C . We show that k C and 2 k C queries suffice to achieve probability 1 for C and R, respectively, where k C = ⌈ ( 1 / ( n + 1 ) ) ( n + d d ) ⌉ except for d =2 and four other special cases. For F q, 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 speed-up by a factor of n +1, ( n +1)/2 and ( n + d )/ d for C, R and 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 F q, we conjecture that 2 k C queries also suffice to achieve probability approaching 1 for large field order q, although we leave this as an open problem.