Quantum locally linear embedding for nonlinear dimensionality reduction

Abstract

Reducing the dimension of nonlinear data is crucial in data processing and visualization. The locally linear embedding algorithm (LLE) is specifically a representative nonlinear dimensionality reduction method with well maintaining the original manifold structure. In this paper, we present two implementations of the quantum locally linear embedding algorithm (QLLE) to perform the nonlinear dimensionality reduction on quantum devices. One implementation, the linear-algebra-based QLLE algorithm, utilizes quantum linear algebra subroutines to reduce the dimension of the given data. The other implementation, the variational quantum locally linear embedding algorithm (VQLLE) utilizes a variational hybrid quantum-classical procedure to acquire the low-dimensional data. The classical LLE algorithm requires polynomial time complexity of $N$, where $N$ is the global number of the original high-dimensional data. Compared with the classical LLE, the linear-algebra-based QLLE achieves quadratic speedup in the number and dimension of the given data. The VQLLE can be implemented on the near term quantum devices in two different designs. In addition, the numerical experiments are presented to demonstrate that the two implementations in our work can achieve the procedure of locally linear embedding.

20 pages, 7 figures

References in corpus (22)

• Scikit-learn: Machine Learning in Python
• A variational eigenvalue solver on a quantum processor
• Quantum algorithm for solving linear systems of equations
• Supervised learning with quantum enhanced feature spaces
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum fingerprinting
• Quantum generative adversarial learning
• Quantum Data Fitting
• Quantum generative adversarial networks
• Variational Quantum Computation of Excited States
• An approximate Fourier transform useful in quantum factoring
• Prediction by linear regression on a quantum computer
• Variational Quantum State Diagonalization
• Addition on a Quantum Computer
• Approximate Quantum Fourier Transform and Decoherence
• Quantum Discriminant Analysis for Dimensionality Reduction and Classification
• Fast versions of Shor's quantum factoring algorithm
• Quantum linear systems algorithms: a primer
• Quantum algorithm and quantum circuit for A-Optimal Projection: dimensionality reduction
• Short-depth circuits for efficient expectation value estimation
• Quantum correlation alignment for unsupervised domain adaptation

Cited by in corpus (1)

• Quantum correlation alignment for unsupervised domain adaptation