Quantum algorithms for machine learning and optimization

dc.contributor.advisorChilds, Andrew M.en_US
dc.contributor.authorLi, Tongyangen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2020-07-08T05:34:47Z
dc.date.available2020-07-08T05:34:47Z
dc.date.issued2020en_US
dc.description.abstractThe 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.en_US
dc.identifierhttps://doi.org/10.13016/notw-y4tt
dc.identifier.urihttp://hdl.handle.net/1903/26068
dc.language.isoenen_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pqcontrolledQuantum physicsen_US
dc.subject.pquncontrolledMachine learningen_US
dc.subject.pquncontrolledOptimization theoryen_US
dc.subject.pquncontrolledQuantum algorithmsen_US
dc.subject.pquncontrolledQuantum computingen_US
dc.subject.pquncontrolledQuantum machine learningen_US
dc.subject.pquncontrolledTheoretical computer scienceen_US
dc.titleQuantum algorithms for machine learning and optimizationen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Li_umd_0117E_20678.pdf
Size:
2.54 MB
Format:
Adobe Portable Document Format