Algoritmi quantistici per operazioni di algebra lineare

Questa tesi descrive e analizza un algoritmo quantistico che permette di invertire matrici in modo efficiente. Il problema si scompone in più passaggi che riguardano la preparazione e l’estrazione dei dati e l’elaborazione vera e propria. Ci occupiamo inizialmente della preparazione della matrice, che consiste nella codifica di quest’ultima come blocco di una matrice unitaria. Mostreremo che questa codifica, detta block encoding, permette di eseguire operazioni aritmetiche tra matrici, ossia combinazioni lineari e moltiplicazioni. Il procedimento per invertire una matrice data fa parte di una classe più ampia di algoritmi. Tratteremo dell’algoritmo quantistico di trasformazione dei valori singolari, che, data una matrice codificata, permette di applicare un polinomio ai suoi valori singolari. Successivamente mostreremo che approssimando la funzione 1/x tramite polinomi, è possibile applicare l’algoritmo all’inversione matriciale. Infine, analizziamo la complessità dell’algoritmo e discutiamo di possibili applicazioni nel campo del machine learning quantistico.