Quantum Least Squares Support Vector Machines

Quantum machine learning is a novel discipline that puts together concepts of machine learning and quantum computing to create algorithms that are faster and with improved performances with respect to their classical counterparts. Our focus for this project is on a specific algorithm called Quantum Least Squares Support Vector Machines (QLS-SVM). The algorithm's most complex task involves solving a linear system of equations, which can be efficiently achieved through quantum computing. In previous works, we can find a modest number of implementations of this quantum algorithm. All of these implementations use the HHL algorithm to solve the linear system of equations, achieving exponential speedup compared to the classical algorithm. In this work, we present an implementation of quantum least squares support vector machines using the block-encoding framework to construct the linear system and QSVT for performing linear algebra operations. Additionally, we demonstrate an enhancement in the classification routine, reducing the error dependency on the final complexity. We conduct experiments using both artificial and real datasets to showcase the accuracy of our algorithm and to compare its complexity with the previous implementations. Furthermore, we illustrate how we can further enhance the algorithm's performance in the low-rank case without compromising accuracy.

Il machine learning quantistico è una nuova disciplina che mette insieme concetti di machine learning e calcolo quantistico in modo tale da creare algoritmi con tempi di esecuzione più vantaggiosi rispetto ai corrispettivi classici. In questo lavoro ci concentreremo su uno specifico algoritmo chiamato Quantum Least Squares Support Vector Machines (QLS-SVM). La procedura più complessa dell'algoritmo consiste nella risoluzione di un sistema lineare di equazioni, che può essere risolto in modo efficiente attraverso il calcolo quantistico. In lavori precedenti al nostro possiamo trovare alcune implementazioni di questo algoritmo quantistico. Tutte queste implementazioni utilizzano l'algoritmo HHL per risolvere il sistema lineare di equazioni, ottenendo un incremento esponenziale rispetto all'algoritmo classico. In questo lavoro, descriviamo una possibile implementazione di quantum least squares support vector machines utilizzando il framework di block-encoding per costruire il sistema lineare e QSVT per eseguire operazioni di algebra lineare. Inoltre, dimostriamo che è possibile migliorare la procedura di classificazione, riducendo la dipendenza dell'errore dalla complessità finale. Effettuiamo esperimenti utilizzando dataset sia artificiali che reali per mostrare l'accuratezza del nostro algoritmo e confrontarne la complessità con le implementazioni precedenti. Infine, illustriamo come possiamo ulteriormente migliorare le prestazioni dell'algoritmo, senza comprometterne l'accuratezza, nel caso low-rank.