论文标题
用于向量插值的最佳量子算法
Optimal Quantum Algorithm for Vector Interpolation
论文作者
论文摘要
在本文中，我们研究了可以通过Childs等人设计的多项式插值量子算法学习的功能。该算法最初旨在找到在有限字段上定义的多元多项式函数的系数，$ \ mathbb {f} _q $。我们将其范围扩展到表格$ \ Mathcal {o} _ {\ MathBf {s}}}（\ MathBf {V}）= \ Mathbf {s} \ CDOT \ CDOT \ CDOT \ MATHBF {V} $的目标是找到Vector $ \ Mathbf {S s}的目标， \ mathbb {f} _q^n $。我们检查了$ \ Mathcal {v} $ $ \ Mathcal {o} _ {\ Mathbf {s}} $的必要条件，并证明该算法对于此类函数是最佳的。此外，我们表明，成功的概率对1的$ Q $和大域订单$ | \ Mathcal {V} |。$最终，我们为实现此成功概率提供了保守的查询次数。
In this paper we study the functions that can be learned through the polynomial interpolation quantum algorithm designed by Childs et al. This algorithm was initially intended to find the coefficients of a multivariate polynomial function defined on finite fields $\mathbb{F}_q$. We extend its scope to vector inner product functions of the form $\mathcal{O}_{\mathbf{s}}(\mathbf{v}) = \mathbf{s}\cdot\mathbf{v}$ where the goal is to find the vector $\mathbf{s} \in \mathbb{F}_q^n$. We examine the necessary conditions on the domain $\mathcal{V}$ of $\mathcal{O}_{\mathbf{s}}$ and prove that the algorithm is optimal for such functions. Furthermore, we show that the success probability approaches 1 for large $q$ and large domain order $|\mathcal{V}|.$ Finally, we provide a conservative formula for the number of queries required to achieve this success probability.
