Quantum machine learning is currently regarded as one of the most promising candidates for solving problems that appear out of reach using classical computers. Recently, a novel subfield of quantum...Show moreQuantum machine learning is currently regarded as one of the most promising candidates for solving problems that appear out of reach using classical computers. Recently, a novel subfield of quantum learning was opened up by Havlíček et al., who proposed a quantum learning algorithm which is closely related to support vector machines, yet which can be implemented on currently available quantum hardware. In this thesis, contribute to quantum machine learning by presenting new results on the capabilities of this algorithm, placing it in the perspectives of classical learning theory and quantum complexity. As the follow-up research which has since been published mainly focusses on details of experimental implementation, results in this direction are still lacking. Specifically, we compare the hyperplane (explicit) and kernel (implicit) formulations of the classifier algorithm, study its generalisation performance in the framework of statistical learning theory, and pin down the precise requirements for a quantum advantage using this algorithm. To this end, we apply the so-called representer theorem, known from the study of kernel methods in machine learning, to show training set optimality of the implicit formulation under regularised error measures. Furthermore, we show a tight upper bound on the fat shattering dimension of this type of quantum classifier, and discuss the implications for generalisation performance. Lastly, we carry out a complexity theoretic study showing that classical intractability of evaluating quantum kernels implies also the intractability of these quantum classifiers. We argue that despite this fact, we cannot claim that there exist problems which are hard to learn classically, but not quantumly, in the PAC learning sense, and subsequently describe the complexity theoretic requirements of quantum CLF learning to achieve quantum learning supremacy.Show less
