Dissertation/Thesis Abstract

Quantum Algorithms for Machine Learning and Optimization
by Li, Tongyang, Ph.D., University of Maryland, College Park, 2020, 404; 27830740
Abstract (Summary)

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 ℓ1-distance, ℓ2-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.

Indexing (document details)
Advisor: Childs, Andrew M.
Commitee: Waks, Edo, Huang, Furong, Liu, Yi-Kai, Wu, Xiaodi
School: University of Maryland, College Park
Department: Computer Science
School Location: United States -- Maryland
Source: DAI-B 82/1(E), Dissertation Abstracts International
Subjects: Computer science, Quantum physics
Keywords: Machine learning, Optimization theory, Quantum algorithms, Quantum computing, Quantum machine learning, Theoretical computer science
Publication Number: 27830740
ISBN: 9798662438484
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy