Quantum singular value estimation techniques for data representation

Quantum computing is a recent computing paradigm that promises substantial speed-ups in several computational tasks that are impractical with classical computers. In this work, we focus on extending the recent technique of Quantum Singular Value Estimation (QSVE) to provide quantum procedures that speed-up the computation of data representation models for machine learning. Firstly, we show how the problems of performing Principal Component Analysis (PCA), Correspondence Analysis (CA), and Latent Semantic Analysis (LSA) are closely related to computing the Singular Value Decomposition (SVD) of matrices obtained from the dataset. Then, we present a series of novel quantum algorithms that allow us to estimate the singular values and singular vectors in time that is sub-linear in the number of elements of the matrices. For each of the quantum algorithms, the computational cost is proven. Furthermore, we discuss how these procedures can be used to extract the representation models for PCA, CA, and LSA. In each of these three cases, we analyze the parameters of the run-time and prove the error bounds on the accuracy of each representation model. Finally, we simulate some of the quantum algorithms on the MNIST dataset, in order to show that the run-time parameters that do not depend on the matrix dimensions are often negligible and that the error bound on the computed model is reasonable and allows for competitive classification performances.

Il quantum computing è un recente paradigma computazionale che promette di accelerare notevolmente la risoluzione di diversi problemi per i quali i computer classici risultano inefficienti. In questo lavoro, intendiamo sviluppare ulteriormente i recenti studi di Quantum Singular Value Estimation (QSVE) per fornire procedure quantistiche che accelerino il calcolo di modelli di rappresentazione dei dati per machine learning. In primo luogo, mostriamo come la computazione dei modelli di Principal Component Analysis (PCA), Correnspondence Analysis (CA) e Latent Semanic Analysis (LSA) sia strettamente collegata al calcolo della Singular Value Decomposition (SVD) di matrici ottenute pre-processando i dataset in input. In seguito, presentiamo una serie di nuovi algoritmi quantistici che consentono di stimare i singular value ed i singular vector di una matrice in tempo sub-lineare nel numero dei suoi elementi. Per ciascuno degli algoritmi proposti, dimostriamo il costo computazionale ed indaghiamo come queste procedure possano essere utilizzate per estrarre i modelli di rappresentazione per PCA, CA ed LSA. Per ciascuno di questi tre casi, analizziamo i parametri del tempo di esecuzione e forniamo dei limiti teorici sulle approssimazioni dei modelli calcolati. Infine, simuliamo alcuni degli algoritmi quantistici sul dataset MNIST per mostrare come i parametri del run-time che non dipendono dalle dimensioni dell’input siano spesso trascurabili. Gli esperimenti dimostrano che i limiti teorici sull’errore del modello approssimato sono contenuti e consentono prestazioni di classificazione competitive.