Quantum algorithms for sparse recovery and machine learning

Quantum computing is a novel computational paradigm that promises substantial speed-ups in a plethora of tasks that are computationally challenging for classical computers. Simultaneously, machine learning has experienced remarkable advancements in recent years, driven by breakthroughs in deep learning, increased computational power, and the availability of vast datasets. These advancements have significantly improved tasks such as image recognition, natural language processing, and autonomous systems. In this PhD thesis, we explore faster quantum algorithms for learning problems and new classical algorithms for graph embeddings. This thesis is structured into three parts, with the main interleaving threads being quantum computation in the circuit model, machine learning and data analysis, and sparsity. Part one discusses what quantum computers can do for sparse recovery problems, where the aim is to reconstruct a target vector using the sparsest combination of basis vectors from an overcomplete dictionary. First, we present quantum versions of the matching pursuit and orthogonal matching pursuit algorithms that achieve a polynomial speed-up over their classical counterparts under the assumption of an efficient classical-writable quantum-readable memory. Then, we define the novel problem of quantum sparse recovery - which consists of recovering the sparsest support of a target quantum state over an overcomplete set of other quantum states - and give conditions for which our quantum orthogonal matching pursuit algorithm efficiently recovers the optimal solution, without the need for a quantum memory. Part two focuses on quantum algorithms for machine learning and data analysis, intending to speed up the training and classification steps of learning algorithms. Under the assumption of an efficient quantum memory, the thesis explores singular value decomposition-based problems and develops quantum algorithms to efficiently retrieve top singular values and vectors of matrices with good low-rank approximations, with applications in machine learning methods such as principal component analysis, correspondence analysis, and latent semantic analysis. Furthermore, it presents an efficient quantum classification algorithm based on a nearest neighbor/centroid algorithm and a norm-based outlier detection procedure, inspired by the seminal eigenfaces approach for face recognition. Lastly, the practical potential of these fault-tolerant quantum algorithms is evaluated through numerical experiments and the discussion of an evaluation framework that can guide computer scientists and engineers toward assessing the potential of fault-tolerant quantum machine learning algorithms on real-world datasets and problems. The third and last part of the thesis studies permutation-invariant graph embeddings, particularly the skew spectrum of graphs. The skew spectrum provides a time-efficient invariant embedding based on group theory and harmonic analysis of the symmetric group. On the road to developing a quantum group theoretic graph embedding, we stop and generalize this classical algorithm in two ways. First, we study a multi-orbit version of the skew spectrum algorithm, improving its completeness (the ability to map non-isomorphic graphs to different vectors) for more complex graph structures like multigraphs or graphs with node/edge attributes. Then, we extend the computation of the multi-orbit skew spectrum to the efficient computation of the spectrum of higher correlation functions, allowing a trade-off between computational efficiency and completeness. The efficient computation of the spectra is achieved through efficient Fourier transforms on the symmetric group that leverages a form of sparsity of the functions representing graphs, which are always constant over a large portion of the domain. We implemented and tested the three graphs invariant to show experimental evidence of the increased completeness. In summary, this thesis contributes to advancing the field of quantum algorithms for sparse recovery and machine learning and developing strongly mathematically supported permutation-invariant graph embeddings.

Il calcolo quantistico rappresenta un paradigma computazionale innovativo, promettendo significativi vantaggi nella risoluzione di problemi computazionalmente complessi, spesso proibitivi per i computer classici. Parallelamente, il machine learning ha recentemente fatto grandi progressi, grazie agli sviluppi nel deep learning, alla crescente disponibilità di potenza computazionale e all’accesso a vasti dataset. Questi progressi hanno permesso la risoluzione automatizzata di problemi in settori quali il riconoscimento delle immagini, l'elaborazione del linguaggio naturale e i sistemi autonomi. In questa tesi di dottorato, esploriamo algoritmi quantistici in grado di accelerare la risoluzione di problemi di machine learning e sviluppiamo nuovi algoritmi classici per la rappresentazione di grafi. La tesi si articola in tre parti principali, accomunate dai temi della computazione quantistica nel modello a circuito, del machine learning e del concetto di sparsità. La prima parte esamina il contributo che i computer quantistici potrebbero apportare alla soluzione di problemi di sparse recovery. In questi problemi, l’obiettivo è ricostruire un vettore target utilizzando la combinazione più sparsa possibile di vettori appartenenti a una base ridondante (non ortonormale, più che completa). Inizialmente, presentiamo le prime versioni quantistiche degli algoritmi di "matching pursuit" e "orthogonal matching pursuit", dimostrando un'accelerazione polinomiale rispetto alle loro controparti classiche, a condizione di disporre di una memoria capace di gestire dati classici in superposizione su un computer quantistico. Successivamente, introduciamo il quantum sparse recovery, ovvero un nuovo problema il cui l’obbiettivo è trovare il supporto più sparso di uno stato quantistico target su un insieme ridondante di stati quantistici; inoltre, dimostriamo dei regimi entro i quali il nostro algoritmo “quantum orthogonal matching pursuit" può calcolare efficientemente la soluzione ottimale a questo problema, senza necessitare di una memoria quantistica. La seconda parte esplora algoritmi quantistici per il machine learning e l'analisi dei dati, con l'obiettivo di accelerare i processi di addestramento e classificazione. Assumendo l'esistenza di una memoria quantistica efficiente, esaminiamo problemi basati sulla decomposizione ai valori singolari e sviluppiamo algoritmi quantistici per approssimare rapidamente i principali valori e vettori singolari di matrici a basso rango. Questi algoritmi trovano applicazione in tecniche di machine learning, tra cui l’analisi delle componenti principali (PCA), l’analisi delle corrispondenze (CA) e l’analisi semantica latente (LSA). Inoltre, presentiamo un algoritmo quantistico di classificazione basato su nearest neighbor/centroid e su una procedura di rilevamento di outlier ispirata agli "eigenfaces" per il riconoscimento facciale. Il potenziale pratico di questi algoritmi viene valutato mediante esperimenti numerici. Infine, forniamo una metodologia che possa guidare ingegneri ed informatici nella valutazione dell’impatto pratico degli algoritmi di machine learning quantistico su problemi e dataset reali. La terza ed ultima parte della tesi analizza tecniche di rappresentazione di grafi, con particolare attenzione ad un algoritmo chiamato “skew spectrum of graphs”. Questo algoritmo fornisce una rappresentazione vettoriale, invariante a permutazioni dei nodi, efficiente da calcolare e basata sulla teoria dei gruppi e sull’analisi armonica di funzioni definite sul gruppo simmetrico. Andando verso lo sviluppo di uno skew spectrum quantistico, abbiamo esteso questo algoritmo classico in due direzioni. In primo momento, attraverso l’elaborazione di una versione multi-orbit dello skew spectrum, ne abbiamo migliorato la completezza (intesa come capacità di mappare grafi non isomorfi su vettori distinti) nella rappresentazione di strutture dati più complesse, come multigrafi o grafi con attributi su nodi ed archi. Successivamente, abbiamo esteso la computazione del multi-orbit skew spectrum al calcolo di correlazioni di ordine superiore al terzo, consentendo un trade-off tra efficienza computazionale e completezza della rappresentazione. L’efficienza computazionale di questo algoritmo classico viene raggiunta grazie all’uso di trasformate di Fourier efficienti che sfruttano proprietà di sparsità delle funzioni rappresentanti i grafi. Abbiamo testato sperimentalmente lo skew spectrum e le due estensioni dimostrando con esempi pratici come le nuove rappresentazioni abbiano una maggiore completezza. In sintesi, questa tesi contribuisce allo sviluppo di nuovi algoritmi quantistici per sparse recovery e machine learning, e propone nuove rappresentazioni di grafi invarianti alle permutazioni, supportate da solide basi matematiche.