Advances in quantum computational learning theory.
详细信息
文摘
This dissertation explores results at the intersection of two important branches of theoretical computer science: quantum computation, which studies the power of computing devices based on quantum physical phenomena, and computational learning theory, which studies the foundations of machine learning algorithms. We refer to the area of research at this intersection as quantum computational learning theory. Like its classical counterpart, quantum computational learning theory aims to understand the computational and information theoretic requirements of learning problems and algorithms. However unlike the classical models, the models for quantum learners generally involve quantum sources of information and quantum gates employing quantum physical phenomena such as superposition and entanglement, which do not have classical equivalents.;Our results can be summarized as follows: (1) In Chapter 3, we study the information theoretic requirements of quantum exact learning, partition learning and "Probably Approximately Correct" (PAC) learning. First, we develop a new general quantum exact learning algorithm, resolving a conjecture by Hunziker et al. [HMP+03]. Next, we present positive and negative results towards the rather general problem of partition learning of which both "exact learning" and "computing a binary property" are special cases. Finally, we derive an improved lower bound on the number of quantum examples required for PAC learning. (2) In Chapter 4, we consider the problem of learning unions of high dimensional rectangles over the domain [b]n using membership queries and uniform quantum examples. These classes oral generalizations of classes of DNF formulae over {0,1}n that have been extensively studied in the learning theory literature. (3) In Chapter 5, we develop quantum algorithms for learning and testing juntas (Boolean functions that depend on a few variables) and learning sparse functions. These algorithms are based on the quantum subroutine due to Bshouty and Jackson [BJ99] that enables sampling from the Fourier spectrum.