  In this dissertation, we study the intersection of quantum computing and
supervised machine learning algorithms, which means that we investigate quantum
algorithms for supervised machine learning that operate on classical data. This
area of research falls under the umbrella of quantum machine learning, a
research area of computer science which has recently received wide attention.
In particular, we investigate to what extent quantum computers can be used to
accelerate supervised machine learning algorithms. The aim of this is to
develop a clear understanding of the promises and limitations of the current
state of the art of quantum algorithms for supervised machine learning, but
also to define directions for future research in this exciting field. We start
by looking at supervised quantum machine learning (QML) algorithms through the
lens of statistical learning theory. In this framework, we derive novel bounds
on the computational complexities of a large set of supervised QML algorithms
under the requirement of optimal learning rates. Next, we give a new bound for
Hamiltonian simulation of dense Hamiltonians, a major subroutine of most known
supervised QML algorithms, and then derive a classical algorithm with nearly
the same complexity. We then draw the parallels to recent "quantum-inspired"
results, and will explain the implications of these results for quantum machine
learning applications. Looking for areas which might bear larger advantages for
QML algorithms, we finally propose a novel algorithm for Quantum Boltzmann
machines, and argue that quantum algorithms for quantum data are one of the
most promising applications for QML with potentially exponential advantage over
classical approaches.
