We consider Legendre-Bregman projections defined on the Hermitian matrix space and design iterative optimization algorithms based on them. A general duality theorem is established for Bregman divergences on Hermitian matrices, and it plays a crucial role in proving the convergence of the iterative algorithms. We study both exact and approximate Bregman projection algorithms. In the particular case of Kullback-Leibler divergence, our approximate iterative algorithm gives rise to the non-commutative versions of both the generalized iterative scaling (GIS) algorithm for maximum entropy inference and the AdaBoost algorithm in machine learning as special cases. As the Legendre-Bregman projections are simple matrix functions on Hermitian matrices, quantum algorithmic techniques are applicable to achieve potential speedups in each iteration of the algorithm. We discuss several quantum algorithmic design techniques applicable in our setting, including the smooth function evaluation technique, two-phase quantum minimum finding, and NISQ Gibbs state preparation.
We consider Legendre-Bregman projections defined on the Hermitian matrix space and design iterative optimization algorithms based on them. A general duality theorem is established for Bregman divergences on Hermitian matrices, and it plays a crucial role in proving the convergence of the iterative algorithms. We study both exact and approximate Bregman projection algorithms. In the particular case of Kullback-Leibler divergence, our approximate iterative algorithm gives rise to the non-commutative versions of both the generalized iterative scaling (GIS) algorithm for maximum entropy inference and the AdaBoost algorithm in machine learning as special cases. As the Legendre-Bregman projections are simple matrix functions on Hermitian matrices, quantum algorithmic techniques are applicable to achieve potential speedups in each iteration of the algorithm. We discuss several quantum algorithmic design techniques applicable in our setting, including the smooth function evaluation technique, two-phase quantum minimum finding, and NISQ Gibbs state preparation.
Maximum entropy inference and learning of graphical models are pivotal tasks in learning theory and optimization. This work extends algorithms for these problems, including generalized iterative scaling (GIS) and gradient descent (GD), to the quantum realm. While the generalization, known as quantum iterative scaling (QIS), is straightforward, the key challenge lies in the non-commutative nature of quantum problem instances, rendering the convergence rate analysis significantly more challenging than the classical case. Our principal technical contribution centers on a rigorous analysis of the convergence rates, involving the establishment of both lower and upper bounds on the spectral radius of the Jacobian matrix for each iteration of these algorithms. Furthermore, we explore quasi-Newton methods to enhance the performance of QIS and GD. Specifically, we propose using Anderson mixing and the L-BFGS method for QIS and GD, respectively. These quasi-Newton techniques exhibit remarkable efficiency gains, resulting in orders of magnitude improvements in performance. As an application, our algorithms provide a viable approach to designing Hamiltonian learning algorithms.
This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.
Density matrices are a central tool in quantum physics, but it is also used in machine learning. A positive definite matrix called kernel matrix is used to represent the similarities between examples. Positive definiteness assures that the examples are embedded in an Euclidean space. When a positive definite matrix is learned from data, one has to design an update rule that maintains the positive definiteness. Our update rule, called matrix exponentiated gradient update, is motivated by the quantum relative entropy. Notably, the relative entropy is an instance of Bregman divergences, which are asymmetric distance measures specifying theoretical properties of machine learning algorithms. Using the calculus commonly used in quantum physics, we prove an upperbound of the generalization error of online learning.
Density matrices are a central tool in quantum physics, but it is also used in machine learning. A positive definite matrix called kernel matrix is used to represent the similarities between examples. Positive definiteness assures that the examples are embedded in an Euclidean space. When a positive definite matrix is learned from data, one has to design an update rule that maintains the positive definiteness. Our update rule, called matrix exponentiated gradient update, is motivated by the quantum relative entropy. Notably, the relative entropy is an instance of Bregman divergences, which are asymmetric distance measures specifying theoretical properties of machine learning algorithms. Using the calculus commonly used in quantum physics, we prove an upperbound of the generalization error of online learning.
An ensemble of quantum states can be described by a Hermitian, positive semidefinite and unit trace matrix called density matrix. Thus, the study of methods for optimizing a certain function (energy, entropy) over the set of density matrices has a direct application to important problems in quantum information and computation. We propose a projected gradient method for solving such problems. By exploiting the geometry of the feasible set, which is the intersection of the cone of Hermitian positive semidefinite matrices with the hyperplane defined by the unit trace constraint, we describe an efficient procedure to compute the projection onto this set using the Frobenius norm. Some important applications, such as quantum state tomography, are described and numerical experiments illustrate the effectiveness of the method when compared to previous methods based on fixed-point iterations or semidefinite programming.
The theories of optimization and machine learning answer foundational questions in computer science and lead to new algorithms for practical applications. While these topics have been extensively studied in the context of classical computing, their quantum counterparts are far from well-understood. In this thesis, we explore algorithms that bridge the gap between the fields of quantum computing and machine learning. First, we consider general optimization problems with only function evaluations. For two core problems, namely general convex optimization and volume estimation of convex bodies, we give quantum algorithms as well as quantum lower bounds that constitute the quantum speedups of both problems to be polynomial compared to their classical counterparts. We then consider machine learning and optimization problems with input data stored explicitly as matrices. We first look at semidefinite programs and provide quantum algorithms with polynomial speedup compared to the classical state-of-the-art. We then move to machine learning and give the optimal quantum algorithms for linear and kernel-based classifications. To complement with our quantum algorithms, we also introduce a framework for quantum-inspired classical algorithms, showing that for low-rank matrix arithmetics there can only be polynomial quantum speedup. Finally, we study statistical problems on quantum computers, with the focus on testing properties of probability distributions. We show that for testing various properties including L1-distance, L2-distance, Shannon and Renyi entropies, etc., there are polynomial quantum speedups compared to their classical counterparts. We also extend these results to testing properties of quantum states.