Density modeling is a machine learning task with the goal of learning an underlying probability distribution from samples. Here the authors show that, when solving certain density modeling problems, algorithms that use fault-tolerant quantum computers have an advantage over classical ones.
Density modelling is the task of learning an unknown probability density function from samples, and is one of the central problems of unsupervised machine learning. In this work, we show that there exists a density modelling problem for which fault-tolerant quantum computers can offer a super-polynomial advantage over classical learning algorithms, given standard cryptographic assumptions. Along the way, we provide a variety of additional results and insights, of potential interest for proving future distribution learning separations between quantum and classical learning algorithms. Specifically, we (a) provide an overview of the relationships between hardness results in supervised learning and distribution learning, and (b) show that any weak pseudo-random function can be used to construct a classically hard density modelling problem. The latter result opens up the possibility of proving quantum-classical separations for density modelling based on weaker assumptions than those necessary for pseudo-random functions.
Machine learning models are used for pattern recognition analysis of big data, without direct human intervention. The task of unsupervised learning is to find the probability distribution that would best describe the available data, and then use it to make predictions for observables of interest. Classical models generally fit the data to Boltzmann distribution of Hamiltonians with a large number of tunable parameters. Quantum extensions of these models replace classical probability distributions with quantum density matrices. An advantage can be obtained only when features of density matrices that are absent in classical probability distributions are exploited. Such situations depend on the input data as well as the targeted observables. Explicit examples are discussed that bring out the constraints limiting possible quantum advantage. The problem-dependent extent of quantum advantage has implications for both data analysis and sensing applications.
All the data stored and processed by our computers is encoded as sequences of zeros and ones, called bits. Quantum computers offer an alternative to this traditional way of encoding and manipulating information. The information in a collection of qubits can be a combination, also called a superposition, over many possible sequences of zeros and ones. Where classical computation consists of flipping zeros and ones, quantum computation consists of manipulating high-dimensional vectors called quantum states. Researchers have found ways to use this to engineer quantum algorithms that solve some tasks much faster than any classical computer would. These are called quantum advantages, and are proven for specific tasks, such as breaking some encryption schemes and solving certain large linear systems. The goal of this thesis was to find new tasks for which quantum computers provably have an advantage over classical computers. In this thesis, I present two such advantages and associated results. The first one revolves around a physically relevant learning task. In other words, I explore how quantum computers can be used to help solve specialized machine learning tasks. The second one addresses the simulation of classical systems. One of the first high-potential and natural uses of quantum computers was the simulation of quantum systems. A lot of real-world problems, however, are ruled by classical physics. It turns out that quantum computers are well suited for the simulation of some exponentially large classical systems. In this thesis, I add a new problem to this list.
Density estimation is a central task in statistics and machine learning. This problem aims to determine the underlying probability density function that best aligns with an observed dataset. Some of its applications include statistical inference, unsupervised learning, and anomaly detection. Despite its relevance, few works have explored the application of quantum computing to density estimation. In this article, we present a quantum-classical density-matrix density estimation model, called Q-DEMDE, based on the expected values of density matrices and a quantum embedding called quantum Fourier features. The method uses quantum hardware to build probability distributions of training data via mixed quantum states. As a core subroutine, we propose an algorithm to estimate the expected value of a mixed density matrix from its spectral decomposition on a quantum computer. In addition, we present an application of the method for quantum-classical anomaly detection. We evaluated the density estimation model with quantum random and quantum adaptive Fourier features on different datasets on a quantum simulator and a real quantum computer. An important result of this work is to show that it is possible to perform density estimation and anomaly detection with high performance on present-day quantum computers.
Quantum Machine Learning (QML) integrates quantum algorithms into machine learning programs to enhance and expedite classical machine learning techniques. It leverages quantum data and hybrid quantum-classical models, utilizing the principles of superposition and entanglement to handle complex joint probability distributions that would require exponential classical computational resources. QML aims to harness the unique properties of quantum computers for practical machine learning tasks, with the goal of achieving quantum advantage over classical approaches. QML finds applications in diverse fields such as chemical and quantum matter simulation, quantum control, quantum communication networks, and quantum metrology. Quantum algorithms can analyze quantum states and improve computational speed and data storage. Two main frameworks, quantum kernel methods and variational quantum algorithms, are widely used due to their implement ability on quantum hardware and capacity to work on general datasets. Quantum computers can solve linear algebraic problems, calculate eigenvectors and eigenvalues, and perform support vector algorithms at exponentially faster rates than classical computers. Despite its potential, QML faces significant challenges related to quantum hardware capabilities, including limited qubit connectivity, noise, coherence times, and errors in state preparation and measurement. Hardware constraints, compatibility issues, high computational and memory requirements, and the difficulty of quantum programming also pose obstacles. Overcoming these hardware and software limitations is crucial for realizing the full potential of quantum machine learning
The use of quantum computing for machine learning is among the most exciting prospective applications of quantum technologies. However, machine learning tasks where data is provided can be considerably different than commonly studied computational tasks. In this work, we show that some problems that are classically hard to compute can be easily predicted by classical machines learning from data. Using rigorous prediction error bounds as a foundation, we develop a methodology for assessing potential quantum advantage in learning tasks. The bounds are tight asymptotically and empirically predictive for a wide range of learning models. These constructions explain numerical results showing that with the help of data, classical machine learning models can be competitive with quantum models even if they are tailored to quantum problems. We then propose a projected quantum model that provides a simple and rigorous quantum speed-up for a learning problem in the fault-tolerant regime. For near-term implementations, we demonstrate a significant prediction advantage over some classical models on engineered data sets designed to demonstrate a maximal quantum advantage in one of the largest numerical tests for gate-based quantum machine learning to date, up to 30 qubits.