论文标题
降低维度的多种学习：量子ISOMAP算法
Manifold Learning for Dimensionality Reduction: Quantum Isomap algorithm
论文作者
论文摘要
ISOMAP算法是一种代表性的多种学习算法。该算法简化了数据分析过程，并广泛用于神经成像，光谱分析和其他领域。但是，在处理大型数据集时，经典的ISOMAP算法变得笨拙。我们的目的是通过量子计算加速经典算法，并提出量子ISOMAP算法。该算法由两个子算法组成。第一个是量子Floyd算法，该算法计算任何两个节点的最短距离。另一个是基于量子Floyd算法的量子isomap算法，该算法为原始高维数据找到了低维表示。最后，我们分析量子Floyd算法实现指数速度而无需采样。此外，量子ISOMAP算法的时间复杂性为$ O（dnpolylogn）$。两种算法都降低了经典算法的时间复杂性。
Isomap algorithm is a representative manifold learning algorithm. The algorithm simplifies the data analysis process and is widely used in neuroimaging, spectral analysis and other fields. However, the classic Isomap algorithm becomes unwieldy when dealing with large data sets. Our object is to accelerate the classical algorithm with quantum computing, and propose the quantum Isomap algorithm. The algorithm consists of two sub-algorithms. The first one is the quantum Floyd algorithm, which calculates the shortest distance for any two nodes. The other is quantum Isomap algorithm based on quantum Floyd algorithm, which finds a low-dimensional representation for the original high-dimensional data. Finally, we analyze that the quantum Floyd algorithm achieves exponential speedup without sampling. In addition, the time complexity of quantum Isomap algorithm is $O(dNpolylogN)$. Both algorithms reduce the time complexity of classical algorithms.
