Alessandro Luongo - Quantum algorithms for supervised and unsupervised machine learning

I'll present the main tools used in quantum machine learning: procedures to perform quantum linear algebraic operations, the QRAM circuit as an access model on the data, and routines to calculate distances - which we refined. Among the results of our group, I'll present three new algorithms. The first, QSFA is a dimensionality reduction algorithm that maps the dataset in a lower dimensional space, where classification can be performed with higher accuracy. Dimensionality reduction is often a necessary while performing classification in high dimensional spaces due to the curse of dimensionality. The second is QFD, a supervised classifier which assign a new point to the cluster with minimum average square distance between the vector and the points of the cluster. The third is q-means: the quantum version of k-means. Being an iterative algorithm for clustering, q-means has convergence and precision guarantees similar to the classical variants of $k$-means. All the algorithms presented here are poly-logarithmic in the number of vectors in the dataset, thus with an exponential separation with respect to classical algorithms.