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 theoreti- cal 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.

Quantum algorithms for SVD-based data representation and analysis

Bellante, Armando;Luongo, Alessandro;Zanero, Stefano
2022-01-01

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 theoreti- cal 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.
2022
Quantum computing; Machine learning; Data analysis; Data representations; Singular value decomposition; Principal component analysis; Correspondence analysis; Latent semantic analysis
File in questo prodotto:
File Dimensione Formato  
Bellante2022_Article_QuantumAlgorithmsForSVD-basedD.pdf

accesso aperto

: Publisher’s version
Dimensione 5.17 MB
Formato Adobe PDF
5.17 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1219302
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact