 Author

S. Arunachalam
 Title
 Quantum algorithms and learning theory
 Supervisors
 Award date
 25 April 2018
 Number of pages
 201
 ISBN
 9789402809848
 Document type
 PhD thesis
 Faculty
 Interfacultary Research Institutes
 Institute
 Institute for Logic, Language and Computation (ILLC)
 Abstract

This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms.
1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm.
2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this.
3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradientcalculation algorithm and a gradientoptimization algorithm that is quadratically faster than classical algorithms.
In the second part of this thesis we look at quantum learning theory.
1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model.
2) We then consider if a quantum learner can PAClearn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.  Note
 ILLC Dissertation Series DS201808.
 Permalink
 http://hdl.handle.net/11245.1/dbec2fe64eb34b4ab758bda4aa66798a
 Downloads
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.