Quantum algorithms for SVD-based data representation and analysis

Abstract

This paper narrows the gap between previous literature on quantum linear algebra and practical data analysis on a quantum computer, formalizing quantum procedures that speed-up the solution of eigenproblems for data representations in machine learning. The power and practical use of these subroutines is shown through new quantum algorithms, sublinear in the input matrix's size, for principal component analysis, correspondence analysis, and latent semantic analysis. We provide a theoretical analysis of the run-time and prove tight bounds on the randomized algorithms' error. We run experiments on multiple datasets, simulating PCA's dimensionality reduction for image classification with the novel routines. The results show that the run-time parameters that do not depend on the input's size are reasonable and that the error on the computed model is small, allowing for competitive classification performances.

References in corpus (24)

• Scikit-learn: Machine Learning in Python
• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum random access memory
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Quantum gradient descent for linear systems and least squares
• Quantum Algorithm for Linear Regression
• Quantum singular value decomposition of non-sparse low-rank matrices
• Quantum-inspired algorithms in practice
• q-means: A quantum algorithm for unsupervised machine learning
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Quantum data compression by principal component analysis
• Quantum Algorithms for Deep Convolutional Neural Networks
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Variational Quantum Singular Value Decomposition
• Resilience of quantum random access memory to generic noise
• Quantum Singular Value Decomposer
• Quantum classification of the MNIST dataset with Slow Feature Analysis
• Quantum Expectation-Maximization for Gaussian Mixture Models
• Quantum-inspired canonical correlation analysis for exponentially large dimensional data
• Quantum Latent Semantic Analysis

Cited by in corpus (2)

• Evaluating the Potential of Quantum Machine Learning in Cybersecurity: A Case-Study on PCA-based Intrusion Detection Systems
• On Modifying the Variational Quantum Singular Value Decomposition Algorithm