Improved quantum algorithm for A-optimal projection
Improved quantum algorithm for A-optimal projection
复制标题
DOI：
10.1103/physreva.102.052402
复制
发表时间：
2020-06
影响因子：
2.9
通讯作者：
Shijie Pan;Lin-chun Wan;Hailing Liu;Qing-le Wang;S. Qin;Q. Wen;F. Gao
中科院分区：
文献类型：
--
作者：
Shijie Pan;Lin-chun Wan;Hailing Liu;Qing-le Wang;S. Qin;Q. Wen;F. Gao
降维算法在机器学习和数据挖掘中起着重要的作用，它在尽可能保留原始数据集信息的同时，对给定数据集进行降维。Duan et al.提出了一种量子版本的A-最优投影降维算法(AOP)。Rev.A 99,032311(2019年)]，并声称与经典算法相比，该算法在原始特征空间$n$的维度和约化后的特征空间$k$的维度上有指数级的加速。本文将Duan等人的S算法的复杂性修正为$O({kappa^{4s}\Sqrt{k^S}}{\epsilon^{S}}\mathm{PolyLog}^S(\fRAC{Mn}{\epsilon}))$，其中$\kappa$是与原始数据集相关的矩阵的条件数，$S$是迭代次数，$m$是数据点的数目，$\epsilon$是输出状态的期望精度。由于复杂度与$S$呈指数依赖关系，量子算法只能适用于迭代次数较少的高维问题$S$。为了获得进一步的加速比，我们提出了一种改进的量子面向方面编程算法，其复杂度为$O(S{S^6\sqrt{k}}{\epsilon}\mathrm{polylog}(\frac{nm}{\epsilon})+\FRAC{S^2\kappa^4}{\epsilon}\mathrm{polylog}(\frac{\kappa k}{\epsilon})$。与段等人的S算法相比，当$S$很大时，我们的算法获得了接近指数级的加速比，即使$S$是一个小常数，我们的算法也达到了多项式的加速比。此外，与经典算法相比，当$kappa$、$k$和$1/epsilon$都是$O(\mathm{PolyLog}(Nm))$时，我们的算法在$n$和$m$上表现出指数加速比。
Dimensionality reduction (DR) algorithms, which reduce the dimensionality of a given data set while preserving the information of original data set as well as possible, play an important role in machine learning and data mining. Duan et al. proposed a quantum version of 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 complexity of Duan et al.'s algorithm to $O(\frac{\kappa^{4s}\sqrt{k^s}} {\epsilon^{s}}\mathrm{polylog}^s (\frac{mn}{\epsilon}))$, where $\kappa$ 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 $\epsilon$ is the desired precision of the output state. Since the 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 proposed an improved quantum AOP algorithm with complexity $O(\frac{s \kappa^6 \sqrt{k}}{\epsilon}\mathrm{polylog}(\frac{nm}{\epsilon}) + \frac{s^2 \kappa^4}{\epsilon}\mathrm{polylog}(\frac{\kappa k}{\epsilon}))$. Our algorithm achieves a nearly exponential speedup if $s$ is large and a polynomial speedup even if $s$ is a small constant compared with Duan et al.'s algorithm. Also, our algorithm shows exponential speedups in $n$ and $m$ compared with the classical algorithm when both $\kappa$, $k$ and $1/\epsilon$ are $O(\mathrm{polylog}(nm))$.