Quantum matching pursuit algorithms

Quantum machine learning is an emerging discipline that combines the benefits of quantum computing with machine learning techniques. Indeed, quantum computing speeds up the computation of several tasks with respect to what the current classical computing techniques achieve. In this work, we provide an analysis of three novel quantum algorithms. The first two algorithms are related to the sparse representation theory and are based respectively on Matching Pursuit and Orthogonal Matching Pursuit. These algorithms solve a linear system minimizing greedily the $l_0$-norm of the solution. Instead, the third one is a nearest neighbor classification algorithm that exploits the reduction of dimensionality to achieve better performance. The use of quantum procedures introduces some approximation error in the computation of several intermediate steps. For each of these algorithms, we provide a detailed description of their procedure, their running time, their probability of failure, and what requirements must be met to ensure a specific error in the final results. The runtimes of these algorithms are lower than their classical equivalents. In addition to that, we study, through the use of numerical experiments, how the outputs of the algorithms are affected by the errors in the intermediate results. In this analysis, we use both artificially generated datasets and real cybersecurity-related datasets.

Il machine learning quantistico è una disciplina emergente che combina i benefici del calcolo quantistico con tecniche di machine learning. Infatti, il calcolo quantistico accellera la computazione di diverse operazioni rispetto alla complessità delle attuali tecniche classiche. In questo lavoro, presentiamo tre nuovi algoritmi quantistici. I primi due algoritmi sono relativi alla teoria delle rappresentazioni sparse e sono basati su Matching Pursuit e Orthogonal Matching Pursuit. Questi algoritmi risolvono un sistema lineare minimizzando in maniera avida la norma $l_0$ della soluzione. Il terzo algoritmo, invece, è un algoritmo di classificazione nearest neighbour che sfrutta la riduzione della dimensionalità per ottenere prestazioni migliori. L'uso di procedure quantistiche introduce errore di approssimazione nel calcolo di alcuni step intermedi. Per ognuno di questi algoritmi, forniamo una spiegazione dettagliata del loro funzionamento, del loro tempo di esecuzione, della loro probabilità di successo e quali requisiti devono essere soddisfatti per ottenere uno specifico errore di approssimazione nei risultati finali. Il tempo di esecuzione di questi algoritmi è inferiore rispetto ai loro equivalenti classici. In aggiunta a ciò, analizziamo, tramite l'uso di esperimenti numerici, come i risultati degli algoritmi sono influenzati dall'errore nei risultati intermedi. Per questa analisi usiamo sia dati generati artificialmente che dati reali relativi alla sicurezza informatica.