This chapter examines quantum linear algebra as a foundational framework for quantum machine learning. Because many core learning tasks, including regression, dimensionality reduction, kernel evaluation, recommendation systems, and representation learning, depend on linear algebraic operations, this chapter explores how these operations can be reformulated in the quantum setting. Emphasis is placed on the shift from explicit numerical computation to coherent manipulation of quantum states and measurement-based access to information. This chapter introduces quantum inner product estimation as a primitive for similarity and kernel evaluation, highlighting the swap test and related overlap-estimation methods. It then develops quantum matrix inversion and the HHL algorithm, emphasizing the preparation of solution states rather than explicit solution vectors and discussing the importance of conditioning and regularization. Quantum singular value decomposition is presented through Hermitian embeddings, phase estimation, block encoding, and quantum singular value transformation, providing a unified framework for spectral filtering and low-rank approximation. This chapter concludes with quantum principal component analysis, in which covariance structure is represented by a density matrix and accessed through quantum phase estimation and density matrix exponentiation. Throughout, practical demonstrations in Qiskit and PennyLane illustrate the algorithms, while careful attention is given to the limitations imposed by state preparation, measurement, noise, and classical data loading.
Quantum computing is certainly one of the greatest advances in the computer science field. Thanks to the parallelism and entanglement properties, it has proved to offer several advantages compared to the classical algorithms especially in the great reduction of the processing time. Quantum phase estimation (QPE) is one of the most important algorithms for quantum computing. It is known as the eigenvalue finding module for unitary operators. The Fourier transform is the key to this procedure. It has been researched and used to solve many problems such as the order finding problem, and the factoring problem. It was also applied for quantum sampling algorithms and the calculation of the eigenvalues of unitary matrices. In this paper, we study three important quantum algorithms for machine learning that use the QPE algorithm as a subroutine: the quantum principal components analysis (PCA) for data visualization, the Harrow-Hassidim-Lloyd (HHL) algorithm for solving linear systems, and the quantum singular value thresholding (SVT) for matrix completion in recommender systems. We also discuss the advantages and limits of such algorithms compared to their classical versions. Then we discuss potential ways of amelioration of such algorithms, and end with a proposed approach for further improvement.
This chapter reviews the principal concepts and computational structures of classical machine learning that provide the foundation for quantum machine learning (QML). It examines linear models, support vector machines, principal component analysis, neural networks, probabilistic learning, generative modeling, and optimization, with emphasis on the linear algebraic, statistical, and variational principles that reappear in quantum algorithms. Particular attention is given to computational bottlenecks such as matrix inversion, eigenvalue decomposition, kernel evaluation, sampling, and high-dimensional optimization since these are among the areas where quantum methods may offer advantages under suitable assumptions. This chapter also discusses classes of learning problems that are most plausibly positioned to benefit from quantum speedups and highlights the importance of data access models, encoding assumptions, and realistic complexity analysis in assessing the promise of QML.
In this chapter and the next one, we will explore the exciting areas of quantum machine learning and quantum deep learning. Machine learning and deep learning have seen great success in recent years because of the increase in the computational power at our disposal and because of the high-end research in these fields. Quantum machine learning presents an exciting opportunity to increase the computational efficiency of the existing machine learning algorithms as well as presents a way to tackle some of the more computationally intractable problems. In this chapter, we start with the Harrow-Hassidim-Lloyd algorithm, popularly known as HHL, which acts as the matrix inversion routine in the quantum computing domain. Hence, HHL will be the default choice for algorithms such as linear regression and least square support vector machines. Subsequently, we touch upon quantum linear regression and support vector machines in detail in this chapter. We will then move on to implementing quantum routines such as quantum dot product and quantum Euclidean distances since they are integral to several machine learning algorithms such as the k-means clustering and nearest neighbor methods. In this regard, we will implement the k-means clustering method in detail. Also, we will discuss how Grover’s algorithm can be used to optimize quantum objectives by illustrating its usage in the cluster assignment in the k-means algorithm. Principal component analysis is an important machine learning technique, and we will walk through its quantum implementation in great detail as well.
Quantum Machine Learning (QML) is the convergence of two cutting-edge technologies—quantum computing and artificial intelligence—dedicated to rewriting computational horizons of pattern recognition, optimization, and prediction based on data. The present chapter is an introductory tutorial and cutting-edge coverage of theory foundations, algorithmic developments, and pedagogical models needed to bring QML into secondary and undergraduate classrooms. We then dispel magic from fundamental quantum-computing concepts such as qubits, superposition, entanglement, and quantum gates and demonstrate how they enable quantum algorithms such as the Quantum Fourier Transform, amplitude amplification, variational circuits, and quantum support-vector machines. From these building blocks, the chapter follows classical machine-learning pipelines—data encoding, feature extraction, model training, inference, and evaluation—and demonstrates how they map to their quantum equivalents, with emphasis on hybrid quantum-classical paradigms that are implementable on near-term noisy intermediate-scale quantum (NISQ) devices.
Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle
QRAM, the standard model studied in quantum query complexity, requires time
O(sqrtn) to encode vectors
vinRn into quantum states. We propose simple hardware augmentations to the oracle
QRAM, that enable vectors
vinRn to be encoded in time
O(logn), with pre-processing. The augmented
QRAM incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented
QRAM for vector state preparation, we present two different algorithms for singular value estimation where given singular vector
ketv for
AinRmtimesn, the singular value
sigmai is estimated within additive error
epsilonnormAF. The first algorithm requires time
wt1/epsilon3 and uses the approach for simulating
e−irho in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time
wt1/epsilon and uses Jordan's lemma from linear algebra and the augmented
QRAM to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and
CX and
CUR decompositions. Classical algorithms for these problems require time
O(mnlogn+poly(1/epsilon)), the quantum algorithms have running time
O(sqrtmpoly(1/epsilon,k,Delta)) where
k,Delta are the rank and spectral gap. The running time of the quantum
CX decomposition algorithm does not depend on
m, it is polynomial in problem parameters. We also provide quantum algorithms for
ell2 regularized regression problems, the quantum ridge regression algorithm requires time
wt1/mu2delta to output a quantum state that is
delta close to the solution, where
mu is the regularization parameter.