Quantum Manifold Learning Algorithms for Dimensionality Reduction

Manifold learning is a kind of method which discusses the machine learning problems under the manifold hypothesis. It assumes that the sampled high-dimensional data actually comes from the embedding of some low-dimensional manifold structure. Manifold learning has wide range of applications in dimensionality reduction and data visualization. In the field of manifold learning, two most representative and commonly used algorithms are isometric mapping and locally linear embedding. Using techniques of quantum computing, we research out two quantum algorithms in correspondence to them. Compared with corresponding classical algorithms, the two quantum algorithms proposed in this paper can be implemented on a quantum computer with quantum speed-up. Quantum isometric mapping provides at least quadratic acceleration and quantum locally linear embedding takes logarithmic resources. In addition, we attempt to find out a common process to deal with quantization of manifold learning algorithms.