Chen Jianxin, Childs Andrew M, Hung Shih-Han
Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD 20742, USA.
Department of Computer Science, University of Maryland, College Park, MD 20742, USA.
Proc Math Phys Eng Sci. 2018 Jan;474(2209):20170480. doi: 10.1098/rspa.2017.0480. Epub 2018 Jan 17.
How many quantum queries are required to determine the coefficients of a degree- polynomial in variables? We present and analyse quantum algorithms for this multivariate polynomial interpolation problem over the fields [Formula: see text], [Formula: see text] and [Formula: see text]. We show that [Formula: see text] and [Formula: see text] queries suffice to achieve probability 1 for [Formula: see text] and [Formula: see text], respectively, where [Formula: see text] except for =2 and four other special cases. For [Formula: see text], we show that ⌈(/(+))(+) ⌉ queries suffice to achieve probability approaching 1 for large field order . The classical query complexity of this problem is (+) , so our result provides a speed-up by a factor of +1, (+1)/2 and (+)/ for [Formula: see text], [Formula: see text] and [Formula: see text], 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 [Formula: see text], we conjecture that [Formula: see text] queries also suffice to achieve probability approaching 1 for large field order , although we leave this as an open problem.
确定一个(n)元(d)次多项式的系数需要多少量子查询？我们针对有限域(\mathbb{Z}p)、(\mathbb{Z}{p^k})和(\mathbb{F}_q)上的这个多元多项式插值问题，给出并分析了量子算法。我们证明，对于(\mathbb{Z}p)和(\mathbb{Z}{p^k})，分别有(n)和(2n)次查询就足以达到概率为(1)，其中(p\neq2)以及其他四种特殊情况除外。对于(\mathbb{F}_q)，我们证明，对于大的域阶(q)，(\lceil(n/(d + 1))(d + 1)\rceil)次查询足以达到概率趋近于(1)。这个问题的经典查询复杂度是(\Omega(n(d + 1)))，所以我们的结果分别为(\mathbb{Z}p)、(\mathbb{Z}{p^k})和(\mathbb{F}_q)提供了(d + 1)、((d + 1)/2)和((d + 1)/n)倍的加速。因此，我们发现经典算法和量子算法之间的差距比单变量情况大得多，在单变量情况下加速因子为(2)。对于(\mathbb{F}_q)的情况，我们猜想对于大的域阶(q)，(n(d + 1))次查询也足以达到概率趋近于(1)，不过我们将此留作一个开放问题。
