Quantum machine learning promises to efficiently solve important problems. There are two persistent challenges in classical machine learning: the lack of labeled data, and the limit of computational power. We propose a novel framework that resolves both issues: quantum semi-supervised learning. Moreover, we provide a protocol in systematically designing quantum machine learning algorithms with quantum supremacy, which can be extended beyond quantum semi-supervised learning. In the meantime, we show that naive quantum matrix product estimation algorithm outperforms the best known classical matrix multiplication algorithm. We showcase two concrete quantum semi-supervised learning algorithms: a quantum self-training algorithm named the propagating nearest-neighbor classifier, and the quantum semi-supervised K-means clustering algorithm. By doing time complexity analysis, we conclude that they indeed possess quantum supremacy.
Quantum machine learning promises to efficiently solve important problems. There are two persistent challenges in classical machine learning: the lack of labeled data, and the limit of computational power. We propose a novel framework that resolves both issues: quantum semi-supervised learning. Moreover, we provide a protocol in systematically designing quantum machine learning algorithms with quantum supremacy, which can be extended beyond quantum semi-supervised learning. In the meantime, we show that naive quantum matrix product estimation algorithm outperforms the best known classical matrix multiplication algorithm. We showcase two concrete quantum semi-supervised learning algorithms: a quantum self-training algorithm named the propagating nearest-neighbor classifier, and the quantum semi-supervised K-means clustering algorithm. By doing time complexity analysis, we conclude that they indeed possess quantum supremacy.
Quantum machine learning (QML) provides a transformative approach to data analysis by integrating the principles of quantum computing with classical machine learning methods. With the exponential growth of data and the increasing complexity of computational tasks, quantum algorithms offer tremendous advantages in terms of processing speed, memory efficiency, and the ability to resolve issues intractable for classical systems. In this work, the use of QML techniques for both supervised and unsupervised learning problems is explored. Quantum-enhanced models such Quantum Support Vector Machines (QSVMs) and Quantum Neural Networks (QNNs) show outstanding performance in classification and regression tasks by using quantum kernels and entanglement in supervised learning. Moreover, hybrid quantum-classical solutions offer useful implementations on noisy intermediate-scale quantum (NISQ) devices, hence bridging the gap between present quantum technology and practical uses. By means of comparative analysis, this paper emphasizes the possible benefits and drawbacks of QML, thereby providing understanding of its future importance in sectors including material science, finance, and healthcare. In the end, QML opens the path for a new era of intelligent data processing and solves until unthinkable difficult challenges.
In this dissertation, we study the intersection of quantum computing and supervised machine learning algorithms, which means that we investigate quantum algorithms for supervised machine learning that operate on classical data. This area of research falls under the umbrella of quantum machine learning, a research area of computer science which has recently received wide attention. In particular, we investigate to what extent quantum computers can be used to accelerate supervised machine learning algorithms. The aim of this is to develop a clear understanding of the promises and limitations of the current state of the art of quantum algorithms for supervised machine learning, but also to define directions for future research in this exciting field. We start by looking at supervised quantum machine learning (QML) algorithms through the lens of statistical learning theory. In this framework, we derive novel bounds on the computational complexities of a large set of supervised QML algorithms under the requirement of optimal learning rates. Next, we give a new bound for Hamiltonian simulation of dense Hamiltonians, a major subroutine of most known supervised QML algorithms, and then derive a classical algorithm with nearly the same complexity. We then draw the parallels to recent "quantum-inspired" results, and will explain the implications of these results for quantum machine learning applications. Looking for areas which might bear larger advantages for QML algorithms, we finally propose a novel algorithm for Quantum Boltzmann machines, and argue that quantum algorithms for quantum data are one of the most promising applications for QML with potentially exponential advantage over classical approaches.
Recent advances in quantum technology have led to the development and the manufacturing of programmable quantum annealers that promise to solve certain combinatorial optimization problems faster than their classical counterparts. Semi-supervised learning is a machine learning technique that makes use of both labeled and unlabeled data for training, which enables a good classifier with only a small amount of labeled data. In this paper, we propose and theoretically analyze a graph-based semi-supervised learning method with the aid of the quantum annealing technique, which efficiently utilizes the quantum resources while maintaining good accuracy. We illustrate two classification examples, suggesting the feasibility of this method even with a small portion (30%) of labeled data involved.
Quantum computing is an interdisciplinary field at the intersection of computer science, mathematics, and physics that studies information processing tasks on a quantum computer. A quantum computer is a device whose operations are governed by the laws of quantum mechanics. As building quantum computers is nearing the era of commercialization and quantum supremacy, it is essential to think of potential applications that we might benefit from. Among many applications of quantum computation, one of the emerging fields is quantum machine learning. We focus on predictive models for binary classification and variants of Support Vector Machines that we expect to be especially important when training data becomes so large that a quantum algorithm with a guaranteed speedup becomes useful. We present a quantum machine learning algorithm for training Sparse Support Vector Machine for problems with large datasets that require a sparse solution. We also present the first quantum semi-supervised algorithm, where we still have a large dataset, but only a small fraction is provided with labels. While the availability of data for training machine learning models is steadily increasing, oftentimes it is much easier to collect feature vectors to obtain the corresponding labels. Here, we present a quantum machine learning algorithm for training Semi-Supervised Kernel Support Vector Machines. The algorithm uses recent advances in quantum sample-based Hamiltonian simulation to extend the existing Quantum LS-SVM algorithm to handle the semi-supervised term in the loss while maintaining the same quantum speedup as the Quantum LS-SVM.
The rapid advancement of quantum computing hardware and software has ushered in a new era for computational science, promising to tackle problems that are intractable for classical computers. Parallelly, machine learning (ML) has revolutionized data analysis and artificial intelligence. The confluence of these two fields, known as Quantum Machine Learning (QML), aims to harness the principles of quantum mechanics-such as superposition, entanglement, and interference-to enhance and redefine classical machine learning algorithms. This survey provides a comprehensive overview of the burgeoning field of QML. We begin by elucidating the fundamental quantum concepts that underpin QML approaches. We then present a detailed taxonomy and analysis of prominent QML algorithms, categorizing them into quantum-enhanced classical models and fully quantum models. Key families of algorithms discussed include Quantum Support Vector Machines (QSVM), Quantum Neural Networks (QNNs), and Quantum Generative Adversarial Networks (QGANs). For each, we explain the theoretical quantum advantage, the circuit implementation, and the current limitations. Furthermore, we delve into the critical challenges facing the practical realization of QML, including the pervasive issue of noise in Noisy Intermediate-Scale Quantum (NISQ) devices, the problem of barren plateaus in training quantum circuits, and the complexities of efficient data encoding (quantum feature maps). We also present a small-scale experimental simulation of a variational quantum classifier on a standardized dataset, demonstrating its principle and comparing its performance with a classical counterpart. Finally, the paper discusses the future trajectory of QML, highlighting the importance of error mitigation, hybrid quantum-classical architectures, and the development of quantum-specific learning inductive biases. We conclude that while fault-tolerant quantum computers remain on the horizon, QML represents a paradigm shift with the potential to deliver profound computational advantages in the coming decades.
Over the past several decades, computing has undergone revolutionary changes, moving beyond classical systems that manipulate ones and zeroes to solve complex problems. One key area where quantum computing power is particularly promising is machine learning. While conventional machine learning algorithms have successfully addressed a diverse set of challenges, they are often computationally intensive and slow, while working on today's massive datasets. Quantum machine learning aims to solve these challenges by enhancing classical methods with quantum algorithms, offering faster processing and more efficient data analysis. In recent years, research has focused on applying quantum techniques to classic machine learning tasks. This paper reviews key contributions from researchers in quantum machine learning and explores its potential to revolutionize real-world problem-solving by integrating both traditional and quantum methods.