论文标题
改进了A-最佳投影的量子算法
Improved quantum algorithm for A-optimal projection
论文作者
论文摘要
降低维度降低（DR）算法，在保留原始数据集的信息的同时，降低了给定数据集的维度，在机器学习和数据挖掘中起着重要作用。 duan \ emph {et al}。提出了用于降低维度的A-最佳投影算法（AOP）的量子版本[Phys。 Rev. A 99，032311（2019）]并声称该算法对原始特征空间$ n $的维度和经典算法上还原功能空间$ K $的维度具有指数加速。在本文中，我们纠正了duan \ emph {et al}的时间复杂性。与原始数据集有关的矩阵，$ s $是迭代的数量，$ m $是数据点的数量，$ε$是输出状态的所需精度。由于时间复杂性对$ s $具有指数依赖性，因此量子算法只能对高维问题和少量迭代$ s $有益。为了获得进一步的加速，我们提出了一种改进的量子AOP算法，具有时间复杂性$ o（\ frac {Sκ^6 \ sqrt {k}}ε\ mathrm {polylog}（\ frac {nm} κ^4}ε\ mathrm {polylog}（\ frac {κK}ε））$和空间复杂度$ o（\ log_2（nk/ε）+s）$。与Duan \ emph {et al}的算法相比，我们的算法稍差，我们的算法至少达到了多项式加速。此外，与经典算法相比，当$κ$，$ k $和$ 1/ε$是$ o（\ mathrm {polylog}（nm））$时，我们的算法显示了$ n $和$ m $的指数加速。
Dimensionality reduction (DR) algorithms, which reduce the dimensionality of a given data set while preserving the information of the original data set as well as possible, play an important role in machine learning and data mining. Duan \emph{et al}. proposed a quantum version of the A-optimal projection algorithm (AOP) for dimensionality reduction [Phys. Rev. A 99, 032311 (2019)] and claimed that the algorithm has exponential speedups on the dimensionality of the original feature space $n$ and the dimensionality of the reduced feature space $k$ over the classical algorithm. In this paper, we correct the time complexity of Duan \emph{et al}.'s algorithm to $O(\frac{κ^{4s}\sqrt{k^s}} {ε^{s}}\mathrm{polylog}^s (\frac{mn}ε))$, where $κ$ is the condition number of a matrix that related to the original data set, $s$ is the number of iterations, $m$ is the number of data points and $ε$ is the desired precision of the output state. Since the time complexity has an exponential dependence on $s$, the quantum algorithm can only be beneficial for high dimensional problems with a small number of iterations $s$. To get a further speedup, we propose an improved quantum AOP algorithm with time complexity $O(\frac{s κ^6 \sqrt{k}}ε\mathrm{polylog}(\frac{nm}ε) + \frac{s^2 κ^4}ε\mathrm{polylog}(\frac{κk}ε))$ and space complexity $O(\log_2(nk/ε)+s)$. With space complexity slightly worse, our algorithm achieves at least a polynomial speedup compared to Duan \emph{et al}.'s algorithm. Also, our algorithm shows exponential speedups in $n$ and $m$ compared with the classical algorithm when both $κ$, $k$ and $1/ε$ are $O(\mathrm{polylog}(nm))$.
