UMD Theses and Dissertations

Permanent URI for this collectionhttp://hdl.handle.net/1903/3

New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a given thesis/dissertation in DRUM.

More information is available at Theses and Dissertations at University of Maryland Libraries.

Browse

Filters

2020 - 20232

Settings

Subject: search.filters.subject.Quantum algorithms

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Quantum Speedups: Structure, Design, and Application
    (2023) Wang, Daochen; Childs, Andrew M.; Miller, Carl A.; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    A quantum speedup occurs when a computational problem can be solved faster on a quantum computer than on a classical computer. This thesis studies the circumstances under which quantum speedups can arise from three perspectives. First, we study the structure of the problem. We characterize how a problem's symmetries decide whether it admits a superpolynomial or polynomial quantum speedup. In particular, we show that the computation of any partial function of a hypergraph's adjacency matrix admits at most a polynomial speedup. Such functions are only weakly symmetric and subsequent work shows that if the symmetry is weakened even further, then a superpolynomial speedup can be possible. To complete the picture for graph problems, we also construct a partial function of a graph's adjacency list that admits an exponential speedup. Second, we study classical paradigms for solving problems. We design a natural quantum query analogue of the divide and conquer paradigm, which we call the ``quantum divide and conquer'' framework. This framework allows us to quantumly speed up the solution of many problems that are classically solved using divide and conquer. The main technical novelty of our framework is that it naturally combines quantum adversary and quantum algorithmic techniques. To showcase its usefulness, we apply it to obtain near-optimal quantum query complexities for four string problems: (i) recognizing regular languages; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence. Third, we study ways of generalizing a problem known to admit a quantum speedup. We generalize the search problem of finding a marked item in a database to the case where the items are not either marked or unmarked, but are ``partially marked''. The goal is to find the item that is the most heavily marked. We construct a quantum algorithm for this problem within the variable-time framework and prove its near-optimality by modifying the standard adversary method to work for oracles encoding probability distributions. Coincidentally, the problem studied is equivalent to the multi-armed bandits problem in reinforcement learning, which has many applications.
  • Thumbnail Image
    Item
    Quantum algorithms for machine learning and optimization
    (2020) Li, Tongyang; Childs, Andrew M.; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    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.