In the age of big data, unsupervised machine learning plays crucial roles in detecting statistical patterns hidden in gigantic dataset. Taking root in statistical physics of random walks and heat diffusion on networks, Diffusion Maps are one of the most efficient modern classical unsupervised algorithms for clustering high-dimensional dataset. Not only it can automatically discover hidden statistical structure in a high-dimensional dataset, but it can also projects the data into a lower dimensional embedding where the majority of the data structure reside. Such projections are termed nonlinear dimensionality reduction or manifold learning in machine leaning literature. In the first part of this thesis, we begin by reviewing the physics of classical random walks on a graph which motivates the construction of Diffusion Maps. We will discuss how Diffusion Maps can perform clustering as well as nonlinear dimensionality reduction based on the properties of Markov transition matrix defined on a dataset-associated graph. We then showcase the usefulness of Diffusion Maps to learn low dimensional embedding in some real data samples. In the second part of this thesis, we bring diffusion maps into the realm of quantum algorithms. Motivated by advances in modern near-term quantum devices, we explore a construction of Quantum Diffusion Maps. By exploiting coherent state encoding scheme into Quantum RAM, we outline how to achieve both quantum computational speedup as well as quantum storage capacity reduction for quantum computations of Diffusion Maps on a quantum device. Lastly, it’s known that quantum walks can spread faster than its classical counterparts; we construct quantum walk protocols that perhaps can provide an alternative way to perform unsupervised data clustering, given that one can create quantum walks on quantum devices or quantum simulators.
In the age of big data, unsupervised machine learning plays crucial roles in detecting statistical patterns hidden in gigantic dataset. Taking root in statistical physics of random walks and heat diffusion on networks, Diffusion Maps are one of the most efficient modern classical unsupervised algorithms for clustering high-dimensional dataset. Not only it can automatically discover hidden statistical structure in a high-dimensional dataset, but it can also projects the data into a lower dimensional embedding where the majority of the data structure reside. Such projections are termed nonlinear dimensionality reduction or manifold learning in machine leaning literature. In the first part of this thesis, we begin by reviewing the physics of classical random walks on a graph which motivates the construction of Diffusion Maps. We will discuss how Diffusion Maps can perform clustering as well as nonlinear dimensionality reduction based on the properties of Markov transition matrix defined on a dataset-associated graph. We then showcase the usefulness of Diffusion Maps to learn low dimensional embedding in some real data samples. In the second part of this thesis, we bring diffusion maps into the realm of quantum algorithms. Motivated by advances in modern near-term quantum devices, we explore a construction of Quantum Diffusion Maps. By exploiting coherent state encoding scheme into Quantum RAM, we outline how to achieve both quantum computational speedup as well as quantum storage capacity reduction for quantum computations of Diffusion Maps on a quantum device. Lastly, it’s known that quantum walks can spread faster than its classical counterparts; we construct quantum walk protocols that perhaps can provide an alternative way to perform unsupervised data clustering, given that one can create quantum walks on quantum devices or quantum simulators.
Inspired by random walks on graphs, the diffusion map (DM) is a class of unsupervised machine learning that offers automatic identification of low-dimensional data structure hidden in a high-dimensional data set. In recent years, among its many applications, the DM has been successfully applied to discover relevant order parameters in many-body systems, enabling automatic classification of quantum phases of matter. However, a classical DM algorithm is computationally prohibitive for a large data set, and any reduction of the time complexity would be desirable. With a quantum computational speedup in mind, we propose a quantum algorithm for the DM, termed the quantum diffusion map (qDM). Our qDM takes as an input N classical data vectors, performs an eigendecomposition of the Markov transition matrix in time O(log3N), and classically constructs the diffusion map via the readout (tomography) of the eigenvectors, giving a total expected runtime proportional to N2polylogN. Finally, quantum subroutines in the qDM for constructing a Markov transition matrix and for analyzing its spectral properties can also be useful for other random-walk-based algorithms.
Dimensionality reduction is an unsupervised learning technique that uncovers the underlying low-dimensional structure in highdimensional data sets. Random walks on graphs for dimensionality reduction, such as diffusion maps (DM) and the Potential of Heat-diffusion for Affinity-based Trajectory Embedding (PHATE), have emerged as powerful tools for automatically identifying low-dimensional data. These methods have applications in various fields, including many-body physics and bioinformatics. However, the classical implementations of DM and PHATE suffer from a computational bottleneck caused by the eigendecomposition step, which has a cubic time complexity to the size of the data set, rendering them impractical for large data sets. Leveraging the quantum computational speedup, we propose a quantum analog of nonlinear dimensionality reduction, named the quantum diffusion map (qDM), which can significantly reduce the computational cost of constructing the Markov transition matrix. Specifically, our algorithm can construct the Markov transition matrix for N classical data vectors in O(log3 N) time and extract the eigenpairs of the transition matrix classically to construct the DM with an expected runtime of N2polylogN. Moreover, the quantum subroutines utilized in our algorithm have potential applications beyond dimensionality reduction, for example, in any random-walk-based problems requiring Markov transition matrix construction and spectral analysis.
Machine Learning (ML) is the process of training machines to analyze and learn from provided data. It can be categorized into three main types: supervised, unsupervised, and reinforcement learning. Unsupervised learning, a method that allows the discovery of underlying patterns in data without the need for additional information or labeled targets, uncovers hidden patterns within the given dataset but lacks associated labels or classes. Unsupervised techniques prove particularly useful for exploring data and comprehending complex behaviors that challenge human identification within large datasets. They find applications in various fields, such as text categorization (e.g., news articles), anomaly detection, satellite and spatial image processing, medical image analysis, customer segmentation, and recommendation engines. Unsupervised learning primarily serves three main tasks: clustering, association, and dimensionality reduction. Clustering is a technique that automatically groups similar samples together based on their inherent characteristics. Association is a technique used to discover relationships between different features within a dataset. Dimensionality reduction is a technique employed to decrease the number of features in a dataset, especially when dealing with high-dimensional data.
In this thesis, we investigate whether quantum algorithms can be used in the field of machine learning for both long and near term quantum computers. We will first recall the fundamentals of machine learning and quantum computing and then describe more precisely how to link them through linear algebra: we introduce quantum algorithms to efficiently solve tasks such as matrix product or distance estimation. These results are then used to develop new quantum algorithms for unsupervised machine learning, such as k-means and spectral clustering. This allows us to define many fundamental procedures, in particular in vector and graph analysis. We will also present new quantum algorithms for neural networks, or deep learning. For this, we introduce an algorithm to perform a quantum convolution product on images, as well as a new way to perform a fast tomography on quantum states. We prove that these quantum algorithms are faster versions of equivalent classical algorithms, but exhibit random effects due to the quantum nature of the computation. Many simulations have been carried out to study these effects and measure their learning accuracy on real data. Finally, we will present a quantum orthogonal neural network circuit adapted to the currently available small and imperfect quantum computers. This allows us to perform real experiments to test our theory.
Experimental quantum simulators have become large and complex enough that discovering new physics from the huge amount of measurement data can be quite challenging, especially when little theoretical understanding of the simulated model is available. Unsupervised machine learning methods are particularly promising in overcoming this challenge. For the specific task of learning quantum phase transitions, unsupervised machine learning methods have primarily been developed for phase transitions characterized by simple order parameters, typically linear in the measured observables. However, such methods often fail for more complicated phase transitions, such as those involving incommensurate phases, valence-bond solids, topological order, and many-body localization. We show that the diffusion map method, which performs nonlinear dimensionality reduction and spectral clustering of the measurement data, has significant potential for learning such complex phase transitions unsupervised. This method may work for measurements of local observables in a single basis and is thus readily applicable to many experimental quantum simulators as a versatile tool for learning various quantum phases and phase transitions.
This thesis presents original contributions at the intersection of quantum computing and machine learning, investigating how these two fields can benefit from each other. The first part of the thesis presents two applications of machine learning techniques in quantum computing. The first contribution involves the use of artificial neural networks for the decoding of quantum error correction codes, resulting in faster decoding times while maintaining a high level of accuracy. The originality of this work lies in the application of explainable machine learning techniques to both improve the decoding performance and to provide insights into the decoding process. The second contribution introduces a novel technique based on reinforcement learning to characterize and simulate the noise affecting a quantum chip. This technique reduces the heuristic assumption on the noise model, making it more adaptable to the specific noise characteristics of the quantum device. In the second part of the thesis, we demonstrate, with two examples, how it is possible to implement machine learning algorithms on quantum devices by replacing artificial neural networks with parametrized quantum circuits. The first contribution in this section introduces a quantum anomaly detection algorithm, applied to the field of high-energy physics. This algorithm allows for the identification of anomalous patterns in quantum data, maintaining a level of accuracy comparable to classical algorithms. The novelty of this work lies in the first use of quantum circuits for the task of anomaly detection in a muon drift chamber trigger system, with possible future applications to quantum detector systems in high-energy physics experiments. The second contribution presents the quantum version of a generative diffusion model, able to sample quantum states from a well-defined distribution. This first implementation of a quantum diffusion model is not meant to outperform classical models, but rather to show potential advantages and limitations of these kinds of algorithms. The aim of the thesis is to show how quantum computing can benefit from machine learning, and how machine learning can be implemented on quantum devices, setting the stage for future advancements in both fields.