Quantum data compression by principal component analysis

Abstract

Data compression can be achieved by reducing the dimensionality of high-dimensional but approximately low-rank datasets, which may in fact be described by the variation of a much smaller number of parameters. It often serves as a preprocessing step to surmount the curse of dimensionality and to gain efficiency, and thus it plays an important role in machine learning and data mining. In this paper, we present a quantum algorithm that compresses an exponentially large high-dimensional but approximately low-rank dataset in quantum parallel, by dimensionality reduction (DR) based on principal component analysis (PCA), the most popular classical DR algorithm. We show that the proposed algorithm achieves exponential speedup over the classical PCA algorithm when the original dataset are projected onto a polylogarithmically low-dimensional space. The compressed dataset can then be further processed to implement other tasks of interest, with significantly less quantum resources. As examples, we apply this algorithm to reduce data dimensionality for two important quantum machine learning algorithms, quantum support vector machine and quantum linear regression for prediction. This work demonstrates that quantum machine learning can be released from the curse of dimensionality to solve problems of practical importance.

12 pages,4 figures; Slight changes made to the abstract and the 1st paragraph of Sec.II

References in corpus (33)

• Quantum Machine Learning
• Elementary gates for quantum computation
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum fingerprinting
• Circuit-centric quantum classifiers
• Quantum random access memory
• Quantum algorithms for supervised and unsupervised machine learning
• Quantum Data Fitting
• Prediction by linear regression on a quantum computer
• Experimental Realization of Quantum Artificial Intelligence
• Experimental Quantum Hamiltonian Learning
• Implementing a distance-based classifier with a quantum interference circuit
• A quantum linear system algorithm for dense matrices
• Hamiltonian Learning and Certification Using Quantum Resources
• Entanglement-Based Machine Learning on a Quantum Computer
• Optimal quantum learning of a unitary transformation
• Quantum Algorithm for Linear Regression
• Quantum machine learning for quantum anomaly detection
• Quantum Discriminant Analysis for Dimensionality Reduction and Classification
• A Separability-Entanglement Classifier via Machine Learning
• Quantum Hamiltonian Learning Using Imperfect Quantum Resources
• Quantum Recommendation Systems
• Quantum algorithm for association rules mining
• Quantum algorithm for association rules mining
• Quantum Data Compression of a Qubit Ensemble
• Quantum algorithm for visual tracking
• Optimizing Quantum Circuits for Arithmetic
• Strategy for quantum algorithm design assisted by machine learning
• Optimal compression for identically prepared qubit states
• Efficient Quantum Compression for Ensembles of Identically Prepared Mixed States
• Obtaining A Linear Combination of the Principal Components of a Matrix on Quantum Computers

Cited by in corpus (11)

• Quantum computing for finance
• Quantum K-nearest neighbor classification algorithm based on Hamming distance
• Improved quantum algorithm for A-optimal projection
• Quantum algorithms for anomaly detection using amplitude estimation
• Quantum Dimensionality Reduction by Linear Discriminant Analysis
• Quantum algorithm for Neighborhood Preserving Embedding
• Dementia Prediction Applying Variational Quantum Classifier
• Experimental implementation of quantum algorithm for association rules mining
• Quantum Algorithm for Unsupervised Anomaly Detection
• Quantum algorithms for SVD-based data representation and analysis
• Image Compression and Reconstruction Based on Quantum Network