Scattered data fitting is a frequently encountered problem for reconstructing an unknown function from given scattered data. Radial basis function (RBF) methods have proven to be highly useful to deal with this problem. We describe two quantum algorithms to efficiently fit scattered data based on globally and compactly supported RBFs respectively. For the globally supported RBF method, the core of the quantum algorithm relies on using coherent states to calculate the radial functions and a nonsparse matrix exponentiation technique for efficiently performing a matrix inversion. A quadratic speedup is achieved in the number of data over the classical algorithms. For the compactly supported RBF method, we mainly use the HHL algorithm as a subroutine to design an efficient quantum procedure that runs in time logarithmic in the number of data, achieving an exponential improvement over the classical methods.
翻译:分层数据安装是从给定的分散数据重建未知函数时经常遇到的一个问题。 辐射基函数( RBF) 方法已证明对解决这一问题非常有用。 我们描述了两种量子算法, 以便有效地匹配分别基于全球和紧密支持的RBF的分散数据。 对于全球支持的 RBF 方法, 量子算法的核心依赖于使用一致的状态来计算辐射函数, 以及一种不偏向的矩阵推导技术来高效地进行矩阵反转。 在经典算法上的数据数量上实现了二次加速。 对于精细支持的 RBF 方法, 我们主要使用 HHL 算法作为子路程来设计一个高效量子程序, 在数据数量上运行时间对数, 实现对古典方法的指数改进 。