We consider the following classes of quantified formulas. Fix a set of basic relations called a basis. Take conjunctions of these basic relations applied to variables and constants in arbitrary ways. Finally, quantify existentially or universally some of the variables. We introduce some conditions on the basis that guarantee efficient learnability. Furthermore, we show that with certain restrictions on the basis the classification is complete. We introduce, as an intermediate tool, a link between this class of quantified formulas and some well-studied structures in Universal Algebra called clones. More precisely, we prove that the computational complexity of the learnability of these formulas is completely determined by a simple algebraic property of the basis of relations, their clone of polymorphisms. Finally, we use this technique to give a simpler proof of the already known dichotomy theorem over boolean domains and we present an extension of this theorem to bases with infinite size.