Quantum algorithm for multivariate polynomial interpolation. (17th 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-17
• 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 fieldsF q, R andC . We show thatk C and2 k C queries suffice to achieve probability 1 forC andR, respectively, wherek C = ⌈ ( 1 / ( n + 1 ) ) ( n + d d ) ⌉ except for d =2 and four other special cases. ForF 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 forC, R andF 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 ofF q, we conjecture that2 k C queries also suffice to achieve probability approaching 1 for large field order q, although we leave this as an open problem.