Quantum algorithm for neighborhood preserving embedding
Quantum algorithm for neighborhood preserving embedding
复制标题
DOI：
10.1088/1674-1056/ac523a
复制
发表时间：
2021-10
影响因子：
1.7
通讯作者：
Shi-Jie 世杰 Pan 潘;Lin-Chun 林春 Wan 万;Hai-Ling 海玲 Liu 刘;Yu-Sen 宇森 Wu 吴;Su-Juan 素娟 Qin 秦;Q. Wen 温;F. Gao 高
中科院分区：
文献类型：
--
作者：
Shi-Jie 世杰 Pan 潘;Lin-Chun 林春 Wan 万;Hai-Ling 海玲 Liu 刘;Yu-Sen 宇森 Wu 吴;Su-Juan 素娟 Qin 秦;Q. Wen 温;F. Gao 高
邻域保持嵌入（NPE）是一种重要的线性降维技术，旨在保持局部流形结构。NPE包含三个步骤，即，找到每个数据点的最近邻，构造权矩阵，得到变换矩阵。Liang等人提出了一种用于NPE的变分量子算法（VQA）[Phys. Rev. A 101 032323（2020）]。该算法由三个量子子算法组成，对应于NPE的三个步骤，并且预计在维数n上具有指数加速比。然而，该算法具有两个缺点：（i）不知道如何从第二子算法的输出有效地获得第三子算法的输入。(ii)它的复杂性不能严格分析，因为它的第三个子算法是一个VQA。在本文中，我们提出了一个完整的量子算法的NPE，我们重新设计的三个子算法，并给出了严格的复杂性分析。结果表明，与经典的NPE算法相比，在一定条件下，该算法在数据点数m上具有多项式加速比，在维数n上具有指数加速比，与Liang等人的算法相比，该算法具有显著的加速比.的算法，即使不考虑复杂性的VQA。
Neighborhood preserving embedding (NPE) is an important linear dimensionality reduction technique that aims at preserving the local manifold structure. NPE contains three steps, i.e., finding the nearest neighbors of each data point, constructing the weight matrix, and obtaining the transformation matrix. Liang et al. proposed a variational quantum algorithm (VQA) for NPE [Phys. Rev. A 101 032323 (2020)]. The algorithm consists of three quantum sub-algorithms, corresponding to the three steps of NPE, and was expected to have an exponential speedup on the dimensionality n. However, the algorithm has two disadvantages: (i) It is not known how to efficiently obtain the input of the third sub-algorithm from the output of the second one. (ii) Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA. In this paper, we propose a complete quantum algorithm for NPE, in which we redesign the three sub-algorithms and give a rigorous complexity analysis. It is shown that our algorithm can achieve a polynomial speedup on the number of data points m and an exponential speedup on the dimensionality n under certain conditions over the classical NPE algorithm, and achieve a significant speedup compared to Liang et al.’s algorithm even without considering the complexity of the VQA.